Skip to content
Tutorials Center
My learning

Topics

Lesson 87 of 135 ยท Data Structures in C

Hash Tables

Build a hash table in C - string hash functions, separate chaining, a string-to-int map with put, get and remove, load factor and resizing, plus open addressing.

A hash table stores key-value pairs and finds any key in roughly constant time, no matter how many entries it holds. It's the structure behind Python's dict, JavaScript objects and Map, C++'s std::unordered_map, database indexes, compiler symbol tables and caches of every kind. C has none built in, so C programmers write their own, and knowing how lets you understand (and tune) every other language's version too.

The trick is to turn the key into an array index. A hash function scrambles the key into a number, and that number, reduced to the table's size, picks a bucket. Looking up the key later computes the same number and goes straight to the same bucket, with no searching through the other entries. In this lesson you'll write hash functions, handle collisions with chaining, build a complete string-to-int map, make it resize as it grows, and finish with open addressing, the cache-friendly alternative.

From keys to buckets

Picture an array of 8 buckets. To store the key "apple":

  1. Compute hash("apple"), say 2,968,163,817.
  2. Reduce it to a bucket index: 2968163817 % 8 is 1.
  3. Store the pair in bucket 1.

Looking up "apple" repeats steps 1 and 2 and checks bucket 1 only. Two different keys can land in the same bucket, which is called a collision; with 8 buckets and 9 keys it's guaranteed (the pigeonhole principle). Every hash table needs a strategy for collisions, and the two big families are:

  • Separate chaining: each bucket holds a small linked list of entries.
  • Open addressing: every entry lives in the array itself; on a collision you probe other slots.

The performance of either depends on two things: a hash function that spreads keys evenly, and keeping the table from getting too full.

Hash functions

A good hash function is deterministic (same key, same hash), fast, and spreads similar keys far apart. A tempting but terrible idea is to add up the characters: "stop", "pots", "tops" and "spot" are all anagrams and get the same sum, and short keys only ever reach small numbers.

A simple, well-tested choice for strings is FNV-1a: start from a fixed "offset basis", and for each byte, XOR it in and multiply by a fixed prime. The multiplication smears every bit of the input across the whole result. Compare the two:

C A bad hash versus FNV-1a

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

All four anagrams get the sum 454 but completely different FNV-1a hashes. The second part shows what that means for a table. A thousand realistic keys (user0 to user999) produce only a narrow range of character sums, so the sum hash crams them into 55 of 1,024 buckets, with a chain of 70 entries in the worst one. FNV-1a uses 650 buckets and its longest chain holds 4 entries, which is about what a perfectly random assignment would give. A few details matter:

  • The hash is uint32_t from <stdint.h>, and unsigned overflow wraps modulo 2ยณยฒ, which is well defined and exactly what the algorithm wants. With a signed type, the overflow would be undefined behavior.
  • Bytes are read as unsigned char, so characters above 127 (UTF-8 text) give the same result on every platform, whether plain char is signed or not.
  • The hash function is passed as a function pointer, so spread works with any of them.

Note: FNV-1a is fine for learning and for trusted keys. If attackers choose your keys (HTTP headers, JSON from the internet), they can pick strings that all collide and turn every lookup into a slow list scan, a hash flooding attack. Servers use a keyed hash such as SipHash with a random secret seed per process. Hash tables never need cryptographic hashes like SHA-256; those are far slower than necessary.

A string-to-int map with chaining

Now for a full map: keys are strings, values are int. Each bucket is the head of a linked list of entries. The map copies each key it stores, so callers can pass temporary buffers, and it frees those copies itself. That ownership rule is the most important design decision in a C container.

C A chained hash map: put, get, remove

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The dump shows the chains: 7 keys in 5 buckets means some buckets hold two or more entries and others may be empty. Updating banana changes its value without adding an entry, so the count stays 7.

The heart of the design is find_link. Like the list code in earlier lessons, it returns a pointer to the link that points at the matching entry (or to the NULL link at the end of the chain). map_put, map_get and map_remove all reuse it, so the search logic exists in exactly one place. Note also calloc for the bucket array: it zero-fills, which gives all-NULL pointers on every platform you'll realistically meet.

Load factor and resizing

The average chain length is the load factor: count / capacity. With a good hash, a lookup inspects about 1 + load factor / 2 entries, so as long as the load factor stays bounded (chaining tables commonly allow up to about 0.75 to 1.0), operations stay O(1) on average. A table that never grows, though, eventually turns into a few very long lists.

So the table resizes: when the load factor crosses a threshold, allocate a bucket array about twice as big and rehash every entry into it. Each entry's bucket depends on the capacity (hash % capacity), so entries really do move. A resize costs O(n), but because the capacity doubles, it happens rarely enough that inserts stay O(1) amortized, the same argument as for dynamic arrays.

C Watching a table grow

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Starting from 4 buckets, the table doubles nine times on the way to 1,000 entries and ends with 2,048 buckets, a load factor of 0.49 and no chain longer than 3. Most of the 1,000 inserts did no extra work at all; the nine resizes together moved 1,533 entries (3 + 6 + 12 + ... + 768), fewer than two moves per insert on average. The * 4 > * 3 comparison checks "load factor above 0.75" using integers only, avoiding floating-point arithmetic in a hot path.

Notice that grow moves the existing nodes into the new array instead of allocating new ones, and that if calloc fails, the old table is left intact and still works. Resizing the bucket array invalidates nothing the user holds, because entries themselves never move; that's one advantage of chaining.

Open addressing

Chaining allocates a node per entry and follows pointers, which costs memory and cache misses. Open addressing stores entries directly in the array. On a collision, it probes other slots in a fixed sequence; the simplest is linear probing: try the next slot, then the next, wrapping around at the end. Because neighboring slots share cache lines, linear probing is very fast in practice, and many modern high-performance tables use it or a refined variant.

Two rules come with it:

  • The table must never fill up. Keep the load factor below about 0.7, or probe sequences get long.
  • Deleting is tricky: simply emptying a slot would break the probe chain for keys stored after it. Use a tombstone marker ("deleted, keep probing"), or shift later entries back.

Here is a small set of integers with linear probing and tombstones:

C Linear probing with tombstones

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Follow the output line by line. Keys 7, 6 and 21 all have home slot 4, so 6 moves on to slot 5 and 21 to slot 6. Key 47 wants slot 7, finds 46 there, wraps around to slot 0 (taken by 15) and settles in slot 1. After 7 is removed, slot 4 shows [x], a tombstone, and 6 and 21 are still found, because searches walk past tombstones instead of stopping. If the removal had marked the slot EMPTY, the search for 6 would stop at slot 4 and wrongly report it missing. Finally, 37 (also home 4) reuses the tombstone slot. (For integer keys, the multiplication by 2654435761, a constant close to 2ยณยฒ divided by the golden ratio, is a classic quick way to scramble bits; the upper bits are the best mixed, hence the shift.)

Hash tables versus trees

Hash table Balanced BST (binary trees)
Lookup, insert, delete O(1) average, O(n) worst case O(log n) guaranteed
Keys kept in order No Yes, in-order traversal
Range queries ("all keys from b to f") No Yes
Needs A good hash function and equality A comparison function
Memory Array slack + per-entry overhead Two pointers per node

Choose a hash table when you need fast exact-match lookups and don't care about order: counting, deduplicating, caching, symbol tables. Choose a tree when order matters. The text analyzer project uses a hash table to count word frequencies in a whole document.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is "add up the character codes" a poor string hash function?

    stop and pots have identical sums, so they always collide. A good hash spreads similar keys across the whole range.
  2. 2. A chained table has 1,000 entries in 500 buckets. What is its load factor?

    The load factor is count / capacity: 1000 / 500 = 2, so chains are two entries long on average. Time to resize.
  3. 3. Why does the FNV-1a code use uint32_t instead of int for the hash value?

    The algorithm relies on arithmetic modulo 2ยณยฒ. Unsigned types guarantee that wrap-around; signed overflow does not.
  4. 4. In a linear-probing table, what goes wrong if removing a key simply marks its slot EMPTY?

    Searches stop at the first EMPTY slot. A key stored further along its probe sequence would be reported missing, which is why tombstones exist.
  5. 5. When a chained table resizes from 8 to 16 buckets, why must every entry be rehashed?

    The hash itself is the same, but reducing it modulo 16 instead of 8 can give a different index, so each entry has to be placed again.

Summary

  • A hash table maps a key to a bucket with hash(key) % capacity, giving O(1) average lookups, insertions and deletions.
  • Good hash functions are deterministic, fast and spread similar keys apart; FNV-1a is a simple choice for strings. Use unsigned arithmetic so overflow wraps legally.
  • Collisions are unavoidable. Separate chaining keeps a linked list per bucket; a find_link helper makes put, get and remove share one search.
  • Keep the load factor bounded by doubling the bucket array and rehashing every entry; inserts stay O(1) amortized.
  • Open addressing stores entries in the array and probes on collisions; linear probing is cache-friendly, needs a low load factor, and uses tombstones for deletion.
  • The container should own copies of its keys and free them; attackers who choose keys can force collisions, so servers use seeded hashes.
  • Use hash tables for fast exact lookups and trees when you need keys in order.

Next: Sorting and Searching Algorithms, where you'll implement the classic sorts yourself and time them against each other.