CP164 Study Guide - Final Guide: Cemetery Man, Init
- Hashing
At some point it may be useful to increase the number of available slots instead of
continuing to grow the Lists attached to the slots. The decision on when to do this is based
upon a load factor. A load factor of five, for example, means that a HashSet is designed to
store no more than five times as many items as it has slots. Our example above, with seven
slots, would store no more than thirty-five items. Again, at worst, all thirty-five would be
placed in a single List in one slot. At best, each of the seven slots would have a List storing
five items each. When this load factor is exceeded, the HashSet should perform a rehash. In
a rehash, the number of available slots is increased. (The number of slots could be doubled,
for example.) Because the number of slots have changed, the indices associated with the
key hashes may change as well, so all of the items in the HashSet must have their indices
recalculated and be moved to their new slot. This can be done as many times as necessary
as the HashSet grows. (It can be done in reverse as well, with the number of slots in the
HashSet shrinking as the number of items in the HashSet decreases.)
Adding more Movie data, we see a few collisions:
Item
Movie Key
Hash
Index (%7)
A
"I Am Legend", 2007
1810314
2
B
"Dark City", 1998
1652346
3
C
"Omega Man, The", 1971
2306070
4
D
"Zulu", 1964
848448
6
E
"Last Man On Earth, The", 1964
3609832
2
F
"Dellamorte Dellamore", 1994
3952108
6
The resulting HashSet contains some empty Lists, some Lists with one item, and some Lists
with two items:
A HashSet With Lists
Note the position of the colliding items in the slot Lists. The newer items are inserted into a
slot List with the standard List insertion, i.e. the new items are added to the front of the
List.
What might be the result of a rehash on this data? Imagine that our rehash method
increases the number of slots with: slots = slots × 2 + 1. (Again, the increase in the
number of slots is arbitrary. We want the number of slots in this example to be odd at all
times.) These are our Movies with new index values:
find more resources at oneclass.com
find more resources at oneclass.com
