Associative Containers and Hash Functions

An associative container that uses hashing has to decide where each element goes. It makes that decision with a hash function, which takes an element and produces a hash value. The container then uses that value to choose a place to store the element. When you use a container from the standard library, the container supplies its own machinery for storing and finding elements, but the function that maps your elements to hash values is still a decision you make. That decision is the subject of this article.

The source material gives three guiding ideas. The first is to test the hash function you choose rather than assume it works. The second is to combine standard hash functions with exclusive or when an element has several parts that all matter for its identity. The third is to prefer standard-library containers to structures you build by hand. Keep one question in mind as you read: given an element, what does its hash value look like, and how is that value produced? The sections below follow a value through a combined hash function and then through a test run, so you can see what each step contributes.

Think of the container as a table of slots, which this article calls buckets. The hash function looks at an element and produces a hash value, and that value determines which bucket the element lands in. Two different elements can in principle end up in the same bucket. The diagram below traces three elements through this process so you can see where each one ends up. The hash values shown are illustrative numbers chosen for this explanation, not values taken from the source.

Read the diagram from the elements downward. Element A and Element C both map to bucket 1, so they share a bucket, while Element B has its own bucket 0 and bucket 2 and bucket 3 remain free. The point is not the particular arithmetic that produced these buckets, which the source does not specify. The point is that the hash function alone decides the bucket, which means a hash function that spreads values unevenly will crowd elements into a few buckets and leave others almost empty. That is exactly why the quality of the hash function matters.

Suppose an element has two parts that both matter for its identity. The source describes one approach: hash each part with a standard hash function, then combine the two results using exclusive or. Each standard hash function handles only one piece of the data, and the combining step is a small, well-defined operation. Nothing in this flow requires you to invent a new mixing scheme from scratch. The source says that hash functions built this way are often good, but it does not explain the operation in depth, so the rest of this section works through a small numeric case.

Read the diagram from top to bottom. The two parts enter separately, each passes through its own standard hash function, and the two results meet at the exclusive or step, which yields one combined value. The combining step is where the two halves of the element's identity are merged into a single number that the container can use for placement.

Exclusive or compares two bit patterns position by position. For each bit position, the result bit is 1 when the two input bits differ and 0 when they match. Working through a case shows the effect directly. The two values used here are illustrative numbers chosen for this explanation, not values from the source.

The first guidance in the source is to experiment to check that you have an acceptable hash function. Writing a hash function is not enough. You need evidence that it behaves acceptably for the data you actually store. The flowchart below shows the stages of a simple test run, from choosing sample keys to deciding whether the candidate is acceptable.

The decision point is the judgment at the diamond. Keeping a function is a conclusion drawn from evidence, and a function that fails the test goes back for revision rather than being shipped. When the function combines standard hash functions with exclusive or, the test must cover the combined result as well as its parts, because the combining step is part of the function you will actually use.

The third guidance in the source is to know your standard-library containers and prefer them to hand-crafted data structures. The idea is to start from what the standard library already provides instead of building a new structure whenever you need one. The source gives the reason only implicitly. A hand-crafted structure requires its author to get every detail right, including the hashing behavior discussed earlier. A standard-library container moves that responsibility onto a component that is already part of the language, so your effort goes into choosing it well and using it correctly.