[hash] Meaning of Open hashing and Closed hashing

Open Hashing (Separate Chaining):

In open hashing, keys are stored in linked lists attached to cells of a hash table.

Closed Hashing (Open Addressing):

In closed hashing, all keys are stored in the hash table itself without the use of linked lists.

I am unable to understand why they are called open, closed and Separate. Can some one explain it?

This question is related to hash

The answer is


You have an array that is the "hash table".

In Open Hashing each cell in the array points to a list containg the collisions. The hashing has produced the same index for all items in the linked list.

In Closed Hashing you use only one array for everything. You store the collisions in the same array. The trick is to use some smart way to jump from collision to collision unitl you find what you want. And do this in a reproducible / deterministic way.


The name open addressing refers to the fact that the location ("address") of the element is not determined by its hash value. (This method is also called closed hashing).

In separate chaining, each bucket is independent, and has some sort of ADT (list, binary search trees, etc) of entries with the same index. In a good hash table, each bucket has zero or one entries, because we need operations of order O(1) for insert, search, etc.

This is a example of separate chaining using C++ with a simple hash function using mod operator (clearly, a bad hash function)