Using Lemma 5.4 to prove upper-bounds on the expected running time of find(x), add(x), and remove(x) is now fairly straightforward. Consider the simplest case, where we execute find(x) for some value x that has never been stored in the LinearHashTable. In this case, \(\texttt{i}=\texttt{hash(x)}\) is a random value in \(\{0,\ldots,\texttt{t.length}-1\}\) independent of the contents of t. If i is part of a run of length \(k\), then the time it takes to execute the find(x) operation is at most \(O(1+k)\). Thus, the expected running time can be upper-bounded by \begin{equation*} O\left(1 + \left(\frac{1}{\texttt{t.length}}\right)\sum_{i=1}^{\texttt{t.length}}\sum_{k=0}^{\infty} k\Pr\{\text{\texttt{i} is part of a run of length \(k\)}\}\right) \enspace . \end{equation*} Note that each run of length \(k\) contributes to the inner sum \(k\) times for a total contribution of \(k^2\), so the above sum can be rewritten as \begin{align*} & { } O\left(1 + \left(\frac{1}{\texttt{t.length}}\right)\sum_{i=1}^{\texttt{t.length}}\sum_{k=0}^{\infty} k^2\Pr\{\mbox{\texttt{i} starts a run of length \(k\)}\}\right) \\
& \le O\left(1 + \left(\frac{1}{\texttt{t.length}}\right)\sum_{i=1}^{\texttt{t.length}}\sum_{k=0}^{\infty} k^2p_k\right) \\
& = O\left(1 + \sum_{k=0}^{\infty} k^2p_k\right) \\
& = O\left(1 + \sum_{k=0}^{\infty} k^2\cdot O(c^k)\right) \\
& = O(1) \enspace . \end{align*} The last step in this derivation comes from the fact that \(\sum_{k=0}^{\infty} k^2\cdot O(c^k)\) is an exponentially decreasing series.¹²In the terminology of many calculus texts, this sum passes the ratio test: There exists a positive integer \(k_0\) such that, for all \(k\ge k_0\), \(\frac{(k+1)^2c^{k+1}}{k^2c^k} < 1\). Therefore, we conclude that the expected running time of the find(x) operation for a value x that is not contained in a LinearHashTable is \(O(1)\).

If we ignore the cost of the resize() operation, then the above analysis gives us all we need to analyze the cost of operations on a LinearHashTable.

First of all, the analysis of find(x) given above applies to the add(x) operation when x is not contained in the table. To analyze the find(x) operation when x is contained in the table, we need only note that this is the same as the cost of the add(x) operation that previously added x to the table. Finally, the cost of a remove(x) operation is the same as the cost of a find(x) operation.

In summary, if we ignore the cost of calls to resize(), all operations on a LinearHashTable run in \(O(1)\) expected time. Accounting for the cost of resize can be done using the same type of amortized analysis performed for the ArrayStack data structure in Section 2.1.

5.2.2 Summary

The following theorem summarizes the performance of the LinearHashTable data structure:

5.2.3 Tabulation Hashing

While analyzing the LinearHashTable structure, we made a very strong assumption: That for any set of elements, \(\{\texttt{x}_1,\ldots,\texttt{x}_\texttt{n}\}\), the hash values \(\texttt{hash}(\)x\(_1),\ldots,\texttt{hash}(\texttt{x}_\texttt{n})\) are independently and uniformly distributed over the set \(\{0,\ldots,\texttt{t.length}-1\}\). One way to achieve this is to store a giant array, tab, of length \(2^{\texttt{w}}\), where each entry is a random w-bit integer, independent of all the other entries. In this way, we could implement hash(x) by extracting a d-bit integer from tab[x.hashCode()]:

    int idealHash(T x) {
        return tab[x.hashCode() >>> w-d];
    }

Unfortunately, storing an array of size \(2^{\texttt{w}}\) is prohibitive in terms of memory usage. The approach used by tabulation hashing is to, instead, treat w-bit integers as being comprised of \(\texttt{w}/\texttt{r}\) integers, each having only \(\texttt{r}\) bits. In this way, tabulation hashing only needs \(\texttt{w}/\texttt{r}\) arrays each of length \(2^{\texttt{r}}\). All the entries in these arrays are independent random w-bit integers. To obtain the value of hash(x) we split x.hashCode() up into \(\texttt{w}/\texttt{r}\) r-bit integers and use these as indices into these arrays. We then combine all these values with the bitwise exclusive-or operator to obtain hash(x). The following code shows how this works when \(\texttt{w}=32\) and \(\texttt{r}=4\):

    int hash(T x) {
        int h = x.hashCode();
        return (tab[0][h&0xff] 
                 ^ tab[1][(h>>>8)&0xff]
                 ^ tab[2][(h>>>16)&0xff] 
                 ^ tab[3][(h>>>24)&0xff])
                  >>> (w-d);
    }

One can easily verify that, for any x, hash(x) is uniformly distributed over \(\{0,\ldots,2^{\texttt{d}}-1\}\). With a little work, one can even verify that any pair of values have independent hash values. This implies tabulation hashing could be used in place of multiplicative hashing for the ChainedHashTable implementation.

However, it is not true that any set of n distinct values gives a set of n independent hash values. Nevertheless, when tabulation hashing is used, the bound of Theorem 5.2 still holds. References for this are provided at the end of this chapter.

5.3 Hash Codes

The hash tables discussed in the previous section are used to associate data with integer keys consisting of w bits. In many cases, we have keys that are not integers. They may be strings, objects, arrays, or other compound structures. To use hash tables for these types of data, we must map these data types to w-bit hash codes. Hash code mappings should have the following properties:

1. If x and y are equal, then x.hashCode() and y.hashCode() are equal.

2. If x and y are not equal, then the probability that \(\texttt{x.hashCode()}=\texttt{y.hashCode()}\) should be small (close to \(1/2^{\texttt{w}}\)).

The first property ensures that if we store x in a hash table and later look up a value y equal to x, then we will find x—as we should. The second property minimizes the loss from converting our objects to integers. It ensures that unequal objects usually have different hash codes and so are likely to be stored at different locations in our hash table.

5.3.1 Hash Codes for Primitive Data Types

Small primitive data types like char, byte, int, and float are usually easy to find hash codes for. These data types always have a binary representation and this binary representation usually consists of w or fewer bits. (For example, in Java, byte is an 8-bit type and float is a 32-bit type.) In these cases, we just treat these bits as the representation of an integer in the range \(\{0,\ldots,2^\texttt{w}-1\}\). If two values are different, they get different hash codes. If they are the same, they get the same hash code.

A few primitive data types are made up of more than w bits, usually \(c\texttt{w}\) bits for some constant integer \(c\). (Java's long and double types are examples of this with \(c=2\).) These data types can be treated as compound objects made of \(c\) parts, as described in the next section.

5.3.2 Hash Codes for Compound Objects

For a compound object, we want to create a hash code by combining the individual hash codes of the object's constituent parts. This is not as easy as it sounds. Although one can find many hacks for this (for example, combining the hash codes with bitwise exclusive-or operations), many of these hacks turn out to be easy to foil (see Exercises Exercise 5.7–Exercise 5.9). However, if one is willing to do arithmetic with \(2\texttt{w}\) bits of precision, then there are simple and robust methods available. Suppose we have an object made up of several parts \(P_0,\ldots,P_{r-1}\) whose hash codes are \(\texttt{x}_0,\ldots,\texttt{x}_{r-1}\). Then we can choose mutually independent random w-bit integers \(\texttt{z}_0,\ldots,\texttt{z}_{r-1}\) and a random \(2\texttt{w}\)-bit odd integer z and compute a hash code for our object with \begin{equation*} h(\texttt{x}_0,\ldots,\texttt{x}_{r-1}) = \left(\left(\texttt{z}\sum_{i=0}^{r-1} \texttt{z}_i \texttt{x}_i\right)\bmod 2^{2\texttt{w}}\right) \ddiv 2^{\texttt{w}} \enspace . \end{equation*} Note that this hash code has a final step (multiplying by z and dividing by \(2^{\texttt{w}}\)) that uses the multiplicative hash function from Section 5.1.1 to take the \(2\texttt{w}\)-bit intermediate result and reduce it to a w-bit final result. Here is an example of this method applied to a simple compound object with three parts x0, x1, and x2:

// ERROR: junk/Point3D.x0 not found
    int hashCode() {
        // random numbers from rand.org
        long[] z = {0x2058cc50L, 0xcb19137eL, 0x2cb6b6fdL}; 
        long zz = 0xbea0107e5067d19dL;

        // convert (unsigned) hashcodes to long
        long h0 = x0.hashCode() & ((1L<<32)-1);
        long h1 = x1.hashCode() & ((1L<<32)-1);
        long h2 = x2.hashCode() & ((1L<<32)-1);
        
        return (int)(((z[0]*h0 + z[1]*h1 + z[2]*h2)*zz)
                     >>> 32);
    }

5.3.3 Hash Codes for Arrays and Strings

The method from the previous section works well for objects that have a fixed, constant, number of components. However, it breaks down when we want to use it with objects that have a variable number of components, since it requires a random w-bit integer \(\texttt{z}_i\) for each component. We could use a pseudorandom sequence to generate as many \(\texttt{z}_i\)'s as we need, but then the \(\texttt{z}_i\)'s are not mutually independent, and it becomes difficult to prove that the pseudorandom numbers don't interact badly with the hash function we are using. In particular, the values of \(t\) and \(\texttt{z}_i\) in the proof of Theorem 5.3 are no longer independent.

A more rigorous approach is to base our hash codes on polynomials over prime fields; these are just regular polynomials that are evaluated modulo some prime number, p. This method is based on the following theorem, which says that polynomials over prime fields behave pretty-much like usual polynomials:

To use Theorem 5.4, we hash a sequence of integers \(\texttt{x}_0,\ldots,\texttt{x}_{r-1}\) with each \(\texttt{x}_i\in \{0,\ldots,\texttt{p}-2\}\) using a random integer \(\texttt{z}\in\{0,\ldots,\texttt{p}-1\}\) via the formula \begin{equation*} h(\texttt{x}_0,\ldots,\texttt{x}_{r-1}) = \left(\texttt{x}_0\texttt{z}^0+\cdots+\texttt{x}_{r-1}\texttt{z}^{r-1}+(\texttt{p}-1)\texttt{z}^r \right)\bmod \texttt{p} \enspace . \end{equation*}

Note the extra \((\texttt{p}-1)\texttt{z}^r\) term at the end of the formula. It helps to think of \((\texttt{p}-1)\) as the last element, \(\texttt{x}_r\), in the sequence \(\texttt{x}_0,\ldots,\texttt{x}_{r}\). Note that this element differs from every other element in the sequence (each of which is in the set \(\{0,\ldots,\texttt{p}-2\}\)). We can think of \(\texttt{p}-1\) as an end-of-sequence marker.

The following theorem, which considers the case of two sequences of the same length, shows that this hash function gives a good return for the small amount of randomization needed to choose z:

Note that this hash function also deals with the case in which two sequences have different lengths, even when one of the sequences is a prefix of the other. This is because this function effectively hashes the infinite sequence \begin{equation*} \texttt{x}_0,\ldots,\texttt{x}_{r-1}, \texttt{p}-1,0,0,\ldots \enspace . \end{equation*} This guarantees that if we have two sequences of length \(r\) and \(r'\) with \(r > r'\), then these two sequences differ at index \(i=r\). In this case, Equation 5.6 becomes \begin{equation*} \left( \sum_{i=0}^{i=r'-1}(\texttt{x}_i-\texttt{y}_i)\texttt{z}^i + (\texttt{x}_{r'} - \texttt{p} + 1)\texttt{z}^{r'} +\sum_{i=r'+1}^{i=r-1}\texttt{x}_i\texttt{z}^i + (\texttt{p}-1)\texttt{z}^{r} \right)\bmod \texttt{p} = 0 \enspace , \end{equation*} which, by Theorem 5.4, has at most \(r\) solutions in \(\texttt{z}\). This combined with Theorem 5.5 suffice to prove the following more general theorem:

The following example code shows how this hash function is applied to an object that contains an array, x, of values:

    int hashCode() {
        long p = (1L<<32)-5;   // prime: 2^32 - 5
        long z = 0x64b6055aL;  // 32 bits from random.org
        int z2 = 0x5067d19d;   // random odd 32 bit number
        long s = 0;
        long zi = 1;
        for (int i = 0; i < x.length; i++) {
            // reduce to 31 bits
            long xi = (x[i].hashCode() * z2) >>> 1; 
            s = (s + zi * xi) % p;
            zi = (zi * z) % p;    
        }
        s = (s + zi * (p-1)) % p;
        return (int)s;
    }

The preceding code sacrifices some collision probability for implementation convenience. In particular, it applies the multiplicative hash function from Section 5.1.1, with \(\texttt{d}=31\) to reduce x[i].hashCode() to a 31-bit value. This is so that the additions and multiplications that are done modulo the prime \(\texttt{p}=2^{32}-5\) can be carried out using unsigned 63-bit arithmetic. Thus the probability of two different sequences, the longer of which has length \(r\), having the same hash code is at most \begin{equation*} 2/2^{31} + r/(2^{32}-5) \end{equation*} rather than the \(r/(2^{32}-5)\) specified in Theorem 5.6.

5.4 Discussion and Exercises

Hash tables and hash codes represent an enormous and active field of research that is just touched upon in this chapter. The online Bibliography on Hashing [10] contains nearly 2000 entries.

A variety of different hash table implementations exist. The one described in Section 5.1 is known as hashing with chaining (each array entry contains a chain (List) of elements). Hashing with chaining dates back to an internal IBM memorandum authored by H. P. Luhn and dated January 1953. This memorandum also seems to be one of the earliest references to linked lists.

An alternative to hashing with chaining is that used by open addressing schemes, where all data is stored directly in an array. These schemes include the LinearHashTable structure of Section 5.2. This idea was also proposed, independently, by a group at IBM in the 1950s. Open addressing schemes must deal with the problem of collision resolution: the case where two values hash to the same array location. Different strategies exist for collision resolution; these provide different performance guarantees and often require more sophisticated hash functions than the ones described here.

Yet another category of hash table implementations are the so-called perfect hashing methods. These are methods in which find(x) operations take \(O(1)\) time in the worst-case. For static data sets, this can be accomplished by finding perfect hash functions for the data; these are functions that map each piece of data to a unique array location. For data that changes over time, perfect hashing methods include FKS two-level hash tables [31,24] and cuckoo hashing [57].

The hash functions presented in this chapter are probably among the most practical methods currently known that can be proven to work well for any set of data. Other provably good methods date back to the pioneering work of Carter and Wegman who introduced the notion of universal hashing and described several hash functions for different scenarios [14]. Tabulation hashing, described in Section 5.2.3, is due to Carter and Wegman [14], but its analysis, when applied to linear probing (and several other hash table schemes) is due to Pătraşcu and Thorup [60].

The idea of multiplicative hashing is very old and seems to be part of the hashing folklore [48]. However, the idea of choosing the multiplier z to be a random odd number, and the analysis in Section 5.1.1 is due to Dietzfelbinger et al [23]. This version of multiplicative hashing is one of the simplest, but its collision probability of \(2/2^{\texttt{d}}\) is a factor of two larger than what one could expect with a random function from \(2^{\texttt{w}}\to 2^{\texttt{d}}\). The multiply-add hashing method uses the function \begin{equation*} h(\texttt{x}) = ((\texttt{z}\texttt{x} + b) \bmod 2^{\texttt{2w}}) \ddiv 2^{\texttt{2w}-\texttt{d}} \end{equation*} where z and b are each randomly chosen from \(\{0,\ldots,2^{\texttt{2w}}-1\}\). Multiply-add hashing has a collision probability of only \(1/2^{\texttt{d}}\) [21], but requires \(2\texttt{w}\)-bit precision arithmetic.

There are a number of methods of obtaining hash codes from fixed-length sequences of w-bit integers. One particularly fast method [11] is the function \begin{equation*}\begin{array} h(\texttt{x}_0,\ldots,\texttt{x}_{r-1}) \\
\quad = \left(\sum_{i=0}^{r/2-1} ((\texttt{x}_{2i}+\texttt{a}_{2i})\bmod 2^{\texttt{w}})((\texttt{x}_{2i+1}+\texttt{a}_{2i+1})\bmod 2^{\texttt{w}})\right) \bmod 2^{2\texttt{w}} \end{array} \end{equation*} where \(r\) is even and \(\texttt{a}_0,\ldots,\texttt{a}_{r-1}\) are randomly chosen from \(\{0,\ldots,2^{\texttt{w}}\}\). This yields a \(2\texttt{w}\)-bit hash code that has collision probability \(1/2^{\texttt{w}}\). This can be reduced to a w-bit hash code using multiplicative (or multiply-add) hashing. This method is fast because it requires only \(r/2\) \(2\texttt{w}\)-bit multiplications whereas the method described in Section 5.3.2 requires \(r\) multiplications. (The \(\bmod\) operations occur implicitly by using w and \(2\texttt{w}\)-bit arithmetic for the additions and multiplications, respectively.)

The method from Section 5.3.3 of using polynomials over prime fields to hash variable-length arrays and strings is due to Dietzfelbinger et al [22]. Due to its use of the \(\bmod\) operator which relies on a costly machine instruction, it is, unfortunately, not very fast. Some variants of this method choose the prime p to be one of the form \(2^{\texttt{w}}-1\), in which case the \(\bmod\) operator can be replaced with addition (+) and bitwise-and (\&) operations [47]. Another option is to apply one of the fast methods for fixed-length strings to blocks of length \(c\) for some constant \(c>1\) and then apply the prime field method to the resulting sequence of \(\lceil r/c\rceil\) hash codes.

    boolean addSlow(T x) {
        if (2*(q+1) > t.length) resize(); // max 50% occupancy
        int i = hash(x);
        while (t[i] != null) {
            if (t[i] != del && x.equals(t[i])) return false;
            i = (i == t.length-1) ? 0 : i + 1; // increment i
        }
        t[i] = x;
        n++; q++;
        return true;
    }