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.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.