SEPARATE CHAINING (OPEN HASHING) (OR) EXTERNAL HASHING:
Separate chaining is a collision resolution technique, in which we can keep the list of all elements that hash to same value. This is called as separate chaining because each hash table element is a separate chain (linked list).
Each link list contains the entire element whose keys hash to the same index. All
keys that map to the same hash value are kept in a list (or “bucket”).. The example is given as follows.
The tradeoff is the same as with linked lists versus array implementations of collections: linked list overhead in space and, to a lesser extent, in time.
Unlimited number of elements
Unlimited number of collisions
Overhead of multiple linked lists
The elements are not evenly distributed. Some hash index may have more elements and some may not have anything.
It requires pointers which require more memory space. This leads to slow the algorithm down a bit because of the time required to allocate the new cells, and also essentially requires the implementation of second data structure.