Java Reference
In-Depth Information
Figure 5-4. A complex hashtable maps keys to buckets that store references to linked lists whose
node values are hashed from the same keys.
Whenstoringavalueinahashtable,thehashtableusesthehashfunctiontohashthe
keytoitshashcode,andthensearchestheappropriatelinkedlisttoseeifanentrywith
amatchingkeyexists.Ifthereisanentry,itsvalueisupdatedwiththenewvalue.Other-
wise, a new node is created, populated with the key and value, and appended to the list.
When retrieving a value from a hashtable, the hashtable uses the hash function to
hash the key to its hash code, and then searches the appropriate linked list to see if an
entrywithamatchingkeyexists.Ifthereisanentry,itsvalueisreturned.Otherwise,the
hashtablemayreturnaspecialvaluetoindicatethatthereisnoentry,oritmightthrow
an exception.
Thenumberofbucketsisknownasthehashtable's capacity .Theratioofthenumber
of stored entries divided by the number of buckets is known as the hashtable's load
factor . Choosing the right load factor is important for balancing performance with
memory use:
• As the load factor approaches 1, the probability of collisions and the cost of
handling them (by searching lengthy linked lists) increase.
• Astheloadfactorapproaches0,thehashtable'ssizeintermsofnumberofbuck-
ets increases with little improvement in search cost.
Search WWH ::




Custom Search