Hashing Collisions and How They Work

Learn Hashing Collisions and How They Work with practical examples, explanations, best practices, and real-world coding techniques.

What Is a Hashing Collision?

A hashing collision occurs when two different keys are mapped to the same bucket or table index by a hash function. Collisions are a normal part of hash table design because a hash table has a finite number of storage locations while the possible number of keys can be much larger.

Example: If both "alice" and "bob" produce index 3, both keys are competing for the same bucket. 

hash("alice") % 10 = 3
hash("bob")   % 10 = 3

"alice" → Bucket 3
"bob"   → Bucket 3

Collision!

Why Do Hash Collisions Occur?

A hash function maps a potentially very large set of keys into a limited set of table positions. For example, a table with 10 buckets can only produce indexes from 0 through 9.

Even if the hash function produces large hash values, the values must eventually be mapped to the available table size. 

Hash value: 127
Table size: 10

127 % 10 = 7

Hash value: 37
Table size: 10

37 % 10 = 7

Different hash values
        ↓
Same table index
        ↓
Collision

Therefore, even different hash values can map to the same bucket.

Hash Collision Example

Consider a hash table with five buckets and a simple numeric hash function: 

index = key % 5

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

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

All three keys produce the same bucket index. Without a collision-resolution technique, storing all three values would not be possible in a single-slot bucket.

Collision Resolution

A hash table needs a strategy for handling multiple keys that map to the same location. These strategies are called collision-resolution techniques.

Two major approaches are:

  • Separate chaining — store multiple entries in the same bucket.
  • Open addressing — find another empty position inside the table.

Separate Chaining

Separate chaining stores multiple entries that map to the same bucket in a collection such as a linked list or dynamic array. 

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

When searching for a key, the hash function identifies the bucket first. The implementation then searches the entries stored inside that bucket.

Simple Chaining Implementation

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

  hash(key) {
    let hash = 0;

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

    return hash;
  }

  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 entry = this.buckets[index].find(
      item => item.key === key
    );

    return entry?.value;
  }
}

const table = new HashTable();

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

console.log(table.get('alice'));
console.log(table.get('bob'));

Advantages of Separate Chaining

  • Multiple entries can be stored in the same bucket.
  • The table can continue accepting entries even when many buckets are occupied.
  • Deletion is generally straightforward.
  • It can be simpler to implement than some open-addressing strategies.

Limitations of Separate Chaining

  • Long chains can make lookup slower.
  • Additional memory is required for the bucket collections.
  • Poor hash distribution can create heavily populated buckets.

Open Addressing

In open addressing, every entry is stored directly inside the hash table. When the calculated position is already occupied, the implementation searches for another available position according to a probing strategy. 

Initial position:

hash("alice") → 3

Bucket 3 → occupied

Probe another position:

3 → 4 → 5 → ...

Find an available bucket.

Open addressing therefore requires the table to have available slots for new entries. The probing method determines how those slots are searched.

Linear Probing

Linear probing checks consecutive positions when a collision occurs. If the original position is occupied, the next position is examined, followed by the next, until an available slot is found. 

index = hash(key) % tableSize

If index is occupied:

(index + 1) % tableSize
(index + 2) % tableSize
(index + 3) % tableSize
...

For example, if the original index is 4 and bucket 4 is occupied: 

4 → 5 → 6 → 7 → ...

Suppose bucket 6 is empty.

Store the entry at bucket 6.

Linear Probing Example

Table size = 7

Key 10:
10 % 7 = 3
Store at index 3

Key 17:
17 % 7 = 3
Collision
Try index 4
Store at index 4

Key 24:
24 % 7 = 3
Collision
Try index 4
Collision
Try index 5
Store at index 5

Primary Clustering

Linear probing can create primary clustering. This happens when consecutive occupied positions form groups that grow as additional collisions occur. 

Index:

0   1   2   3   4   5   6
        X   X   X
        ↑       ↑
      cluster grows

Larger clusters can increase the number of positions that must be examined during insertion and lookup.

Quadratic Probing

Quadratic probing changes the probe distance as the number of attempts increases. Instead of checking consecutive positions, it uses increasingly larger offsets. 

index = hash(key) % tableSize

Probe sequence:

index
index + 1²
index + 2²
index + 3²
index + 4²
...

With modulo arithmetic, the actual index is kept within the table: 

probeIndex =
  (index + attempt * attempt) % tableSize

Quadratic probing can reduce the primary clustering associated with linear probing, although it has its own behavior and table-size considerations.

Double Hashing

Double hashing uses a second hash function to determine the step size for probing. This produces a probe sequence that depends on the key rather than using the same fixed sequence for every collision. 

index = hash1(key)

step = hash2(key)

probeIndex =
  (index + attempt * step) % tableSize

A well-designed second hash function helps distribute probe sequences and can reduce clustering compared with simple linear probing.

Collision Resolution Comparison

Technique How It Handles Collisions Main Consideration
Separate chaining Stores multiple entries in a bucket Long chains can slow lookup
Linear probing Checks the next available table position Primary clustering
Quadratic probing Uses quadratic probe offsets Probe sequence and table-size constraints
Double hashing Uses a second hash to calculate probe steps Requires a suitable second hash function

Collision Resolution and Lookup

Collision handling affects not only insertion but also searching and deletion. A lookup must follow the same collision-resolution rules used when the entry was inserted.

For example, with linear probing: 

Insert "alice":

hash("alice") → 3
3 occupied
4 occupied
5 empty

"alice" stored at 5


Lookup "alice":

hash("alice") → 3
Check 3
Check 4
Check 5
Found "alice"

Simply checking the original hash position would not be enough.

Deletion in Open Addressing

Deletion requires special care in open-addressed hash tables. Simply marking a slot as completely empty can break the probe sequence used by later searches. 

Suppose:

3 → A
4 → B
5 → C

B is deleted.

If bucket 4 becomes "empty",
a search for C might stop at 4
and incorrectly conclude that C does not exist.

Implementations can therefore use a special deleted marker, often called a tombstone, so probing can continue through previously occupied positions.

Load Factor and Collisions

The load factor is the ratio between the number of stored entries and the number of available buckets. 

Load Factor =
Number of Entries / Number of Buckets

Example:

8 entries / 10 buckets = 0.8

As the load factor increases, collisions generally become more frequent, particularly in open-addressed tables. Hash-table implementations commonly resize the table before the load becomes too high.

Rehashing

Rehashing means creating a larger table and inserting existing entries again using the new table size. The bucket index may change because the table-size component of the hash calculation has changed. 

Old table size = 5

hashValue = 17

17 % 5 = 2


New table size = 11

17 % 11 = 6

Old index → 2
New index → 6

This is why entries generally cannot simply be copied to the same indexes after resizing. They need to be redistributed.

How a Poor Hash Function Increases Collisions

Collision frequency is influenced by both the number of entries and how effectively the hash function distributes keys.

For example, a hash function that only examines the first character of a username can produce poor distribution if many usernames begin with the same character. 

hash("alice") → based only on 'a'
hash("adam")  → based only on 'a'
hash("anna")  → based only on 'a'

Many keys → same region

A better hash function incorporates more information from the key so that similar keys do not unnecessarily cluster together.

Collision Does Not Mean Equal Keys

One of the most important concepts in hashing is that a collision does not mean that the keys are equal. 

hash("cat") = 42
hash("dog") = 42

"cat" !== "dog"

Same hash value
≠
Same key

Hash tables therefore use key equality checks after locating the appropriate bucket or probe position.

Hash Collisions in JavaScript Map and Set

JavaScript provides built-in Map and Set collections that provide efficient key-based operations. Their internal implementation details are handled by the JavaScript engine, so developers normally do not implement collision resolution themselves. 

const users = new Map();

users.set('alice', 100);
users.set('bob', 200);

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

const uniqueNumbers = new Set([
  10,
  20,
  10,
  30
]);

console.log(uniqueNumbers);
// Set(3) { 10, 20, 30 }

The important data-structure concept is understanding that these collections require an internal strategy for mapping keys and handling cases where different keys compete for the same internal location.

Average and Worst-Case Performance

With a well-designed hash table and a suitable load factor, insertion, search, and deletion are commonly expected to take O(1) average time.

However, excessive collisions can increase the amount of work required. In the worst case, many keys may end up competing for the same locations, causing an operation to approach O(n) time.

Operation Average Case Worst Case
Search O(1) O(n)
Insertion O(1) O(n)
Deletion O(1) O(n)

Choosing a Collision Resolution Technique

The appropriate collision-resolution strategy depends on the requirements of the hash table. The main approaches can be remembered by how they respond when the preferred location is already occupied.

  • Separate chaining: keep multiple entries in the same bucket.
  • Linear probing: check the next positions sequentially.
  • Quadratic probing: increase the probe distance quadratically.
  • Double hashing: use another hash function to determine the probe step.

Real-World Applications

Collision handling is relevant anywhere hash-based data structures are used. Common applications include:

  • User and session lookup.
  • Caching systems.
  • Database indexing structures.
  • Compiler symbol tables.
  • Duplicate detection.
  • Frequency counting.
  • Graph traversal with visited sets.
  • In-memory key-value storage.

Common Mistakes with Hash Collisions

1. Assuming Hashes Are Unique

A hash function maps many possible keys into a limited set of values or indexes. Different keys can therefore produce the same result.

2. Ignoring Collision Resolution

A hash function only determines the preferred location. A complete hash table also needs a strategy for handling occupied locations.

3. Forgetting Key Equality

Two keys can have the same hash value but still represent different entries. The actual keys must be compared when necessary.

4. Allowing the Load Factor to Grow Excessively

A crowded table generally increases collisions and can reduce practical performance. Resizing and rehashing are common techniques for controlling this problem.

5. Mishandling Deletion in Open Addressing

Removing an entry by simply marking its position empty can interrupt a probing sequence. Open-addressed implementations need an appropriate deletion strategy.

Hash Collisions in Interview Questions

Hashing collisions are a common data-structures interview concept because they test whether you understand what happens inside a hash table rather than only knowing how to use a Map or dictionary.

Be prepared to explain:

  • What a hash collision is.
  • Why collisions are unavoidable.
  • How separate chaining works.
  • How open addressing works.
  • Linear probing, quadratic probing, and double hashing.
  • How load factor affects performance.
  • Why resizing requires rehashing.
  • Why equal hash values do not imply equal keys.
  • Why poor distribution can degrade hash-table performance.

Key Takeaways

  • A hashing collision occurs when different keys map to the same bucket or table index.
  • Collisions are unavoidable because the key space can be much larger than the table.
  • Separate chaining stores multiple entries within a bucket.
  • Open addressing searches for another position within the table.
  • Linear probing checks consecutive positions.
  • Quadratic probing uses increasingly larger probe offsets.
  • Double hashing uses a second hash function to determine the probe step.
  • High load factors generally increase collision-related work.
  • Resizing usually requires entries to be rehashed for the new table size.
  • Different keys can have the same hash value, so hash equality is not key equality.
  • Good collision handling is essential for maintaining efficient hash-table operations.

Code Examples 

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

  hash(key) {
    let hash = 0;

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

    return hash;
  }

  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 entry = this.buckets[index].find(
      item => item.key === key
    );

    return entry?.value;
  }
}

const table = new HashTable();

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

console.log(table.get('alice'));
console.log(table.get('bob'));
    
class LinearProbingHashTable {
  constructor(size = 7) {
    this.table = new Array(size);
  }

  hash(key) {
    return key % this.table.length;
  }

  set(key, value) {
    let index = this.hash(key);

    while (
      this.table[index] &&
      this.table[index].key !== key
    ) {
      index = (index + 1) % this.table.length;
    }

    this.table[index] = { key, value };
  }

  get(key) {
    let index = this.hash(key);
    const start = index;

    while (this.table[index]) {
      if (this.table[index].key === key) {
        return this.table[index].value;
      }

      index = (index + 1) % this.table.length;

      if (index === start) {
        break;
      }
    }

    return undefined;
  }
}

const table = new LinearProbingHashTable();

table.set(10, 'A');
table.set(17, 'B');
table.set(24, 'C');

console.log(table.get(10));
console.log(table.get(17));
console.log(table.get(24));
    
const tableSize = 5;

const keys = [10, 15, 20];

for (const key of keys) {
  const index = key % tableSize;

  console.log(
    `Key ${key} → Bucket ${index}`
  );
}

// Output:
// Key 10 → Bucket 0
// Key 15 → Bucket 0
// Key 20 → Bucket 0

// All three keys collide.

Pro Tip

When explaining hash collisions, remember the complete chain: key → hash function → bucket index → collision handling → key equality check. A collision is not a failure of hashing; it is an expected situation that the hash-table design must handle efficiently.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.