Algorithms in a Nutshell

(^126) | Chapter 5: Searching
Table 5-6 shows the actual load factor in the hash tables we create asbincreases.
Note how the maximum length of the element linked lists drops consistently
while the number of bins containing a unique element rapidly increases oncebis
sufficiently large. You can see that the performance of hash tables becomes O(1)
when the size of the hash table is sufficiently large.
The performance of the existingjava.util.Hashtableclass outperforms our
example code, but the savings are reduced as the size of the hash table grows. The
reason is thatjava.util.Hashtablehas optimized list classes that efficiently
manage the element chains. In addition,java.util.Hashtable automatically
“rehashes” the entire hash table when the load factor is too high; the rehash
strategy is discussed in the “Variations” section, next. It increases the cost of
building the hash table but improves the performance of searching. If we prevent
the “rehash” capability, then the performance of search injava.util.Hashtableis
nearly consistent with our implementation. Table 5-7 shows the number of times
rehash is invoked when building thejava.util.Hashtablehash table and the total
time (in milliseconds) required to build the hash table. We constructed the hash
tables from the word list described earlier; after running 100 trials the best and
Table 5-5. Search time (in milliseconds) for various hash table sizes
b Our hashtable shown in Example 5-8 java.util.Hashtable with default capacity
p = 1.0 p = 0.0 p = 1.0 p = 0.0
4,095 1143.33 2039.10 104.42 47.85
8,191 673.91 1095.67 99.48 45.26
16,383 433.87 615.63 111.74 48.60
32,767 308.03 364.88 107.11 47.33
65,535 237.07 245.86 98.53 45.14
131,071 194.37 172.81 98.53 44.47
262,143 164.85 118.93 96.62 44.32
524,287 144.97 79.87 94.24 44.97
1,048,575 136.97 62.42 96.77 43.22
Table 5-6. Statistics of hash tables created by example code
b Load factorα
Min length of
linked list
Max length of
linked list Number Unique
4,095 54.04 27 82 0
8,191 27.5 9 46 0
16,383 15 2 28 0
32,767 9.5 0 19 349
65,535 6.5 0 13 8,190
131,071 5 0 10 41,858
262,143 3.5 0 7 94,319
524,287 3.5 0 7 142,530
1,048,575 2.5 0 5 173,912
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use