Open Addressing vs Chaining: Hash Collisions

The Conflict of Collisions

When you build a hash map, you are fundamentally mapping keys to a fixed array size using a hash function. Sooner or later, two different keys will produce the same index. This is a collision. How you handle that collision dictates the performance of your entire system. The two primary schools of thought are chaining and open addressing.

Chaining: The Linked List Approach

Chaining is the default for most people. You keep an array of buckets, and each bucket is a pointer to a linked list (or sometimes a balanced tree). When a collision happens, you just append the new item to the end of that list.

1
// A basic concept of chaining
2
class HashTable {
3
  constructor(size) {
4
    this.table = new Array(size).fill(null).map(() => []);
5
  }
6

7
  set(key, value) {
8
    const index = hash(key) % this.table.length;
9
    this.table[index].push({ key, value });
10
  }
11
}

Chaining is easy to implement. You don’t have to worry about the table getting ‘full’ in the traditional sense, though performance drops if your lists get too long. Because each node is a separate object, you also face memory overhead due to the pointers. It is forgiving, but not always cache-friendly.

Open Addressing: Keeping It Together

Open addressing is more aggressive. You do not use linked lists. If the slot is taken, you search for the next available slot in the array itself. This is often called probing. Common techniques include linear probing (just checking index + 1) or quadratic probing.

1
// A conceptual look at linear probing
2
set(key, value) {
3
  let index = hash(key) % this.table.length;
4
  while (this.table[index] !== null) {
5
    index = (index + 1) % this.table.length;
6
  }
7
  this.table[index] = { key, value };
8
}

This approach is incredibly fast when the load factor is low. Because everything is stored directly in the array, you get better cache locality. CPUs love sequential memory access. If your array fits in the L1 or L2 cache, open addressing usually crushes chaining in speed tests.

Which Should You Choose?

The answer depends on how much you care about micro-optimizations versus simplicity.

If you want a robust system where you don’t know the upper bound of your data, chaining is the safer bet. It handles high load factors without catastrophic performance degradation. However, it will consume more memory and perform more allocations because every insertion creates a new node object.

If you are writing a low-level library, or a system where performance is tight, go with open addressing. You will need to manage the load factor carefully, though. Once you fill up about 70-80% of your array, open addressing performance starts to degrade exponentially. You have to trigger a resize earlier than you would with chaining.

The Takeaway

Most modern languages like Python use open addressing for their built-in dictionaries because it is generally faster for common usage patterns. The trade-off is that it requires more sophisticated resizing logic.

Don’t overthink this for basic CRUD applications. In most web development contexts, the bottleneck will be your database or your network calls, not the collision resolution strategy of your hash map. But if you find yourself writing a custom cache layer or a performance-sensitive data pipeline, consider how your memory is being accessed. If your data fits in cache, open addressing is a winner. If your data is massive and erratic, stick to chaining to avoid complex resizing nightmares.