Hash Functions and Unordered Maps

Usually the hash function you already have is enough.

Programming

Predicting an Exclusive Or Result

An unordered map needs a way to turn each key into a hash value. Usually the hash function you already have is enough. Sometimes it is not: the key type may be your own, or you may want a new hash that is derived from parts of the key that already have hash functions. This article studies one approach the source describes for that situation, which is to build a new hash function by combining existing hash functions. The source calls this approach simple and often very effective. Before we look at hashes at all, try a plain integer operation, because the combining step is built on it.

What do you think happens?

In C++, what does the expression 5 ^ 3 evaluate to? Make a guess before you read the answer.

Reveal answer

Answer:

The caret ^ is the exclusive or operator. It gives 1 in each bit position where the two operands differ. In binary, 5 is 101 and 3 is 011. The bits differ in the first and second positions, so the result is 110, which is 6.

Building a Hash From Existing Hashes

Suppose you have two existing hash functions, h_1 and h_2, and a key k. Each function looks at the same key and produces its own hash value. A combined hash takes those two outputs and merges them into one new value using exclusive or. The final result therefore depends on both outputs, and you do not have to design a hashing scheme from scratch.

Formula

Here the symbol $\oplus$ stands for exclusive or. The combined value is the new hash for the key, and it is the value that the unordered map would use to decide where the key-value pair goes.

What happens to a key when it passes through two existing hash functions and their results are combined into one new hash value?

How Exclusive Or Combines Bits

The source names exclusive or, written with the caret, as the tool for combining hash values. In C++ the operator is written as ^. The mechanism is easiest to see at the bit level. Exclusive or compares two bits in the same position and gives 1 only when they differ. When the bits match, the result bit is 0.

How does ^ combine two hash values bit by bit, so that each output bit depends on whether the corresponding input bits match or differ?

cpp

#include <iostream>

int main() {
    int h1 = 5;
    int h2 = 3;
    std::cout << (h1 ^ h2) << std::endl;
    return 0;
}

#include <iostream>

int main() {
    int h1 = 5;
    int h2 = 3;
    std::cout << (h1 ^ h2) << std::endl;
    return 0;
}

Output

Notes on the code

h1 and h2 stand in for two hash results. Integers keep the output fixed so you can check it by hand.
The ^ operator performs exclusive or on the two integers, bit by bit.
5 is 101 and 3 is 011 in binary. They differ in two positions, so the result is 110, which prints as 6.

Formula, step by step

1
Write 5 in binary as 101.
2
Write 3 in binary as 011.
3
Compare bit by bit: position 1 gives 1 and 0 (differ, result 1), position 2 gives 0 and 1 (differ, result 1), position 3 gives 1 and 1 (match, result 0).
4
The result is 110 in binary, which is 6 in decimal.

Tracing a Combined Hash Through Two Cases

Now apply the operation to a combined hash. Consider a combined hash built as h(a) XOR h(b), where a and b are two pieces of a key. Trace what happens to the result when the two pieces hash to different values, and then when they hash to the same value.

Worked example

Combining the hashes of two key pieces

A key has two pieces, a and b. Suppose h(a) = 5 and h(b) = 3. Then suppose h(a) = 5 and h(b) = 5. Find the combined hash in each case.

1
Case 1: different values
Compute h(a) XOR h(b) = 5 XOR 3. From the earlier code, this is 6.
2
Case 2: identical values
Compute h(a) XOR h(b) = 5 XOR 5. Every bit of 5 matches itself, so every result bit is 0, and the combined hash is 0.
3
Compare the outcomes
The two pieces produced different combined hashes in Case 1 and an identical combined hash of 0 in Case 2, even though both keys have the same two pieces in structure.

Result

The combined hash is 6 when the piece hashes differ and 0 when they are identical.

Where the Combination Breaks Down

The source says combining hash functions is often very effective, and the word often is doing real work. Two properties of exclusive or explain where the approach can fail.

The first property is that exclusive or is commutative: $x \oplus y = y \oplus x$. Combining the same two hash values in either order gives the same result. So a pair of pieces (a, b) and the pair (b, a) produce identical combined hashes. A map cannot tell those two keys apart by their hash values alone.

The second property is that any value exclusive ored with itself is 0: $x \oplus x = 0$. If both pieces of a key have the same hash value, the combined hash is always 0, no matter what the key contains. A map that uses this combination would place every such key in the same bucket.

Why does combining two hashes with ^ give a poor result when both inputs are equal, or when the order of the inputs is swapped, and how do the good and bad cases differ?

Mistakes When Combining Hashes

Common mistake
Assuming the combined hash preserves the order of the key's parts
What it looks like
h(a) ^ h(b) and h(b) ^ h(a) are both 6 when h(a) is 5 and h(b) is 3.
Why it fails
Exclusive or is commutative, so swapping the two inputs does not change the result.
Do this instead
If order matters for equality, combine the parts in a way that is not symmetric, or test whether swapped keys collide.
Common mistake
Expecting distinct keys to always get distinct combined hashes
What it looks like
Two pieces with equal hash values always produce a combined hash of 0.
Why it fails
Any value exclusive ored with itself is 0, so equal pieces cancel out completely.
Do this instead
Check realistic keys for repeated or matching parts, and test the combined hash on them before relying on it.
Common mistake
Treating the source's often very effective as a guarantee rather than a hedged claim

Evaluating a Combined Hash

EASY

A key has two pieces, a and b, with h(a) = 9 and h(b) = 9. Predict the combined hash h(a) XOR h(b) before you check. Then explain whether this key would be a good or poor case for the combination, and say what you would test before using it.

Hints

Recall that any value exclusive ored with itself is 0.
Ask whether the two pieces are distinguishable by the combined value alone.

Your attempt (not saved)

MEDIUM

Show that h(a) XOR h(b) equals h(b) XOR h(a) by computing both for h(a) = 12 and h(b) = 10. Then state whether a map using this combination could tell apart the key (a, b) from the key (b, a).