Subsections

5.3 Hash Codes

The hash tables discussed in the previous section are used to associate data with integer keys consisting of $ \ensuremath{\ensuremath{\mathit{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 $ \ensuremath{\ensuremath{\mathit{w}}}$-bit hash codes. Hash code mappings should have the following properties:

  1. If $ \ensuremath{\ensuremath{\mathit{x}}}$ and $ \ensuremath{\ensuremath{\mathit{y}}}$ are equal, then $ \ensuremath{\ensuremath{\mathit{x}}.\mathrm{hash\_code}()}$ and $ \ensuremath{\ensuremath{\mathit{y}}.\mathrm{hash\_code}()}$ are equal.

  2. If $ \ensuremath{\ensuremath{\mathit{x}}}$ and $ \ensuremath{\ensuremath{\mathit{y}}}$ are not equal, then the probability that $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}.\mathrm{hash\_code}()}}=\ensuremath{\ensuremath{\ensuremath{\mathit{y}}.\mathrm{hash\_code}()}}$ should be small (close to $ 1/2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}$).

The first property ensures that if we store $ \ensuremath{\ensuremath{\mathit{x}}}$ in a hash table and later look up a value $ \ensuremath{\ensuremath{\mathit{y}}}$ equal to $ \ensuremath{\ensuremath{\mathit{x}}}$, then we will find $ \ensuremath{\ensuremath{\mathit{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 $ \ensuremath{\ensuremath{\mathit{char}}}$, $ \ensuremath{\ensuremath{\mathit{byte}}}$, $ \ensuremath{\ensuremath{\mathit{int}}}$, and $ \ensuremath{\ensuremath{\mathit{float}}}$ are usually easy to find hash codes for. These data types always have a binary representation and this binary representation usually consists of $ \ensuremath{\ensuremath{\mathit{w}}}$ or fewer bits. In these cases, we just treat these bits as the representation of an integer in the range $ \{0,\ldots,2^\ensuremath{\ensuremath{\ensuremath{\mathit{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 $ \ensuremath{\ensuremath{\mathit{w}}}$ bits, usually $ c\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}$ bits for some constant integer $ c$. (Java's $ \ensuremath{\ensuremath{\mathit{long}}}$ and $ \ensuremath{\ensuremath{\mathit{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 5.7-5.9). However, if one is willing to do arithmetic with $ 2\ensuremath{\ensuremath{\ensuremath{\mathit{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 $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_{r-1}$. Then we can choose mutually independent random $ \ensuremath{\ensuremath{\mathit{w}}}$-bit integers $ \ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}_{r-1}$ and a random $ 2\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}$-bit odd integer $ \ensuremath{\ensuremath{\mathit{z}}}$ and compute a hash code for our object with

$\displaystyle h(\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ens...
...right)
\ddiv 2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}} \enspace .
$

Note that this hash code has a final step (multiplying by $ \ensuremath{\ensuremath{\mathit{z}}}$ and dividing by $ 2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}$) that uses the multiplicative hash function from Section 5.1.1 to take the $ 2\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}$-bit intermediate result and reduce it to a $ \ensuremath{\ensuremath{\mathit{w}}}$-bit final result. Here is an example of this method applied to a simple compound object with three parts $ \ensuremath{\ensuremath{\mathit{x_0}}}$, $ \ensuremath{\ensuremath{\mathit{x_1}}}$, and $ \ensuremath{\ensuremath{\mathit{x_2}}}$:
\begin{leftbar}
\begin{flushleft}
\hspace*{1em} \ensuremath{\mathrm{hash\_code}(...
...{\mathit{w}})}) \ensuremath{\gg} \ensuremath{w}}\\
\end{flushleft}\end{leftbar}
The following theorem shows that, in addition to being straightforward to implement, this method is provably good:

Theorem 5..3   Let $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_{r-1}$ and $ \ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_{r-1}$ each be sequences of $ \ensuremath{\ensuremath{\mathit{w}}}$ bit integers in $ \{0,\ldots,2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}-1\}$ and assume $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_i \neq \ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_i$ for at least one index $ i\in\{0,\ldots,r-1\}$. Then

$\displaystyle \Pr\{ h(\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldot...
...) \}
\le 3/2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}} \enspace .
$

Proof. We will first ignore the final multiplicative hashing step and see how that step contributes later. Define:

$\displaystyle h'(\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\en...
...right)\bmod 2^{2\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}} \enspace .
$

Suppose that $ h'(\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ensuremath{\ens...
...\mathit{y}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_{r-1})$. We can rewrite this as:

$\displaystyle \ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}_i(\ensuremath{\...
...athit{y}}}}_i) \bmod 2^{2\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}} = t$ (5.4)

where

$\displaystyle t = \left(\sum_{j=0}^{i-1} \ensuremath{\ensuremath{\ensuremath{\m...
...{x}}}}_j)\right) \bmod 2^{2\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}
$

If we assume, without loss of generality that $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_i> \ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_i$, then (5.4) becomes

$\displaystyle \ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}_i(\ensuremath{\...
...thit{x}}}}_i-\ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_i) = t\enspace ,$ (5.5)

since each of $ \ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}_i$ and $ (\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_i-\ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_i)$ is at most $ 2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}-1$, so their product is at most $ 2^{2\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}-2^{\ensuremath{\ensurem...
...h{\mathit{w}}}}+1}+1 < 2^{2\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}-1$. By assumption, $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_i-\ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_i\neq 0$, so (5.5) has at most one solution in $ \ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}_i$. Therefore, since $ \ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}_i$ and $ t$ are independent ( $ \ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}_{r-1}$ are mutually independent), the probability that we select $ \ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}_i$ so that $ h'(\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ensuremath{\ens...
...\mathit{y}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_{r-1})$ is at most $ 1/2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}$.

The final step of the hash function is to apply multiplicative hashing to reduce our $ 2\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}$-bit intermediate result $ h'(\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_{r-1})$ to a $ \ensuremath{\ensuremath{\mathit{w}}}$-bit final result $ h(\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_{r-1})$. By Theorem 5.3, if $ h'(\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ensuremath{\ens...
...\mathit{y}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_{r-1})$, then $ \Pr\{h(\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ensuremath{...
...thit{y}}}}_{r-1})\} \le 2/2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}$.

To summarize,

  $\displaystyle \Pr\left\{\begin{array}{l} h(\ensuremath{\ensuremath{\ensuremath{...
...ots,\ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_{r-1})\end{array}\right\}$    
  $\displaystyle = \Pr\left\{\begin{array}{ll} \mbox{$h'(\ensuremath{\ensuremath{\...
...div 2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}$} \end{array}\right\}$    
  $\displaystyle \le 1/2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}} + 2/2...
...} = 3/2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}} \enspace . \qedhere$    

$ \qedsymbol$


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 $ \ensuremath{\ensuremath{\mathit{w}}}$-bit integer $ \ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}_i$ for each component. We could use a pseudorandom sequence to generate as many $ \ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}_i$'s as we need, but then the $ \ensuremath{\ensuremath{\ensuremath{\mathit{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 $ \ensuremath{\ensuremath{\ensuremath{\mathit{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, $ \ensuremath{\ensuremath{\mathit{p}}}$. This method is based on the following theorem, which says that polynomials over prime fields behave pretty-much like usual polynomials:

Theorem 5..4   Let $ \ensuremath{\ensuremath{\ensuremath{\mathit{p}}}}$ be a prime number, and let $ f(\ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}) = \ensuremath{\ensuremath...
...math{\mathit{x}}}}_{r-1}\ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}^{r-1}$ be a non-trivial polynomial with coefficients $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_i\in\{0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{p}}}}-1\}$. Then the equation $ f(\ensuremath{\ensuremath{\ensuremath{\mathit{z}}}})\bmod \ensuremath{\ensuremath{\ensuremath{\mathit{p}}}} = 0$ has at most $ r-1$ solutions for $ \ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}\in\{0,\ldots,p-1\}$.

To use Theorem 5.4, we hash a sequence of integers $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_{r-1}$ with each $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_i\in \{0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{p}}}}-2\}$ using a random integer $ \ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}\in\{0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{p}}}}-1\}$ via the formula

$\displaystyle h(\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ens...
...}}^r \right)\bmod \ensuremath{\ensuremath{\ensuremath{\mathit{p}}}} \enspace .
$

Note the extra $ (\ensuremath{\ensuremath{\ensuremath{\mathit{p}}}}-1)\ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}^r$ term at the end of the formula. It helps to think of $ (\ensuremath{\ensuremath{\ensuremath{\mathit{p}}}}-1)$ as the last element, $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_r$, in the sequence $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_{r}$. Note that this element differs from every other element in the sequence (each of which is in the set $ \{0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{p}}}}-2\}$). We can think of $ \ensuremath{\ensuremath{\ensuremath{\mathit{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 $ \ensuremath{\ensuremath{\mathit{z}}}$:

Theorem 5..5   Let $ \ensuremath{\ensuremath{\ensuremath{\mathit{p}}}}>2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}+1$ be a prime, let $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_{r-1}$ and $ \ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_{r-1}$ each be sequences of $ \ensuremath{\ensuremath{\mathit{w}}}$-bit integers in $ \{0,\ldots,2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}-1\}$, and assume $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_i \neq \ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_i$ for at least one index $ i\in\{0,\ldots,r-1\}$. Then

$\displaystyle \Pr\{ h(\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldot...
...
\le (r-1)/\ensuremath{\ensuremath{\ensuremath{\mathit{p}}}} \} \enspace .
$

Proof. The equation $ h(\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ensuremath{\ensu...
...\mathit{y}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_{r-1})$ can be rewritten as

$\displaystyle \left( (\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0-\ensu...
...z}}}}^{r-1} \right)\bmod \ensuremath{\ensuremath{\ensuremath{\mathit{p}}}} = 0.$ (5.6)

Since $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_\ensuremath{\ensuremath{\ens...
...ath{\ensuremath{\mathit{y}}}}_\ensuremath{\ensuremath{\ensuremath{\mathit{i}}}}$, this polynomial is non-trivial. Therefore, by Theorem 5.4, it has at most $ r-1$ solutions in $ \ensuremath{\ensuremath{\mathit{z}}}$. The probability that we pick $ \ensuremath{\ensuremath{\mathit{z}}}$ to be one of these solutions is therefore at most $ (r-1)/\ensuremath{\ensuremath{\ensuremath{\mathit{p}}}}$. $ \qedsymbol$

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

$\displaystyle \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ensur...
...-1}, \ensuremath{\ensuremath{\ensuremath{\mathit{p}}}}-1,0,0,\ldots \enspace .
$

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, (5.6) becomes

$\displaystyle \left(
\sum_{i=0}^{i=r'-1}(\ensuremath{\ensuremath{\ensuremath{\...
... \right)\bmod \ensuremath{\ensuremath{\ensuremath{\mathit{p}}}} = 0 \enspace ,
$

which, by Theorem 5.4, has at most $ r$ solutions in $ \ensuremath{\ensuremath{\ensuremath{\mathit{z}}}}$. This combined with Theorem 5.5 suffice to prove the following more general theorem:

Theorem 5..6   Let $ \ensuremath{\ensuremath{\ensuremath{\mathit{p}}}}>2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}+1$ be a prime, let $ \ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_{r-1}$ and $ \ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_0,\ldots,\ensuremath{\ensuremath{\ensuremath{\mathit{y}}}}_{r'-1}$ be distinct sequences of $ \ensuremath{\ensuremath{\mathit{w}}}$-bit integers in $ \{0,\ldots,2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}-1\}$. Then

$\displaystyle \Pr\{ h(\ensuremath{\ensuremath{\ensuremath{\mathit{x}}}}_0,\ldot...
...le \max\{r,r'\}/\ensuremath{\ensuremath{\ensuremath{\mathit{p}}}} \enspace .
$

The following example code shows how this hash function is applied to an object that contains an array, $ \ensuremath{\ensuremath{\mathit{x}}}$, of values:
\begin{leftbar}
\begin{flushleft}
\hspace*{1em} \ensuremath{\mathrm{hash\_code}(...
...\ensuremath{\ensuremath{\mathit{s}}\bmod 2^{32}}\\
\end{flushleft}\end{leftbar}

The preceding code sacrifices some collision probability for implementation convenience. In particular, it applies the multiplicative hash function from Section 5.1.1, with $ \ensuremath{\ensuremath{\ensuremath{\mathit{d}}}}=31$ to reduce $ \ensuremath{\ensuremath{\mathit{x}}[\ensuremath{\mathit{i}}].\mathrm{hash\_code}()}$ to a 31-bit value. This is so that the additions and multiplications that are done modulo the prime $ \ensuremath{\ensuremath{\ensuremath{\mathit{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

$\displaystyle 2/2^{31} + r/(2^{32}-5)
$

rather than the $ r/(2^{32}-5)$ specified in Theorem 5.6.

opendatastructures.org