Open Addressing

Closed Addressing

Also known as closed hashing.

Also known as open hashing.

Collisions are dealt with by searching for another empty buckets within the hash table array itself.

A key is always stored in the bucket it's hashed to. Collisions are dealt with using separate data structures on a per-bucket basis.

At most one key per bucket.

Arbitrary number of keys per bucket.

Characteristic structure (colors denote "home" bucket):

Characteristic structure (colors denote "home" bucket):

Example techniques:

• Linear Probing
• Quadratic Probing
• Double hashing
• Hopscotch hashing
• Robin Hood hashing
• Cuckoo hashing
• 2-Choice hashing

Example techniques:

• Separate chaining using linked lists
• Separate chaining using dynamic arrays
• Using self-balancing binary search trees

Theoretical maximum load factor of 1.

No theoretical maximum load factor.

The size of the hash table array must always be at least as large as the number of keys in the hash table.

Performance degrades as load factor grows.

Benefits:

• No size overhead apart from the hash table array.
• Better memory locality and cache performance. All elements laid out linearly in memory.
• Performs better than closed addressing when the number of keys is known in advance and the churn is low.

Benefits:

• Easier removal (no need for deleted markings)
• Typically performs better with high load factor.
• No issues with clustering.

For more details on open addressing, see Hash Tables: Open Addressing.

The most common closed addressing implementation uses separate chaining with linked lists. This approach is described in detail the introductory article.