Hash table costs

Why this matters

A hash table is one of the most used data structures in software. Python calls it a dict or a set. Java calls it a HashMap or a HashSet. C++ has unordered_map and unordered_set. Login systems, caches, spell checkers and counting code all depend on it.

Hash tables are often described as "constant time". That is true on average, and only on average. The people who build fast systems need to know when the average breaks down, and what settings keep it working. This lesson covers three things: why lookup is expected O(1) time, what happens when many keys land in the same place, and how the load factor controls the average cost.

Big-O notation is explained in the first lessons of this module. Here it only means "how the work grows as the number of keys grows". The neighbouring lessons cover best, average and worst case in general, and the hidden costs inside library calls. This lesson stays with the hash table itself.

The idea in one picture

A list stores items one after another. To find an item, you check them one by one. A hash table works differently. It has a row of numbered boxes called buckets. A hash function takes a key, such as the word "apple", and turns it into a number. That number, after a small adjustment, picks one bucket. The value is stored in that bucket.

Here is the everyday version. A coat check at a large event gives each coat a number tag. The staff have a rule: coats with tag numbers ending in 0 go on rack 0, coats ending in 1 go on rack 1, and so on. To find a coat, you read the tag, compute the rack, and look only on that rack. You do not walk the whole room. If the racks are spread evenly, each rack holds only a few coats, so the search is quick.

The rule "tag number to rack" is the hash function. The racks are the buckets. A coat on a rack is a stored entry. Two coats on the same rack are a collision. Collisions are the reason hash table costs are not always constant.

Lookup in expected O(1) time

Look up a key in a hash table with these steps:

1. Run the hash function on the key. This takes time that depends on the key's length, not on how many keys the table holds.
2. Turn the hash number into a bucket index. In most designs, this is the remainder after dividing by the number of buckets.
3. Look at the keys in that bucket. Usually there is zero or one.

Steps 1 and 2 cost the same no matter how many items are stored. Step 3 costs about the same if the bucket is short. So the total work is roughly constant. We say the cost is O(1) "expected" time, because the constant result depends on the keys being spread across buckets fairly evenly.

Here is a small table with a simple hash function written in plain Python. It is a teaching table, not the one Python uses internally, but the idea is the same. Each bucket is a list of pairs. The class counts comparisons, which means each time it checks whether a stored key equals the key it is looking for.

Demo 1: spread keys, 8 buckets, 8 keys
bucket sizes: [1, 1, 1, 1, 1, 1, 1, 1]
comparisons to find item5: 1

The simple_hash function walks through the characters of the key. For each character it multiplies the running total by 31, adds the character's code, and keeps the result below 2 to the power 32. Real hash functions are more careful than this, but the job is the same: turn text into a number that looks random.

In this run every bucket holds exactly one key. Finding "item5" takes one comparison. That is the best case, and it is also the expected case when the spread is good.

The word "expected" matters. The result above is for this particular set of eight keys. A different set could land two keys in one bucket. Expected cost is an average over the keys you might store, with a good hash function. It is not a promise for every set of keys.

What a collision costs

A collision happens when two different keys map to the same bucket. The table has to keep both. In the design used above, which is called chaining, the bucket becomes a short list and the table checks each entry in the list.

Take two keys in one bucket. Looking up the second key costs two comparisons, not one: first the table checks the first key and sees it is not a match, then it checks the second key and finds it. With three keys in one bucket, the cost rises to three comparisons for the last key. One collision adds one comparison. A few collisions add a few comparisons. None of this changes the picture much, as long as each bucket stays short.

The cost grows when the buckets get long. That leads to the worst case.

The worst case: every key in one bucket

Suppose the hash function returns the same number for every key. This is a bad hash function, and it is an easy one to write by mistake. The table still works, because it checks keys for equality, but every key lands in bucket 0. The table has become a single list.

Here is that case. The function constant_hash returns zero for every key. We insert n keys and count the comparisons.

Demo 2: every key has the same hash (worst case)
n=   10  total comparisons for 10 inserts=      45  longest bucket=10
n=  100  total comparisons for 100 inserts=    4950  longest bucket=100
n= 1000  total comparisons for 1000 inserts=  499500  longest bucket=1000

Read the output carefully. The table has 64 buckets, but only bucket 0 is used. Each insert has to scan everything already stored, so the k-th insert makes about k comparisons. Added up, n inserts make about n times n minus 1, divided by 2, comparisons. For 1000 keys that is 499500.

Multiplying the number of keys by 10 multiplies the cost by about 100. This is O(n squared) total work. A single lookup in this table costs O(n), because it scans the one long bucket. The table has lost its advantage completely. A plain list would do the same job with the same scan.

Real systems have been attacked this way. An attacker who knows the hash function can send keys that all collide, and a server that stores request fields in a hash table slows to a crawl. Modern language runtimes protect against this in several ways, such as using a random seed for the hash, but the basic lesson holds: the constant-time promise depends on the keys being spread out.

Load factor: how full the table is

The load factor is the number of stored keys divided by the number of buckets. A table with 64 buckets and 32 keys has a load factor of 0.5. A table with 64 buckets and 128 keys has a load factor of 2.0. Each bucket holds about as many keys as the load factor says, on average.

The load factor sets the average length of a bucket, and the average length sets the average cost of a lookup. A low load factor means short buckets and fast lookups, but wasted empty buckets. A high load factor means fewer empty buckets and more collisions. Table designers pick a maximum load factor and grow the table when they reach it.

The next example keeps the table at 64 buckets and fills it with more and more keys. It measures two things: the average number of comparisons for a key that is stored (a successful lookup), and for a key that is not stored (an unsuccessful lookup). It uses the same ChainedTable and simple_hash as before. The class is repeated in full so the example runs by itself.

Demo 3: load factor with 64 buckets and simple_hash
n    load  successful_avg  unsuccessful_avg  longest_bucket
 16  0.25            1.00              0.12               1
 32  0.50            1.00              0.22               1
 64  1.00            1.50              0.41               3
 96  1.50            1.90              0.69               4
128  2.00            1.95              1.66               5

The average cost rises with the load factor, and it rises slowly. At load 0.25, a stored key is found in about one comparison. At load 2.0, the average is still close to two comparisons, because a stored key shares its bucket with about two other keys, and the search stops partway down it.

The standard textbook formula for a table with chaining and an evenly spread hash function says a successful lookup costs about 1 plus half the load factor, and an unsuccessful lookup costs about the load factor. The successful numbers above follow this closely: at load 2.0 the formula gives 2.0 and the measurement is 1.95. The unsuccessful numbers do not follow it. This is a sign that simple_hash does not spread the keys missing0 to missing127 as evenly as the formula assumes. Formulas describe ideal spreading. Measurements show what your real keys do.

The longest bucket column matters too. With 128 keys in 64 buckets, one bucket holds five keys. An unlucky key that lands there pays five comparisons, even though the average is under two. Average cost hides the worst bucket, and a slow request is usually one that hit a long bucket.

What happens when the table gets full

A table with a fixed number of buckets cannot stay at a low load factor as you keep adding keys. Table designers handle this with resizing. When the load factor passes a chosen limit, the table allocates a bigger array of buckets, often double the size, and moves every key into it. The new bucket for each key is computed again, because the bucket index depends on the number of buckets.

Resizing is expensive for one insert. It might copy thousands of keys in one go. But it happens rarely, and each resize makes the table big enough for many more inserts. Over a long run of inserts, the average cost per insert stays small. This is the same idea as amortised cost (the average cost per operation over a long run), which is covered in the module on space complexity and amortised cost. For this lesson, the useful point is simple: a resizing table keeps its load factor under a limit, and that limit keeps the average lookup cost low.

The limit is a trade-off. A low limit gives short buckets and fast lookups, but the table uses more memory for empty buckets. A high limit saves memory but makes buckets longer. Python's dict and set use their own limits and their own methods for handling collisions. The exact numbers are an internal detail that can change between Python versions, so do not rely on them in your own code. What you can rely on is the principle: the table grows so that the load factor stays bounded, and that is why the average lookup stays close to constant.

A third example: keys that look alike

The hash function is what decides whether real keys spread out. Keys that look similar can still collide if the function does not mix their characters well. A simple test is to look at the bucket sizes after you insert a set of keys.

Take a weak hash function that adds up the character codes of the key. The words "listen" and "silent" use the same letters in a different order, so their totals are the same. Adding up the codes gives 655 for both words.

Two keys with the same total always land in the same bucket, whatever the table size. A hash function that adds up letters is easy to write and easy to break. The simple_hash used in this lesson multiplies by 31 at each step, so the order of the letters changes the result: simple_hash("listen") % 64 is 7 and simple_hash("silent") % 64 is 21. Your own tests should include anagrams like these, because they expose weak functions. For real code, use the hash function that your language library already provides. It has been tested on far more keys than you will test by hand.

The lesson for your own work is to measure, not guess. If a table is slow, look at its size and bucket lengths. A table with 10 keys in 10 buckets is not the cause of a slow program. A table with 10000 keys in 4 buckets is.

Common mistakes

Mistakes about hash table costs usually come from treating "O(1)" as "always fast".

Mistake 1: using a mutable key. A key must not change after it is stored. If you change it, the hash function may return a different number, and the table will look in the wrong bucket. Python does not allow this at all for lists:

Running cache[key] = 7 with a list as the key stops with this error:

TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

Use a tuple, such as (3, 4), which cannot change. Python accepts tuples as keys because tuples cannot be modified after creation.

Mistake 2: assuming lookup is constant when keys are shaped badly. If every key in a table returns the same hash, lookups scan the whole table. The code still runs, and the answers are still correct, so the problem can hide until the data grows. Check that your keys spread across buckets when you build a custom hash function.

Mistake 3: building a huge table and then looking up a few keys. Filling a table costs time too. If you only need to check whether one value appears in a list of ten items, a list scan is simpler and just as fast. A hash table pays off when there are many lookups against many keys.

Mistake 4: reading the load factor as a fixed number of comparisons. A load factor of 2.0 does not mean every lookup takes two comparisons. It means the average bucket holds two keys. Some lookups take one, some take five. The longest bucket matters for the slowest request.

Mistake 5: ignoring memory. A table with a low load factor has many empty buckets, and each empty bucket takes memory. Speed and memory trade against each other. Choosing a table size is a decision about both.

Practice

Exercise 1. A table has 100 buckets and holds 300 keys. What is the load factor? If all 300 keys land in one bucket, about how many comparisons does it take to find a key that is stored there?

Show the answer.

The load factor is 300 divided by 100, which is 3.0. If all 300 keys share one bucket, that bucket is a list of 300 pairs. Finding a key costs one comparison for each pair up to the one it is looking for. On average the key is in the middle, so the cost is about 150 comparisons, and in the worst position it is 300.

Exercise 2. Using the constant hash from Demo 2, how many comparisons does it take to insert 50 keys in total? Explain the formula.

Show the answer.

The insert of the first key makes no comparisons, because the bucket is empty. The second insert makes one comparison, the third makes two, and the fiftieth makes 49. The total is 0 + 1 + 2 + ... + 49, which is 49 times 50 divided by 2, so 1225 comparisons. This is the same pattern as Demo 2, where 100 inserts gave 4950 comparisons.

Exercise 3. Change Demo 3 so it uses 128 buckets instead of 64, and keep the same key counts. Predict whether the successful average at load 2.0 goes up or down, and then run the code to check.

Show the answer.

With 128 buckets, the load factor at 128 keys is 1.0 instead of 2.0, so the successful average should go down. Running the code with ChainedTable(128, simple_hash) gives this output for the successful average:

16 keys: 1.0
32 keys: 1.0
64 keys: 1.09
96 keys: 1.27
128 keys: 1.32

At 128 keys the average drops from 1.95 with 64 buckets to 1.32 with 128 buckets. The exact values depend on how simple_hash spreads these keys, so the output is the check.

Exercise 4. Write a function average_successful(num_keys, num_buckets) that builds a ChainedTable with simple_hash, stores keys item0 to item{num_keys - 1}, and returns the average number of comparisons for a successful lookup of each stored key. Call it with 200 keys and 64 buckets.

Show the answer.

average successful comparisons: 2.46

The load factor here is 200 divided by 64, about 3.1. The formula for a successful lookup gives about 1 plus 3.1 divided by 2, which is about 2.56. The measured value of 2.46 is close to that.

Exercise 5. A program stores one million keys in a table with a constant hash function. About how many comparisons does one successful lookup take on average? Is this an O(1) or O(n) cost?

Show the answer.

With a constant hash, all one million keys share one bucket. A successful lookup scans the bucket until it finds its key. Keys are in the bucket in insertion order, so a key stored at a random position costs about half of one million comparisons, which is about 500000. The cost grows with the number of keys, so it is O(n). This is the case the table is supposed to avoid.

Summary

• A hash table turns a key into a bucket number, so a lookup checks one bucket instead of every key.
• The expected cost of a lookup is constant only when keys spread across buckets fairly evenly.
• When many keys share one bucket, lookups scan that bucket, and a table of n keys in one bucket costs O(n) per lookup.
• The load factor, which is keys divided by buckets, sets the average bucket length and so the average cost.
• Tables grow when the load factor passes a limit, which keeps average lookups close to constant.
• Keys must not change after they are stored, and a poor hash function can silently turn a fast table into a slow list.