Grokking Algorithms

Chapter 5
 
 
I
 
 
Hash tables
Now you need to re-insert all of those items into this new hash table 
using the
 
hash
function:
This new table has a load factor of 
3
/
8
. Much better! With a lower load 
factor, you’ll have fewer collisions, and your table will perform better. A 
good rule of thumb is, resize when your load factor is greater than 0.7.
You might be thinking, “This resizing business takes a lot of time!” And 
you’re right. Resizing is expensive, and you don’t want to resize too 
often. But averaged out, hash tables take O(1) even with resizing.
A good hash function
A good hash function distributes values in the array evenly.
A bad hash function groups values together and produces a lot of 
collisions.
What is a good hash function? That’s something you’ll never have to 
worry about—old men (and women) with big beards sit in dark rooms 
and worry about that. If you’re really curious, look up the SHA function 
(there’s a short description of it in the last chapter). You could use that 
as your hash function.

---

93
Recap
EXERCISES
It’s important for hash functions to have a good distribution. They 
should map items as broadly as possible. The worst case is a hash 
function that maps all items to the same slot in the hash table.
Suppose you have these four hash functions that work with strings:
a. Return “1” for all input.
b. Use the length of the string as the index.
c. Use the first character of the string as the index. So, all strings 
starting with 
a
are hashed together, and so on.
d. Map every letter to a prime number: a = 2, b = 3, c = 5, d = 7,
e = 11, and so on. For a string, the hash function is the sum of all
the characters modulo the size of the hash. For example, if your
hash size is 10, and the string is “bag”, the index is 3 + 2 + 17 %
10 = 22 % 10 = 2.
For each of these examples, which hash functions would provide a good 
distribution? Assume a hash table size of 10 slots.