Hash functions part 1 – introduction

Suppose we are building a phone directory. Given a name, we want to find its phone number. We could store names and numbers in a list and check each name until we find a match. That works, but as the directory grows, so does the amount of searching.

A hash table gives us another option: use the name to calculate where to start looking. The calculation is performed by a hash function.

Hash functions also appear in file verification, caches, Bloom filters, and cryptography. Those applications have different requirements, but before choosing an algorithm, we need to understand what a hash value tells us, and what it does not.

In this first part, we will use a small phone directory and a deliberately weak hash function. Later parts will examine distribution, security, and performance.

01From an Input to a Hash Value#

A hash function maps an input to a value in an output space. For the fixed-width hashes we will focus on here, that output is often a 32-bit, 64-bit, or larger value, regardless of the input's length. We call it the hash value, or simply the hash.

We can write the operation as h(input) = hash. The input might be a name, a sequence of bytes, or the fields of an object. The important property is determinism: with the same input and the same algorithm and parameters, we get the same result.

That qualification about parameters matters. A hash function can take a seed or a key, and changing it can change the result. Determinism does not mean every application must use the same hash for the same name.

A hash is also not necessarily an identifier. If two inputs have the same hash, we cannot assume they are the same input. We will see why shortly.

02A Hash Function We Can Calculate by Hand#

For our directory, let's add up the numeric values in each name:

static uint SumCodeUnits(string value)
{
    uint hash = 0;

    foreach (char c in value)
    {
        hash = unchecked(hash + c);
    }

    return hash;
}

In C#, a char is a UTF-16 code unit. It does not always represent a complete character. Our examples use simple Latin letters, so we can calculate their sums without dealing with surrogate pairs. unchecked makes overflow wrap around within the 32-bit unsigned result, even if overflow checking is enabled elsewhere.

For the name Ada, the calculation is:

'A' = 65
'd' = 100
'a' = 97

h("Ada") = 65 + 100 + 97 = 262

This is a hash function, but it is a poor choice for a real hash table. Rearranging the same letters never changes the sum: Ada and Aad both produce 262. We are using it because every step is visible. A production hash function needs to distribute the inputs we expect much more effectively.

03From a Hash Value to a Bucket#

Our function returns a uint, but we do not want an array with over four billion entries. Let's start with just eight buckets instead. A bucket is a place where the table can store entries. To select one, we take the remainder after dividing the hash value by eight:

const uint bucketCount = 8;
uint hash = SumCodeUnits("Ada");
int bucketIndex = (int)(hash % bucketCount);

Console.WriteLine(bucketIndex); // 6

The remainder is between 0 and 7, so it is a valid array index. Here is what happens to five names:

Notice the two kinds of overlap. Bob and Dan have the same hash value: this is a hash collision. Eve and Ian have different hashes, but both land in bucket 0: this is a bucket collision. Making the array larger can separate some bucket collisions, but it cannot separate identical hash values using the same remainder operation.

The bucket index belongs to the table's layout. If we resize the table, an entry may need a new bucket even though its hash has not changed.

04A Collision Does Not Mean We Lost an Entry#

Our table must account for multiple keys reaching the same bucket. One approach is chaining: each bucket holds a collection of entries. The occupied buckets might look like this:

The table stores the original keys as well as the phone numbers. To look up Dan, we:

1. Calculate h("Dan") = 275.
2. Calculate 275 % 8 = 3.
3. Inspect the entries in bucket 3.
4. Compare the stored names with Dan.
5. Return 555-0300 when the key matches.

The hash narrows the search. The key comparison decides whether we found the right entry. Returning the first phone number in the bucket would give us Bob's number instead.

Another family of techniques, called open addressing, keeps entries in the table's array and probes other positions when a position is occupied. The details differ, but the table still needs a collision strategy and an equality check.

In application code, we can let a collection handle these details:

var directory = new Dictionary<string, string>(StringComparer.Ordinal)
{
    ["Ada"] = "555-0100",
    ["Bob"] = "555-0200",
    ["Dan"] = "555-0300",
    ["Eve"] = "555-0400",
    ["Ian"] = "555-0500"
};

if (directory.TryGetValue("Dan", out string? phone))
{
    Console.WriteLine(phone); // 555-0300
}

This dictionary uses its own hashing and storage implementation, not our sum function or our eight-bucket layout. StringComparer.Ordinal makes our intended case-sensitive string comparison explicit. Microsoft's Dictionary documentation describes the collection and its comparer support.

05Why Collisions Are Unavoidable#

A 32-bit hash has exactly 2³² possible output values. There are more than 2³² possible strings. If we map all those strings into that output space, some different strings must share an output. This follows from the pigeonhole principle: we have more inputs than places to put them.

A larger output gives us more possible values, but it does not make a fixed-width hash unique for every possible input. Even a cryptographic hash has collisions. Its security goals include making certain kinds of attack computationally infeasible, rather than making collisions mathematically impossible.

For a hash table, collisions are an expected part of operation. What matters is how often they occur for our workload and how the table handles them.

06What Makes Lookup Fast?#

If the keys are spread reasonably evenly and the table grows as we add entries, each lookup only needs to inspect a small number of candidates. Under suitable assumptions about hashing and table occupancy, this gives expected O(1) lookup with respect to the number of stored entries.

The qualification is important. If all keys land in the same bucket of a chained table, we can end up scanning that bucket's entire collection: O(n) work. The table can still return correct answers, but it loses the performance benefit we wanted.

There is also a cost before we reach the bucket. Our sum function reads every UTF-16 code unit, so hashing a name of length L takes O(L) time. Comparing strings can also depend on their length. Saying that hash-table lookup is O(1) does not mean looking up a million-character key costs the same as looking up Ada.

These are separate concerns: the cost of hashing a key, the distribution of keys among buckets, and the work required to resolve collisions. We will need to measure all of them when we get to performance.

07Equality Comes First#

Hashing and equality must agree. If two keys are considered equal, their hashes must also be equal under the comparer used by the table. The reverse is not required.

Suppose we decide that Ada and ADA should refer to the same entry. Our sum function gives them different values, so pairing it with case-insensitive equality would be a mistake. In C#, we can choose StringComparer.OrdinalIgnoreCase for the dictionary instead; the comparer supplies compatible equality and hashing behavior.

For the same reason, changing fields that participate in a key's hash or equality while that key is stored in a hash table can make lookups fail. The entry is still located according to the old key. Immutable keys make this much easier to reason about.

An in-memory hash code is not automatically a persistent fingerprint, either. .NET does not promise that a string's GetHashCode() result remains stable across processes or runtime versions. Do not save it as a durable identifier. See the String.GetHashCode documentation for the lifetime and equality guarantees.

08Different Uses, Different Requirements#

Our directory needs fast hashing, useful distribution, and a way to resolve collisions. Other applications ask different questions:

Good distribution alone does not establish cryptographic security. A hash can work well on ordinary data while being easy for an attacker to manipulate. Likewise, password storage has additional requirements and uses dedicated password-hashing constructions; our directory example does not tell us how to store passwords safely.

For now, the useful distinction is between the hash function and the application using it. The function produces a hash value. The application determines how to interpret that value, what to do about collisions, and which guarantees it needs.

In the next part, we will look at distribution and avalanche behavior, and test how much a hash function's output actually tells us about its quality.