Home | | Fundamentals of Data Structures in C | | Data Structures | | Programming and Data Structures I | Separate Chaining (Open Hashing) (or) External Hashing

Chapter: Programming and Data Structures - Sorting And Searching

| Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail |

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).


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.

 

Advantages:

Unlimited number of elements

Unlimited number of collisions

 

Disasdvantages:

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.


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail


Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.