Hash functions, buckets and collisions

How it works and why

For non-negative integers, a tiny teaching rule is bucket = id % bucketCount. For values 1, 6, 11, 14, 19, 21, 27, 34 and five buckets, bucket 1 contains 1,6,11,21; bucket 4 contains 14,19,34; bucket 2 contains 27; buckets 0 and 3 are empty. The collisions are expected, not errors.

A hash code is not a unique ID. Two different keys can have equal hash codes, and two different hash codes may map into the same bucket after reducing the hash to an array index. Collision resolution must compare actual keys using equality rules.

C# and C++ examples

C#

C# | Example.cs

static int BucketIndex(int id, int bucketCount)
{
    if (bucketCount <= 0) throw new ArgumentOutOfRangeException(nameof(bucketCount));
    // Maps negative IDs into 0..bucketCount-1 as well.
    return ((id % bucketCount) + bucketCount) % bucketCount;
}
Console.WriteLine(BucketIndex(19, 5)); // 4
Console.WriteLine(BucketIndex(29, 5)); // 4; not necessarily present

C++

C++ | Example.cpp

#include <iostream>
#include <stdexcept>

int bucketIndex(int id, int bucketCount) {
    if (bucketCount <= 0) throw std::invalid_argument("bucketCount");
    return (id % bucketCount + bucketCount) % bucketCount;
}
// The same bucket can contain several different keys.
std::cout << bucketIndex(19, 5) << '\n'; // 4
std::cout << bucketIndex(29, 5) << '\n'; // 4

When and why to use it

Lookup: 19 % 5 = 4; scan bucket 4 and compare each key. 29 % 5 = 4 too, but if the bucket contains no 29, the lookup fails. Deletion: find the matching key first, then remove that entry only. Pitfall: Never use hash == key as a substitute for equality.

Interactive hash table · HashSet and Dictionary