Hash functions

A hash function turns a word into a bucket number. Watch sixteen words go into sixteen buckets. Then switch to the letter sum, and watch the words that look alike pile up.

⋯7uint32_t fnv1a(const char *s)8{9    uint32_t h = 2166136261u;10    for (size_t i = 0; s[i] != '\0'; i++) {11        h ^= (unsigned char)s[i];12        h *= 16777619u;13    }14    return h;15}16 17unsigned letter_sum(const char *s)18{19    unsigned sum = 0;20    for (size_t i = 0; s[i] != '\0'; i++)21        sum += (unsigned char)s[i];22    return sum;23}24 25int main(void)26{27    const char *words[WORDS] = { "listen", "silent", "enlist", "tinsel", "stone", "notes", "onset", "tones",28        "cat", "act", "dog", "god", "signal", "aligns", "phase", "shape" };29    int by_sum[M] = { 0 }, by_fnv[M] = { 0 };30    for (int i = 0; i < WORDS; i++) {31        unsigned a = letter_sum(words[i]) % M;32        unsigned b = fnv1a(words[i]) % M;33        by_sum[a]++;34        by_fnv[b]++;35        printf("%-7s sum %2u  fnv %2u\n", words[i], a, b);36    }37    int used_sum = 0, used_fnv = 0;38    for (int k = 0; k < M; k++) {39        used_sum += by_sum[k] > 0;40        used_fnv += by_fnv[k] > 0;41    }42    printf("buckets used: sum %d, fnv %d\n", used_sum, used_fnv);43    return 0;44}

From a key to an index

A hash table keeps its items in an array of m buckets, and finds an item by computing which bucket it belongs in. The hash function does that computing: it turns a key into a number, and % m turns the number into an index from 0 to m − 1.

For an integer key, k % m is often enough. For a string, every character must count, so that changing any one of them changes the result. A good hash function has three properties:

• Deterministic: the same key always gives the same bucket.
• Fast: a few operations per byte.
• Spreading: similar keys end up far apart, so the buckets fill evenly.

The code and its cost

uint32_t fnv1a(const char *s)
{
    uint32_t h = 2166136261u;
    for (size_t i = 0; s[i] != '\0'; i++) {
        h ^= (unsigned char)s[i];
        h *= 16777619u;
    }
    return h;
}

unsigned letter_sum(const char *s)
{
    unsigned sum = 0;
    for (size_t i = 0; s[i] != '\0'; i++)
        sum += (unsigned char)s[i];
    return sum;
}

FNV-1a starts from a fixed number, the offset basis 2166136261. For each byte it XORs the byte into h, then multiplies h by a fixed prime, 16777619. A uint32_t keeps only the low 32 bits of each product, so the arithmetic wraps modulo 2³². The order of the bytes matters, but the multiplication carries a bit’s effect only into the same bit and the ones above it, never down: the low 4 bits of h, which pick one of 16 buckets, depend only on the low 4 bits of each byte. That is why a table either mixes the high bits down first, as with h ^ (h >> 16), or uses a prime number of buckets, where h % m depends on every bit. For “listen”, fnv1a returns 993,752,742, and 993,752,742 % 16 = 6.

The cast to unsigned char matters: a char above 127 may be negative, and it should count as a byte from 0 to 255.

Both functions cost one pass over the string: O(length).

Why a letter sum is poor

Addition ignores order, so words made of the same letters, anagrams, always get the same sum. hashes.c hashes sixteen words both ways:

It prints buckets used: sum 6, fnv 9. The letter sum fills 6 buckets, two of them with four words each. FNV-1a sends the anagrams to different buckets.

Collisions are certain

Even FNV-1a puts two words in buckets 7, 8, 9 and 10, and four in bucket 6, while seven buckets stay empty. That is not a fault. Two keys in one bucket, a collision, cannot be avoided: with more keys than buckets it must happen, and even with fewer it is likely.

Suppose a hash sends each of n keys to one of m buckets evenly and independently. Each key misses a given bucket with probability 1 − 1/m, so the bucket stays empty with probability (1 − 1/m)ⁿ, and on average m(1 − 1/m)ⁿ buckets stay empty (Expected value). A hash table therefore needs a way to hold several keys in one bucket, or to find another bucket. The next lessons are about exactly that.

Rolling hashes

Some hashes can be updated instead of recomputed. A rolling hash of a window of text is changed in a few steps when the window slides one character: the leaving character’s share is taken out and the new one’s added. Searching a long text for a pattern then hashes each window in constant time, and compares characters only where the hashes match. The polynomial form of such a hash is evaluated by Horner’s rule.

Worked example

Sixteen keys, sixteen buckets. With a perfectly even random hash, 16 × (15/16)¹⁶ ≈ 5.7 buckets stay empty on average. FNV-1a left seven empty on the sixteen words: close to that average. A hash that gave every key its own bucket would be the rare exception.

The birthday problem. With 23 people and 365 equally likely birthdays, the chance that two of them share a birthday is 0.507: more likely than not (What probability measures). Put 23 keys in 365 buckets and a collision is already more likely than not.

Keys that share their low bits. Integer keys that are all multiples of 4, put in 16 buckets by k % 16, use only buckets 0, 4, 8 and 12. With m a power of two, % m keeps only the low bits of the key, and these keys all end in two zero bits. A prime m, or mixing the bits first, avoids it.

Two checks. Why does the letter sum send anagrams to the same bucket? (Addition ignores order.) Why convert to unsigned char before adding a byte? (So bytes above 127 are not negative.)

Where it’s used

Hash tables in every language’s library, for dictionaries, sets and caches.

Checksums and deduplication: a file’s hash finds copies without comparing whole files.

Bloom filters, which use several hashes of a key to set bits in a bit array.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, uint32_t 4, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.