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.
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
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
• As the load factor approaches 1, the probability of collisions and the cost of
handling them (by searching lengthy linked lists) increase.
ets increases with little improvement in search cost.