FNV Hash Map

This article was partially written by Claude Sonnet 3.5. All of the below was an attempt by me to understanding how hashtables work better, and FNV was the function I chose since I use it often without understanding why it is fast.

:warning: I’m not a C programmer, I just want to get better at it. I found bugs in Claude’s implementation, and I’m sure there’s more I didn’t find. All code below includes my bugfixes, and what I found is cataloged at the end.

All of this is because of a build-it-from-scratch kick with C that I’ve been on, re-inventing a lot of wheels to see how they work. See the use case for this hashmap here.

The Code

(Which we will explain further on, this is just to get the big picture.)

hashmap.h

#ifndef HASHMAP_H
#define HASHMAP_H

// stdint pulls in exact width integers like uint64_t
#include <stdint.h>
// stdbool includes...bool
#include <stdbool.h>
// For size_t
#include <stddef.h>

// Opaque pointer to hide implementation details
typedef struct HashMap HashMap;

typedef void (*ValueCleanupFn)(void*);

// Create/destroy functions
HashMap* hm_create(size_t initial_capacity, ValueCleanupFn value_cleanup);
void hm_destroy(HashMap* map);

// Core operations
bool hm_put(HashMap* map, const char* key, void* value);
void* hm_get(HashMap* map, const char* key);
bool hm_remove(HashMap* map, const char* key);

// Utility functions
size_t hm_size(HashMap* map);
bool hm_is_empty(HashMap* map);

#endif // HASHMAP_H

hashmap.c

// includes stdint and stdbool
#include "hashmap.h" 
// For malloc / calloc / free
#include <stdlib.h>
// For strcmp / strdup
#include <string.h>

// FNV-1a hash function constants
#define FNV_OFFSET 14695981039346656037UL
#define FNV_PRIME 1099511628211UL

// Initial load factor and growth settings
#define INITIAL_CAPACITY 16
#define LOAD_FACTOR_THRESHOLD 0.75

typedef struct Entry {
    char* key;
    void* value;
    struct Entry* next;
} Entry;


// typedef in header
struct HashMap {
    // A pointer to a pointer of type Entry,
    // in this case this is an array of pointers of Entry.
    // Each index in the array is a "bucket" and the
    // Entries are a linked list.
    Entry** buckets;
    size_t capacity;
    size_t size;
    // A fn to call when we clean up values.
    ValueCleanupFn value_cleanup;
};

// FNV-1a hash function - proven fast for string keys
static uint64_t hash_key(const char* key) {
    uint64_t hash = FNV_OFFSET;
    for (const char* p = key; *p; p++) {
        hash ^= (uint64_t)(unsigned char)(*p);
        hash *= FNV_PRIME;
    }
    return hash;
}

size_t round_to_power_of_2(size_t initial_capacity) {
    // Ensure power of two capacity to ensure fast indexing
    if (initial_capacity < INITIAL_CAPACITY) {
        return INITIAL_CAPACITY;
    }

    initial_capacity--;

    // Calculate the number of shifts needed based on the size of size_t
    #if SIZE_MAX == 0xffffffffffffffffULL  // 64-bit
        initial_capacity |= initial_capacity >> 32;
    #endif
    initial_capacity |= initial_capacity >> 16;
    initial_capacity |= initial_capacity >> 8;
    initial_capacity |= initial_capacity >> 4;
    initial_capacity |= initial_capacity >> 2;
    initial_capacity |= initial_capacity >> 1;

    // Check for overflow before incrementing
    if (initial_capacity == SIZE_MAX) {
        // We can't round up - we should handle this error
        // Maybe return 0 to indicate error, or
        // use errno, or return the largest power of 2
        return SIZE_MAX >> 1;  // Return largest power of 2 that fits
    }
    
    return initial_capacity + 1;

}

// Create a `HashMap`, returns NULL if a `HashMap` could not be created.
HashMap* hm_create(size_t initial_capacity, ValueCleanupFn value_cleanup) {
    // Round up to the next power of 2
    initial_capacity = round_to_power_of_2(initial_capacity);
    HashMap* map = malloc(sizeof(HashMap));
    if (!map) return NULL;

    map->value_cleanup = value_cleanup;

    // calloc initializes the memory when it creates it, and it does the 
    // multiplication of `sizeof(Entry*) * capapcity` and checks for overflows.
    map->buckets = calloc(initial_capacity, sizeof(Entry*));
    if (!map->buckets) {
        free(map);
        return NULL;
    }

    map->capacity = initial_capacity;
    map->size = 0;
    return map;
}

static void resize_if_needed(HashMap* map) {
    if ((double)map->size / map->capacity > LOAD_FACTOR_THRESHOLD) {
        // No resize needed
        return;
    }

    size_t new_capacity = map->capacity * 2;
    Entry** new_buckets = calloc(new_capacity, sizeof(Entry*));
    if (!new_buckets) return; // Failed alloc

    // Rehash all entries
    for (size_t i = 0; i < map->capacity; i++) {
        // since we calloc'd to zero this out, buckets with no pointer are NULL
        Entry* entry = map->buckets[i];
        while (entry) { // Traverse the linked list
            Entry* next = entry->next; 
            size_t new_index = hash_key(entry->key) & (new_capacity - 1);
            // Set the next for this entry to whatever is currently in the 
            // new_buckets list of pointers, then set the new_buckets pointer
            // to this entry, extending the linked list.
            entry->next = new_buckets[new_index];
            new_buckets[new_index] = entry;
            entry=next;
        }
    }
    free(map->buckets);
    map->buckets = new_buckets;
    map->capacity = new_capacity;
}

// Returns true if the key was set, false if allocations failed and it was not set.
// If the key already exists, this will overwrite its value.
bool hm_put(HashMap* map, const char* key, void* value) {
    resize_if_needed(map);
    size_t index = hash_key(key) & (map->capacity - 1);

    // Check for an existing key
    for (Entry* entry = map->buckets[index]; entry; entry = entry->next) {
        if (strcmp(entry->key, key) == 0) {
            if (map->value_cleanup) map->value_cleanup(entry->value);
            entry->value = value;
            return true;
        }
    }
    
    // Create a new entry
    Entry* new_entry = malloc(sizeof(Entry));
    if (!new_entry) return false;
    
    new_entry->key = strdup(key);
    if (!new_entry->key) {
        free(new_entry);
        return false;
    }

    new_entry->value = value;
    new_entry->next = map->buckets[index];
    map->buckets[index] = new_entry;
    map->size++;
    return true;
}

void* hm_get(HashMap* map, const char* key) {
    size_t index = hash_key(key) & (map->capacity - 1);
    for (Entry* entry = map->buckets[index]; entry; entry = entry->next) {
        if (strcmp(entry->key, key) == 0) {
            return entry->value;
        }
    }
    return NULL;
}


// Returns true if the key was in the map and was deleted.
bool hm_remove(HashMap* map, const char* key) {
    size_t index = hash_key(key) & (map->capacity - 1);
    Entry** pp = &map->buckets[index];

    while (*pp) {
        Entry* entry = *pp;
        if (strcmp(entry->key, key) == 0) {
            // This is tricky.
            // This is setting the pervious entries / buckets pointer
            // to point the the next entry to skip this node in the linked list.
            *pp = entry->next;
            free(entry->key);
            if (map->value_cleanup) map->value_cleanup(entry->value);
            free(entry);
            map->size--;
            return true;

        }
        pp = &entry->next;
    }
    return false;
}

void hm_destroy(HashMap* map) {
    if (!map) return;

    for (size_t i = 0; i < map->capacity; i++) {
        Entry* entry = map->buckets[i];
        while (entry) {
            Entry* next = entry->next;
            free(entry->key);
            if (map->value_cleanup) map->value_cleanup(entry->value);
            free(entry);
            entry=next;
        }

    }
    free(map->buckets);
    free(map);
}

// Get the current number of elements in the map
size_t hm_size(HashMap* map) {
    return map->size;
}


// Check if the map is empty
bool hm_is_empty(HashMap* map) {
    return map->size == 0;
}

Key Ideas

Power of two sizing (capacity)

Power of two sizing allows for very fast lookup with the hash key.

In our implementation, we use this simple but effective line:

size_t index = hash_key(key) & (map->capacity - 1);

Let’s break down why this works so well. Say our hashmap has a capacity of 16. In binary:

capacity     = 16    = 00010000
capacity - 1 = 15    = 00001111

When we do a bitwise AND (&) with any number and (capacity-1), we’re essentially taking the remainder of that number when divided by capacity. But we’re doing it much faster than using the modulo operator (%).

Let’s walk through an example. Imagine our FNV hash function returns this value for a key:

hash = 12345678    = 00000000000000000000000010111100101100101001110
capacity - 1 = 15  = 00000000000000000000000000000000000000001111

When we do the bitwise AND:

hash         = 00000000000000000000000010111100101100101001110
capacity - 1 = 00000000000000000000000000000000000000001111
result       = 00000000000000000000000000000000000000001110 = 14

We get 14, which is a valid index for our array of size 16.

This is why we always make our capacity a power of 2 in the create function:

// Round up to next power of 2
initial_capacity--;
initial_capacity |= initial_capacity >> 1;
initial_capacity |= initial_capacity >> 2;
initial_capacity |= initial_capacity >> 4;
initial_capacity |= initial_capacity >> 8;
initial_capacity |= initial_capacity >> 16;
initial_capacity++;

The magic here is that powers of 2 minus 1 give us numbers that are all 1s in binary:

Capacity    Binary (capacity)    Binary (capacity - 1)
4           100                  011
8           1000                0111
16          10000               1111
32          100000              11111

If we didn’t use a power of 2 for capacity, say 10:

capacity = 10     = 1010
capacity - 1 = 9  = 1001

This would lead to uneven distribution of indices because some bits in our mask would be 0, meaning those positions in our hash value wouldn’t contribute to the final index.

To make this even more concrete, let’s add some debug code to see this process:

void debug_hash_to_index(const char* key, size_t capacity) {
    uint64_t hash = hash_key(key);
    size_t index = hash & (capacity - 1);
    
    printf("Key: %s\n", key);
    printf("Hash: %lu\n", hash);
    printf("Capacity: %zu\n", capacity);
    printf("Capacity - 1 (mask): %zu\n", capacity - 1);
    printf("Resulting index: %zu\n\n", index);
}

// Usage example:
debug_hash_to_index("hello", 16);
debug_hash_to_index("hello", 32);

This technique of using bitwise AND with (power_of_2 - 1) is so efficient that it’s used in many high-performance applications, including the Java HashMap implementation.

Fast hashing

The FNV (Fowler-Noll-Vo) hash function a fascinating algorithm that achieves excellent distribution while remaining surprisingly simple and fast.

Let’s look at the core implementation from our hashmap:

#define FNV_OFFSET 14695981039346656037UL  // FNV offset basis for 64-bit
#define FNV_PRIME 1099511628211UL          // FNV prime for 64-bit

static uint64_t hash_key(const char* key) {
    uint64_t hash = FNV_OFFSET;            // Start with the offset basis
    for (const char* p = key; *p; p++) {   // For each byte in the input
        hash ^= (uint64_t)(unsigned char)(*p);  // XOR the byte into the hash
        hash *= FNV_PRIME;                 // Multiply by the prime number
    }
    return hash;
}

The FNV hash works through a carefully chosen combination of three elements:

1. An offset basis (FNV_OFFSET): This is a large, carefully selected number that starts the hash calculation. Think of it as providing a random-looking starting point for every hash computation.

2. A prime number (FNV_PRIME): This prime was specifically chosen because its multiplication properties help spread the bits of the input across the hash result. It’s similar to how multiplying by a prime number tends to distribute numbers evenly when taking remainders.

3. The mixing operation: For each byte of input, the algorithm:

   • XORs the byte into the current hash value
   • Multiplies the result by the prime number

Let’s walk through a simple example of hashing the string “cat”:

Starting with: hash = FNV_OFFSET
For 'c' (ASCII 99):
    hash = hash XOR 99
    hash = hash * FNV_PRIME

For 'a' (ASCII 97):
    hash = hash XOR 97
    hash = hash * FNV_PRIME

For 't' (ASCII 116):
    hash = hash XOR 116
    hash = hash * FNV_PRIME

The genius of FNV lies in how these operations interact:

• The XOR operation mixes in each byte’s bits in a reversible way
• The multiplication by a prime number diffuses these bits throughout the hash value
• Each subsequent byte affects all bits of the final hash

What makes FNV particularly good for hashmaps is:

1. Speed: It uses simple CPU operations (XOR and multiply)
2. Avalanche effect: Small input changes cause large hash value changes
3. Good distribution: Output values spread evenly across the possible range
4. Low collision rate: Different inputs rarely produce the same hash

We can actually visualize this distribution. Here’s a conceptual example:

// Demonstrating FNV's distribution
void visualize_distribution(void) {
    char key[4] = "aaa";
    int buckets[16] = {0};  // Count hashes in 16 buckets
    
    // Try all possible 3-letter combinations
    for(char c1 = 'a'; c1 <= 'z'; c1++) {
        for(char c2 = 'a'; c2 <= 'z'; c2++) {
            for(char c3 = 'a'; c3 <= 'z'; c3++) {
                key[0] = c1; key[1] = c2; key[2] = c3;
                uint64_t hash = hash_key(key);
                buckets[hash % 16]++;  // Count which bucket it falls into
            }
        }
    }
    // buckets[] would show relatively even distribution
}

When we need to optimize this function further, there are several variations:

• FNV-1a (what we used): XOR then multiply
• FNV-1: Multiply then XOR
• Different bit widths (32-bit, 64-bit, etc.)

The version we used (FNV-1a) is generally considered the best for most purposes because the XOR-then-multiply pattern provides slightly better avalanche behavior than the original FNV-1.

Quick Aside on the implementation from Claude in C

I am not a C programmer, really. And I’m not an expert in building hash maps. But the implementation from Claude had a lot of bugs that I caught along the way that would have been problems if I just copy pasted and ran with it:

• Claude didn’t free the memory of the values when calling hm_put or hm_destroy.
• Claude didn’t handle size_t being 64 bits for initial_capacity
  • When prompted to handle this better, it then failed to handle the case of being passed SIZE_MAX (max u64) (if someone asked for a hashmap of that size, things are arguably borked, but it should still handle it)
• Claude truncated the comparison against LOAD_FACTOR_THRESHOLD to a float instead of a double

Other Interesting Tidbits

Null Terminated Strings

I’ve always wondered at the null terminated string choice in C. I still wonder about it, but this little loop at least shed a bit of light on how an ecosystem designed around it can work:

for (const char* p = key; *p; p++) {
    hash ^= (uint64_t)(unsigned char)(*p);
    hash *= FNV_PRIME;
}

That loops through the string, the stop condition is checking *p which will be false when it hits the null termination character.

The Cost or Resizing a HashMap

I knew that you had to re-allocate and copy, like when resizing a Vector/List, but I did not realize that re-sizing involved re-hashing all keys.

Linked Lists :vomit:

What if we just kept a dynamically sized array… or even fixed size for each bucket that held entries? That way when looking through a bucket we don’t have to fetch all over the heap. I’m betting that this is negligible with a good hash function that avoids collisions. But I don’t really have a sense of how often collisions happen. To be explored later.

Further Reading

• Article on the limitations of the Rust Hasher trait.
• Article on fixed size integer hashing (potential future exploration for encoded kmer hashing).

Comment

If you have any feedback, especially pointing out mistakes, please leave a comment!

• Hacker News
• Reddit
• Blue Sky