1.5 Universal hashing

We end this chapter with an application of number theory to the design of hash functions. Hashing is a very useful method of storing data items in a table so as to support insertions, deletions, and lookups.

Suppose, for instance, that we need to maintain an ever-changing list of about 250 IP (Internet protocol) addresses, perhaps the addresses of the currently active customers of a Web service. (Recall that an IP address consists of 32 bits encoding the location of a computer on the Internet, usually shown broken down into four 8-bit fields, for example, 128.32.168.80.) We could obtain fast lookup times if we maintained the records in an array indexed by IP address. But this would be very wasteful of memory: the array would have $2 ^ { 3 2 } \approx 4 \times 1 0 ^ { 9 }$ entries, the vast majority of them blank. Or alternatively, we could use a linked list of just the 250 records. But then accessing records would be very slow, taking time proportional to 250, the total number of customers. Is there a way to get the best of both worlds, to use an amount of memory that is proportional to the number of customers and yet also achieve fast lookup times? This is exactly where hashing comes in.

1.5.1 Hash tables

Here’s a high-level view of hashing. We will give a short “nickname” to each of the 232 possible IP addresses. You can think of this short name as just a number between 1 and 250 (we will later adjust this range very slightly). Thus many IP addresses will inevitably have the same nickname; however, we hope that most of the 250 IP addresses of our particular customers are assigned distinct names, and we will store their records in an array of size 250 indexed by these names. What if there is more than one record associated with the same name? Easy: each entry of the array points to a linked list containing all records with that name. So the total amount of storage is proportional to 250, the number of customers, and is independent of the total number of possible IP addresses. Moreover, if not too many customer IP addresses are assigned the same name, lookup is fast, because the average size of the linked list we have to scan through is small.

But how do we assign a short name to each IP address? This is the role of a hash function: in our example, a function h that maps IP addresses to positions in a table of length about 250 (the expected number of data items). The name assigned to an IP address x is thus h( $x$ ), and the record for x is stored in position h( $x$ ) of the table. As described before, each position of the table is in fact a bucket, a linked list that contains all current IP addresses that map to it. Hopefully, there will be very few buckets that contain more than a handful of IP addresses.

Space of all $2 ^ { 3 2 }$ IP addresses

1.5.2 Families of hash functions

Designing hash functions is tricky. A hash function must in some sense be “random” (so that it scatters data items around), but it should also be a function and therefore “consistent” (so that we get the same result every time we apply it). And the statistics of the data items may work against us. In our example, one possible hash function would map an IP address to the 8-bit number that is its last segment: $h ( 1 2 8 . 3 2 . 1 6 8 . 8 0 ) = 8 0$ . A table of $n = 2 5 6$ buckets would then be required. But is this a good hash function? Not if, for example, the last segment of an IP address tends to be a small (single- or double-digit) number; then low-numbered buckets would be crowded. Taking the first segment of the IP address also invites disaster— for example, if most of our customers come from Asia.

There is nothing inherently wrong with these two functions. If our 250 IP addresses were uniformly drawn from among all $N = 2 ^ { 3 2 }$ possibilities, then these functions would behave well. The problem is we have no guarantee that the distribution of IP addresses is uniform.

Conversely, there is no single hash function, no matter how sophisticated, that behaves well on all sets of data. Since a hash function maps $2 ^ { 3 2 }$ IP addresses to just 250 names, there must be a collection of at least $2 ^ { 3 2 } / 2 5 0 \approx 2 ^ { 2 4 } \approx 1 6 { , } 0 0 0 { , } 0 0 0$ IP addresses that are assigned the same name (or, in hashing terminology, “collide”). If many of these show up in our customer set, we’re in trouble.

Obviously, we need some kind of randomization. Here’s an idea: let us pick a hash function at random from some class of functions. We will then show that, no matter what set of 250 IP addresses we actually care about, most choices of the hash function will give very few collisions among these addresses.

To this end, we need to define a class of hash functions from which we can pick at random; and this is where we turn to number theory. Let us take the number of buckets to be not 250 but $n = 2 5 7 { - } a$ prime number! And we consider every IP address x as a quadruple $x =$ $( x _ { 1 } , \ldots , x _ { 4 } )$ of integers modulo n—recall that it is in fact a quadruple of integers between 0 and 255, so there is no harm in this. We can define a function h from IP addresses to a number mod n as follows: fix any four numbers mod $n = 2 5 7$ , say 87, 23, 125, and 4. Now map the IP address $( x _ { 1 } , . . . , x _ { 4 } )$ to $h ( x _ { 1 } , . . . , x _ { 4 } ) = ( 8 7 x _ { 1 } + 2 3 x _ { 2 } + 1 2 5 x _ { 3 } + 4 x _ { 4 } )$ mod 257. Indeed, any four numbers mod n define a hash function.

For any four coefficients $a _ { 1 } , \dots , a _ { 4 } \in \{ 0 , 1 , \dots , n - 1 \}$ , write $a = ( a _ { 1 } , a _ { 2 } , a _ { 3 } , a _ { 4 } )$ and define $h _ { a }$ to be the following hash function:

h _ {a} (x _ {1}, \dots , x _ {4}) = \sum_ {i = 1} ^ {4} a _ {i} \cdot x _ {i} \bmod n.

We will show that if we pick these coefficients a at random, then $h _ { a }$ is very likely to be good in the following sense.

Property

Consider any pair of distinct IP addresses $x = ( x _ { 1 } , \ldots , x _ { 4 } )$ and $y = ( y _ { 1 } , \dotsc , y _ { 4 } )$ . If the coefficients $a = ( a _ { 1 } , a _ { 2 } , a _ { 3 } , a _ { 4 } )$ are chosen uniformly at random from $\{ 0 , 1 , \ldots , n - 1 \}$ , then

\operatorname * {P r} \left\{h _ {a} (x _ {1}, \ldots , x _ {4}) = h _ {a} (y _ {1}, \ldots , y _ {4}) \right\} = \frac {1}{n}.

In other words, the chance that x and $y$ collide under $h _ { a }$ is the same as it would be if each were assigned nicknames randomly and independently. This condition guarantees that the expected lookup time for any item is small. Here’s why. If we wish to look up x in our hash table, the time required is dominated by the size of its bucket, that is, the number of items that are assigned the same name as x. But there are only 250 items in the hash table, and the probability that any one item gets the same name as x is $1 / n = 1 / 2 5 7$ . Therefore the expected number of items that are assigned the same name as x by a randomly chosen hash function $h _ { a }$ is $2 5 0 / 2 5 7 \approx 1$ , which means the expected size of $x _ { \mathbf { s } }$ bucket is less than 2.¹

Let us now prove the preceding property.

Proof

Since $\boldsymbol { x } = ( x _ { 1 } , \dots , x _ { 4 } )$ and $y = ( y _ { 1 } , \dotsc , y _ { 4 } )$ are distinct, these quadruples must differ in some component; without loss of generality let us assume that $x _ { 4 } \neq y _ { 4 }$ . We wish to compute the probability $\mathbf { P r } [ h _ { a } ( x _ { 1 } , \ldots , x _ { 4 } ) = h _ { a } ( y _ { 1 } , \ldots , y _ { 4 } ) ]$ , that is, the probability that $\textstyle \sum _ { i = 1 } ^ { 4 } a _ { i } \cdot x _ { i } \equiv$ $\textstyle \sum _ { i = 1 } ^ { 4 } a _ { i } \cdot y _ { i }$ mod $n .$ . This last equation can be rewritten as

\sum_ {i = 1} ^ {3} a _ {i} \cdot (x _ {i} - y _ {i}) \equiv a _ {4} \cdot (y _ {4} - x _ {4}) \bmod n\tag{1}

Suppose that we draw a random hash function $h _ { a }$ by picking $a = ( a _ { 1 } , a _ { 2 } , a _ { 3 } , a _ { 4 } )$ at random. We start by drawing $a _ { 1 } , a _ { 2 }$ , and $a _ { 3 } ,$ , and then we pause and think: What is the probability that the last drawn number $a _ { 4 }$ is such that equation (1) holds? So far the left-hand side of equation (1) evaluates to some number, call it $c .$ And since $n$ is prime and $x _ { 4 } \neq y _ { 4 } , ( y _ { 4 } - x _ { 4 } )$ has a unique inverse modulo $n$ . Thus for equation (1) to hold, the last number $a _ { 4 }$ must be precisely $c \cdot \left( y _ { 4 } - x _ { 4 } \right)$ −¹ mod $n ,$ , out of its n possible values. The probability of this happening is $1 / n _ { ; }$ , and the proof is complete.

Let us step back and see what we just achieved. Since we have no control over the set of data items, we decided instead to select a hash function h uniformly at random from among a family $\mathcal { H }$ of hash functions. In our example,

\mathcal {H} = \{h _ {a}: a \in \{0, \dots , n - 1 \} ^ {4} \}.

To draw a hash function uniformly at random from this family, we just draw four numbers $a _ { 1 } , \ldots , a _ { 4 }$ modulo $n$ . (Incidentally, notice that the two simple hash functions we considered earlier, namely, taking the last or the first 8-bit segment, belong to this class. They are $h _ { ( 0 , 0 , 0 , 1 ) }$ and $h _ { ( 1 , 0 , 0 , 0 ) }$ , respectively.) And we insisted that the family have the following property:

For any two distinct data items $x$ and $y ,$ exactly $| \mathcal { H } | / n$ of all the hash functions in map x and $y$ to the same bucket, where n is the number of buckets.

A family of hash functions with this property is called universal. In other words, for any two data items, the probability these items collide is $1 / n$ if the hash function is randomly drawn from a universal family. This is also the collision probability if we map x and $y$ to buckets uniformly at random—in some sense the gold standard of hashing. We then showed that this property implies that hash table operations have good performance in expectation.

This idea, motivated as it was by the hypothetical IP address application, can of course be applied more generally. Start by choosing the table size $n$ to be some prime number that is a little larger than the number of items expected in the table (there is usually a prime number close to any number we start with; actually, to ensure that hash table operations have good performance, it is better to have the size of the hash table be about twice as large as the number of items). Next assume that the size of the domain of all data items is $N = n ^ { k }$ , a power of n (if we need to overestimate the true number of data items, so be it). Then each data item can be considered as a k-tuple of integers modulo $n ,$ and ${ \mathcal { H } } = \{ h _ { a } : a \in \{ 0 , \ldots , n - 1 \} ^ { k } \}$ is a universal family of hash functions.