Database Reference
In-Depth Information
Figure A2-7.
Graphic Representation of Synonym Chaining
Programmatically, the hash table may be implemented via any of the following
strategies (you are encouraged to try implementing this on your own):
•
An array of linked lists or queues
•
An array-list of linked lists or queues
•
An array-list of array-lists
Observe:
•
The table size
s
is the number of linked lists (chains), not the
number of nodes.
•
The average length of each chain is n/s where
n
is the number of
records (nodes).
•
The load factor
s
is therefore the average length of each chain.
•
An unsuccessful search will involve the examination of
f
items;
a successful search will require an average of 1 + f/2 examinations.
So as expected, the performance is significantly better than linear
probing.
Synonym chaining has the following advantages:
•
The technique reduces access time for records with collision
addresses.
•
It is relatively easy to insert nodes in a given chain.
•
There is even distribution of keys (nodes) over address space.
