Lecture 8 - Notes

January 28, 2016

Hashing

definition: With hashing we save items in a key-indexed table (where the index is a function of the key). A hash function is used for computing the array index from the key.

Horner's Rule

To hash a string we use,

$$\begin{align} h = s[0] \cdot 31^{L–1} + \ldots + s[L – 3] \cdot 31^2 + s[L – 2] \cdot 31^1 + s[L – 1] \cdot 31^0 \end{align}$$

for example,

public final class String
{
    private final char[] s;
    ...
    public int hashCode()
    {
        int hash = 0;
        for (int i = 0; i < length(); i++)
            hash = s[i] + (31 * hash);
        return hash;
    }
}