Java Reference
In-Depth Information
Figure 5-3.
A simple hashtable maps keys to buckets that store values associates with
those keys.
Thehashfunctionhashes
Bob Doe
to
0
,whichidentifiesthefirstbucket.Thisbuck-
etcontains
ACCTS
,whichis
Bob Doe
'semployeetype.Thehashfunctionalsohashes
John Doe
and
Sally Doe
to
1
and
2
(respectively)whosebucketscontain
SALES
.
Aperfecthashfunctionhasheseachkeytoauniqueintegervalue.However,thisideal
isverydifficulttomeet.Inpractice,somekeyswillhashtothesameintegervalue.This
nonunique mapping is referred to as a
collision
.
Toaddresscollisions,mosthashtablesassociatealinkedlistofentrieswithabucket.
Instead of containing a value, the bucket contains the address of the first node in the
linked list, and each node contains one of the colliding entries. See
Figure 5-4
.
