Fixing LOOKUP with Hash Functions

When we first started talking about structures to support search, we thought about doing it with an array. Arrays have a lot to offer, particularly really fast random access. That makes insert (at the back) really efficient!

The problem was LOOKUP. As we saw back then, and recapped on the previous page, if the keys are in no particular order, LOOKUP is worst-case \( \Theta(n) \). We also figured out that even the expected complexity of LOOKUP is \( \Theta(n) \)! So that's bad.

We then turned to the idea of sorting the keys. That would make LOOKUP \( \Theta(\log n) \) with binary search. But the question then becomes one of keeping our list sorted. If we do that in an array, then INSERT becomes \( \Theta(n) \) in the worst case, because we have to shift all the elements over to make room for the new one.

So what we did then was abandoned the idea of arrays and developed binary-search trees, which have \( \Theta(\log n) \) INSERT and LOOKUP in the worst case if we keep the tree balanced.

Today, we're going to follow a different path, instead of abandoning arrays, we're going to abandon the idea of keeping the keys sorted.

Here's where we're at for how to store a set in an array:

• Putting the items in the array in the order they're inserted gives us \( \Theta(1) \) INSERT and \( \Theta(n) \) LOOKUP. So that order is no good.
• Putting the items in the array in sorted order gives us \( \Theta(n) \) INSERT and \( \Theta(\log n) \) LOOKUP. So that order is no good either.

We need another way. We need to somehow “just know” where in the array the items so we can avoid blindly searching through the array in LOOKUP, or putting them in one place and moving them later.

Hash Functions

Big Idea: What if we had a function that could take a key and return a number we could use to find the right place in the array for that key?

We'll call that function \( \mathrm{H} \) and our array \( \mathit{arr} \).

• If I want to insert a key, \( k \), I find the array index to store it at, \( i \), by saying \( i = \mathrm{H}(k) \), and then set the array element with \( {\mathit{arr}}[i] = k \).
• If I want to check whether a key is present, I find the array index for the location we would have put it, \( i \), by saying \( i = \mathrm{H}(k) \), and then just look in \( \mathit{arr}[i] \) to see if it's there.

Assuming computing \( \mathrm{H}(k) \) is constant time, it takes \( \Theta(1) \) time for both INSERT and LOOKUP!

Terminology

• This function is called a hash function.
• We call the array that stores the keys a hash table.
• A slot in the table is often called a bucket.
• The function's output is called a hash value.
  • We use the hash value to get an index into the table to find a bucket.

So, the most straightforward way to implement a hash table is to have an array of buckets, and a hash function use \( \mathrm{H}(k) \mod M \), where \( M \) is the number of buckets, to get an index into the array. In C++ code, it'd be something like arr[ hash(k) % array_size ].

Example

Say we have the following hash function that takes a string and returns an int:

int hash(const string& key) {
    int sum = addASCIIValues(key);  // Adds ASCII values of characters
    int hash = (sum % 13) + (sum % 7) + (sum % 5); // Jumble more
    return hash;
}

Here's a handy ASCII table. Use it to insert eggs.

Okay, now our sumOfASCIIValues function gives us 101 + 103 + 103 + 115 = 422. But our hash function then scrambles that up a bit more, giving us 422 % 13 + 422 % 7 + 422 % 5.

Okay, so the final hash value is the sum of those. So…

In summary, inside our hash function

• The sum of the ASCII values in the string eggs is 101 + 103 + 103 + 115 = 422.
• The hash value is (422 % 13) + (422 % 7) + (422 % 5) = 10.

and then to map the hash value to a bucket, we use modulo 10

• So the bucket is 10 % 10 = 0.

Now, whenever we want to check if a key is in the table, we can just figure out which bucket it belongs in and see if it's there!

If we look up something that's already in the table, it'll have the same hash value and we'll find it right there, in one step. So let's try looking up a couple of things that aren't in the table…

We can see we'd put them in buckets 5 and 9 respectively, but they're not there, so they aren't in the set. No searching through the whole array needed!

If keys mapped to buckets randomly, the chance of everything mapping to a distinct bucket would be

\[ 1 \times \frac{9}{10} \times \frac{8}{10} \times \frac{7}{10} \times \frac{6}{10} \times \frac{5}{10} \times \frac{4}{10} \times \frac{3}{10} \times \frac{2}{10} \times \frac{1}{10} = \frac{567}{1562500} \approx 0.00036288 \]

Perfect Hash Functions

A hash function that maps all the data that'll be stored in the hash table to a unique bucket is known as a perfect hash function. It's only possible if you know all the keys you'll be storing in your table in advance (so you can cook up a suitable function).

(When logged in, completion status appears here.)