Hashing Collision Handling with Chaining Tutorial

What Is Chaining in Hashing?

Chaining, also called separate chaining, is a collision resolution technique used in hash tables. When multiple keys are mapped to the same bucket by a hash function, chaining stores those entries together in that bucket instead of looking for another empty position in the table.

Each bucket can contain a collection of entries, commonly represented using a linked list, dynamic array, or another suitable collection.

Basic idea: Hash Key → Bucket → Collection of Entries

Hash Table

Bucket 0 → []
Bucket 1 → []
Bucket 2 → [
  ("alice", 100),
  ("bob", 200)
]
Bucket 3 → []
Bucket 4 → [
  ("carol", 300)
]

Here, alice and bob produced the same bucket index. Instead of treating the collision as an error, the hash table stores both entries in the collection associated with that bucket.

Why Is Chaining Needed?

A hash function maps a potentially large set of keys to a limited number of buckets. Because there are fewer buckets than possible keys, different keys can eventually map to the same location.

For example, suppose the table contains five buckets and uses:

index = key % 5

Several keys can map to bucket zero:

10 % 5 = 0
15 % 5 = 0
20 % 5 = 0

10 → Bucket 0
15 → Bucket 0
20 → Bucket 0

Chaining allows bucket zero to hold all three entries.

How Separate Chaining Works

The process is straightforward. The hash function first determines the bucket. The entry is then added to the collection associated with that bucket.

Receive the key and value.
Calculate the key's hash value.
Convert the hash value into a bucket index.
Access the collection stored at that bucket.
Search for the key if it already exists.
Update the existing value or add a new entry.

Key: "alice"

      ↓

Hash Function

      ↓

Index: 2

      ↓

Bucket 2

      ↓

[("alice", 100)]

Bucket Structure in Chaining

The table itself contains an array of buckets. Each bucket contains zero or more entries. A bucket can therefore be thought of as a small collection inside the larger hash table.

Index 0 → []
Index 1 → [A]
Index 2 → [B → C → D]
Index 3 → []
Index 4 → [E]

In a linked-list implementation, the entries in bucket two might form a chain:

Bucket 2
   ↓
[A] → [B] → [C] → [D] → null

Chaining with Linked Lists

A linked list is a traditional way to implement the collection associated with each bucket. Each node stores the key, value, and a reference to the next entry.

Bucket 3

┌──────────────┐
│ key: alice   │
│ value: 100   │
│ next ────────┼─────┐
└──────────────┘     ↓
               ┌──────────────┐
               │ key: bob     │
               │ value: 200   │
               │ next → null  │
               └──────────────┘

Linked-list chaining is useful because a bucket can grow without requiring the table itself to move the existing entries to neighboring positions.

Chaining with Arrays

A bucket can also be represented by an array. This approach is convenient in languages such as JavaScript where arrays are readily available.

const buckets = [
  [],
  [],
  [
    { key: 'alice', value: 100 },
    { key: 'bob', value: 200 }
  ],
  [],
  []
];

The underlying collection can vary by implementation. The important concept is that multiple entries are allowed within the same bucket.

Insertion Using Chaining

During insertion, the hash table calculates the bucket index and then examines that bucket. If the key already exists, its value can be updated. Otherwise, a new entry is added to the bucket.

function insert(table, key, value) {
  const index = hash(key);
  const bucket = table[index];

  const existing = bucket.find(
    entry => entry.key === key
  );

  if (existing) {
    existing.value = value;
  } else {
    bucket.push({ key, value });
  }
}

Searching with Chaining

Searching follows the same hash calculation used during insertion. Once the correct bucket is identified, the implementation searches only that bucket rather than scanning the entire table.

Search for "bob"

"bob"
  ↓
Hash function
  ↓
Bucket 2
  ↓
Search bucket 2
  ↓
alice → bob → carol
          ↑
        found

The actual key must still be compared because different keys can have the same hash value and therefore belong to the same chain.

Deletion Using Chaining

Deletion is generally simpler with separate chaining because removing an entry does not require shifting or probing through other table positions.

The table calculates the bucket, locates the entry inside that bucket, and removes it from the bucket collection.

Before:

Bucket 2
[A] → [B] → [C]


Delete B:


Bucket 2
[A] → [C]

With a linked list, the node can be removed by reconnecting the surrounding nodes. With an array-based bucket, the implementation can remove the corresponding array element.

Complete Chaining Implementation in JavaScript

The following example implements a basic hash table using separate chaining. Each bucket is represented by an array of key-value entries.

class HashTable {
  constructor(size = 7) {
    this.buckets = Array.from(
      { length: size },
      () => []
    );
  }

  hash(key) {
    let hashValue = 0;

    for (const char of key) {
      hashValue =
        (hashValue * 31 + char.charCodeAt(0)) %
        this.buckets.length;
    }

    return hashValue;
  }

  set(key, value) {
    const index = this.hash(key);
    const bucket = this.buckets[index];

    const existing = bucket.find(
      entry => entry.key === key
    );

    if (existing) {
      existing.value = value;
      return;
    }

    bucket.push({ key, value });
  }

  get(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];

    const entry = bucket.find(
      item => item.key === key
    );

    return entry ? entry.value : undefined;
  }

  delete(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];

    const entryIndex = bucket.findIndex(
      item => item.key === key
    );

    if (entryIndex === -1) {
      return false;
    }

    bucket.splice(entryIndex, 1);
    return true;
  }
}

const table = new HashTable();

table.set('alice', 100);
table.set('bob', 200);
table.set('carol', 300);

console.log(table.get('alice'));
// 100

console.log(table.delete('bob'));
// true

console.log(table.get('bob'));
// undefined

How Collisions Are Stored in a Chain

Suppose three keys happen to produce the same bucket index. With chaining, the entries can all remain associated with that bucket.

Key "A" → Bucket 3
Key "B" → Bucket 3
Key "C" → Bucket 3

Bucket 3:

[A] → [B] → [C]

A lookup for "C" first calculates bucket three and then checks the entries in that chain until the matching key is found.

Load Factor in Separate Chaining

The load factor is commonly expressed as the number of stored entries divided by the number of buckets.

Load Factor =
Number of Entries / Number of Buckets

For example, if a hash table has 8 buckets and contains 12 entries:

12 / 8 = 1.5

With separate chaining, a load factor greater than one is possible because each bucket can contain multiple entries. However, as the average chain length grows, searches within buckets generally require more work.

Chaining and Hash Function Quality

Chaining does not eliminate the importance of a good hash function. A poorly distributed hash function can place a large number of keys into the same bucket, creating long chains.

Poor distribution:

Bucket 0 → A → B → C → D → E → F
Bucket 1 → []
Bucket 2 → []
Bucket 3 → []


Better distribution:

Bucket 0 → A
Bucket 1 → D
Bucket 2 → B
Bucket 3 → F
Bucket 4 → C
Bucket 5 → E

Better distribution generally results in shorter chains and more predictable hash-table performance.

Time Complexity of Chaining

Under typical assumptions about the hash function and load factor, hash-table operations using separate chaining are expected to be efficient.

Operation	Average Case	Worst Case
Search	O(1) expected	O(n)
Insertion	O(1) expected	O(n)
Deletion	O(1) expected	O(n)
Space	O(n + m)	O(n + m)

Here, n represents the number of stored entries and m represents the number of buckets. In the worst case, all keys can end up in one chain, making a lookup potentially O(n).

Chaining vs Open Addressing

Separate chaining and open addressing solve the same fundamental problem but organize collided entries differently.

Feature	Separate Chaining	Open Addressing
Collision handling	Stores entries in the same bucket	Searches for another table position
Storage	Buckets contain collections	Entries stay inside the table
Load factor	Can exceed 1	Must remain below table capacity
Deletion	Generally straightforward	Requires careful probing/deletion handling
Extra structure	Uses bucket collections	Does not require bucket chains

Advantages of Separate Chaining

Flexible Bucket Size

A bucket can contain multiple entries, so the table does not require one free slot for every new entry at the moment of insertion.

Simple Collision Handling

The implementation can simply add a collided entry to the bucket's collection instead of calculating a probe sequence.

Straightforward Deletion

Removing an entry from a chain does not require the probing adjustments associated with open-addressed tables.

Supports Higher Load Factors

Since buckets can contain multiple entries, the number of entries can exceed the number of buckets. Performance still depends on keeping chains reasonably short.

Limitations of Separate Chaining

Long chains can make lookup slower.
Additional memory is needed for bucket collections.
Poor hash functions can cause severe clustering inside buckets.
Memory access patterns can depend on the bucket collection implementation.
Resizing may still be necessary when the average chain length becomes too large.

Chaining with Frequency Counting

Hash tables using chaining can support common frequency-counting tasks. The key identifies the item while the value stores its count.

const words = [
  'apple',
  'banana',
  'apple',
  'orange',
  'banana',
  'apple'
];

const frequency = new Map();

for (const word of words) {
  frequency.set(
    word,
    (frequency.get(word) ?? 0) + 1
  );
}

console.log(frequency);

// apple → 3
// banana → 2
// orange → 1

The built-in Map manages its internal hashing and collision handling, so application developers generally do not need to implement chaining manually.

Chaining in Real-World Systems

Separate chaining is an important technique for understanding how hash-based collections can handle collisions. The exact implementation used by a particular programming language or runtime can differ and should not be assumed to use a specific internal structure without checking its implementation details.

The general concept appears in many applications involving key-based lookup, including:

In-memory key-value storage.
Caching.
Symbol tables.
Frequency counting.
Duplicate detection.
Lookup tables.
Visited-item tracking in graph algorithms.

When Does Chaining Become Expensive?

Chaining becomes less efficient when individual buckets contain many entries. If a lookup must examine a long chain, the operation requires more comparisons.

Bucket 4:

[A] → [B] → [C] → [D] → [E] → [F] → [G]

Search for G:

A → B → C → D → E → F → G

A good hash function, suitable table sizing, and controlled load factor help reduce the probability of very long chains.

Chaining and Rehashing

A hash table may resize when its load factor becomes too high. When the number of buckets changes, the bucket index calculated from a key can also change.

Old table:

17 % 5 = 2


New table:

17 % 11 = 6

Existing entries therefore need to be rehashed and placed into their new buckets. This process is commonly called rehashing.

Common Mistakes When Learning Chaining

1. Thinking One Bucket Holds Only One Entry

That is not how separate chaining works. A bucket can contain multiple entries.

2. Assuming Collisions Are Errors

Collisions are expected in hash tables. The collision-resolution strategy determines how the table continues operating when they occur.

3. Comparing Only Hash Values

Different keys can have the same hash value. After locating the bucket, the actual key must be checked.

4. Ignoring Load Factor

Chaining can support multiple entries per bucket, but very long chains still affect lookup performance.

5. Assuming All Hash Tables Use Chaining

Hash tables can use different collision-resolution techniques, including separate chaining and open addressing. A particular programming language may use an implementation that differs from a textbook example.

Chaining in Data Structures Interviews

Separate chaining is a common hash-table interview topic. A strong explanation should connect the hash function, bucket selection, collision, and bucket collection into one process.

You should be able to explain:

What a collision is.
Why collisions are unavoidable.
What separate chaining means.
How a bucket stores multiple entries.
How insertion works.
How lookup searches a chain.
How deletion works.
How load factor affects chain length.
Why rehashing may be necessary.
How chaining differs from open addressing.

Key Takeaways

Separate chaining is a collision-resolution technique for hash tables.
Each bucket can contain multiple entries.
Linked lists and arrays are common ways to represent bucket chains.
The hash function determines which bucket should be searched.
Actual key comparison is required because different keys can collide.
Insertion, search, and deletion are typically O(1) expected with suitable hashing and load factor.
The worst-case operation can become O(n) when many entries form a long chain.
A load factor greater than 1 is possible with separate chaining.
Good hash distribution helps keep chains short.
Resizing a hash table generally requires rehashing existing entries.
Chaining and open addressing are different approaches to resolving hash collisions.

Topics

Hashing Collision Handling with Chaining