tidwall/hashmap.c - GitHub Documentation Generator

Project Overview

This library provides a high-performance, generic hash map implementation in C. It uses open addressing with Robin Hood hashing to deliver low probe counts and fast lookups. You can store any key/value types by supplying custom hash and equality functions, and iterate over entries with built-in utilities.

Key Features

Open addressing with Robin Hood hashing for minimal clustering and uniform probe lengths
Generic storage: user-defined key and value structures
Custom hash and compare callbacks per map instance
Iteration utilities: hashmap_each, hashmap_keys, hashmap_values
Thread-unsafe core for zero locking overhead (thread safety managed externally)
Lightweight: only a single C source file, no external dependencies

Performance Characteristics

Average O(1) lookup, insertion, and deletion
Low memory overhead and high cache locality from open-address layout
Maintains high load factors (up to ~90%) with consistent probe lengths
Robin Hood strategy minimizes worst-case lookup time under heavy load

When to Choose This Library

You need a drop-in, header-only C hash map with minimal dependencies
You require maximum throughput in single-threaded or externally synchronized contexts
You want flexible key/value types via custom callbacks
You value predictable performance under high load factors

Quick Start Example

Instantiate a map for NUL-terminated string keys and integer values.

#include "hashmap.h"
#include <stdlib.h>
#include <string.h>

// Hash function for C strings
static size_t str_hash(void *key) {
    char *s = key;
    size_t h = 5381;
    while (*s) h = ((h << 5) + h) + (unsigned char)*s++;
    return h;
}

// Equality function for C strings
static int str_eq(void *a, void *b) {
    return strcmp((char*)a, (char*)b) == 0;
}

int main(void) {
    // Create map with initial capacity 1024
    hashmap_t *map = hashmap_new(1024, str_hash, str_eq);

    // Insert key/value
    int value = 42;
    hashmap_set(map, "answer", &value);

    // Retrieve value
    int *ptr = hashmap_get(map, "answer");
    if (ptr) {
        printf("The answer is %d\n", *ptr);
    }

    // Iterate all entries
    hashmap_each(map, [](https://github.com/tidwall/hashmap.c/blob/master/void *key, void *val) {
        printf("%s → %d\n", (char*)key, *(int*)val);
    });

    hashmap_free(map);
    return 0;
}
## Quick Start & Basic Usage

This section shows how to integrate Tidwall’s high-performance generic hash map into your C project and run a minimal example that creates a map, inserts entries, retrieves values, iterates, and cleans up.

### 1. Add to Your Project

Option A: Git submodule

git submodule add https://github.com/tidwall/hashmap.git extern/hashmap

Include `extern/hashmap` in your build.

Option B: Copy files

cp path/to/hashmap.h path/to/hashmap.c your_project/src/

Ensure your compiler can find `hashmap.h` and compile `hashmap.c` into your project.

### 2. Compile Flags

Compile with C11 and optimization. Adjust `-I` to your include path:

gcc -std=c11 -O2 -I./include -c src/hashmap.c -o build/hashmap.o gcc -std=c11 -O2 -I./include example.c build/hashmap.o -o build/example

Or combine:

gcc -std=c11 -O2 -I./include example.c src/hashmap.c -o build/example


### 3. Minimal Working Example

Below is `example.c`. It maps string keys to integer values, demonstrating creation, insertion, lookup, iteration, removal, and cleanup.

```c
#include "hashmap.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// String hash and compare functions
static size_t str_hash(const void *key) {
    return hashmap_hash_string(key);
}
static int str_cmp(const void *a, const void *b) {
    return strcmp(a, b);
}

int main(void) {
    // Create a map: initial capacity 16, string hash/compare, free() for keys and values
    struct hashmap *map = hashmap_new(
        16,
        str_hash,
        str_cmp,
        free,   // free(key)
        free    // free(value)
    );

    // Insert entries
    char *k1 = strdup("one");
    int *v1 = malloc(sizeof *v1); *v1 = 1;
    hashmap_set(map, k1, v1);

    char *k2 = strdup("two");
    int *v2 = malloc(sizeof *v2); *v2 = 2;
    hashmap_set(map, k2, v2);

    // Retrieve a value by key
    int *r1 = hashmap_get(map, "one");
    if (r1) {
        printf("one → %d\n", *r1);
    }

    // Iterate all entries
    struct hashmap_iter *iter = hashmap_iter(map);
    void *key;
    void *value;
    while (hashmap_next(map, iter, &key, &value)) {
        printf("%s => %d\n", (char*)key, *(int*)value);
    }
    hashmap_iter_free(iter);

    // Remove an entry
    hashmap_remove(map, "two");

    // Cleanup map and all remaining keys/values
    hashmap_free(map);
    return 0;
}

Compile and run:

gcc -std=c11 -O2 -I./include example.c src/hashmap.c -o example
./example

Common Operations

hashmap_set(map, key, value): insert or update
hashmap_get(map, key): retrieve value or NULL
hashmap_remove(map, key): delete entry
hashmap_free(map): free map and invoke your free functions
Iteration: hashmap_iter(), hashmap_next(), hashmap_iter_free()

For advanced usage (custom allocators, resizing thresholds), see the full API in hashmap.h.

Advanced Usage & Customization

This section covers power-user patterns: custom hashing/comparison, memory allocators, load-factor tuning, iteration, and thread-safety.

Custom Hash and Compare Functions

Provide tailored hash/compare callbacks for non-trivial key types or performance tuning.

Example: Composite Key with xxHash3

#include "hashmap.h"
#include <string.h>

// Composite key type
typedef struct {
    uint32_t id;
    char    *name;
} user_key;

// xxhash3-based hash: combines id and name
uint64_t user_hash(const void *item, uint64_t seed0, uint64_t seed1) {
    const user_key *k = item;
    // hash id
    uint64_t h = hashmap_xxhash3(&k->id, sizeof(k->id), seed0, seed1);
    // mix in name
    return hashmap_xxhash3(k->name, strlen(k->name), h, seed1);
}

// Compare id then name
int user_cmp(const void *a, const void *b, void *udata) {
    (void)udata;
    const user_key *x = a, *y = b;
    if (x->id != y->id) return (int)x->id - (int)y->id;
    return strcmp(x->name, y->name);
}

// Optional cleanup for name
void user_free(void *item) {
    free(((user_key*)item)->name);
}

// Create map
struct hashmap *map = hashmap_new(
    sizeof(user_key), 128,           // element size, initial buckets
    0xCAFEBABEDEADBEEFULL,            // seed0
    0xFACEFEED12345678ULL,            // seed1
    user_hash,                        // custom hash
    user_cmp,                         // custom compare
    user_free,                        // element cleanup
    NULL                              // compare user data
);

Custom Memory Allocators

Supply custom malloc/realloc/free on a per-map basis to integrate with memory pools, debuggers, or failure injection.

#include "hashmap.h"

// Custom pool routines
void *pool_malloc(size_t sz);
void *pool_realloc(void *p, size_t sz);
void  pool_free(void *p);

// Create a map using pool allocators
struct hashmap *pool_map = hashmap_new_with_allocator(
    pool_malloc,    // malloc
    pool_realloc,   // realloc
    pool_free,      // free
    sizeof(int),    // element size
    256,            // initial capacity
    0x1111222233334444ULL, // seed0
    0x5555666677778888ULL, // seed1
    NULL,           // default hash (FNV-1a)
    NULL,           // default compare (memcmp)
    NULL,           // no per-element free
    NULL            // no compare user data
);

Notes

Passing NULL allocator falls back to global or stdlib.
Set allocators before any hashmap_new* call.

Controlling Load Factor

Adjust the load-factor threshold to balance memory usage and probe length.

#include "hashmap.h"

int main(void) {
    struct hashmap *m = hashmap_new(
        sizeof(int),  64,
        0, 0,
        NULL, NULL, NULL, NULL
    );
    // Force resize when ≥50% full
    hashmap_set_max_load_factor(m, 0.5);
    // ...
    hashmap_free(m);
    return 0;
}

Key Points

Default max load ≈0.85.
Lower load ⇒ fewer probes, more memory; higher load ⇒ more memory-efficient, longer probes.

Iterating Over Items

Use the built-in iterator to scan all elements without exposing internals.

#include "hashmap.h"
#include <stdio.h>

void print_map(struct hashmap *m) {
    user_key entry;
    struct hashmap_iter it;
    hashmap_iter_init(m, &it);
    while (hashmap_iter_next(&it, &entry)) {
        printf("id=%u name=%s\n", entry.id, entry.name);
    }
}

int main(void) {
    // assume map populated
    print_map(map);
    return 0;
}

Iterator API

void hashmap_iter_init(const struct hashmap *map, struct hashmap_iter *it)
int hashmap_iter_next(struct hashmap_iter *it, void *out) returns 1 if an element is written to out, 0 at end.

Thread-Safety Considerations

hashmap is not internally synchronized. Coordinate concurrent access with external locks.

#include "hashmap.h"
#include <pthread.h>

static pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
static struct hashmap *shared_map;

void thread_safe_set(const user_key *k) {
    pthread_mutex_lock(&mtx);
    hashmap_set(shared_map, k);
    pthread_mutex_unlock(&mtx);
}

user_key thread_safe_get(const user_key *k) {
    pthread_mutex_lock(&mtx);
    const user_key *res = hashmap_get(shared_map, k);
    user_key copy = res ? *res : (user_key){0};
    pthread_mutex_unlock(&mtx);
    return copy;
}

// For read-only access after full construction, you may omit locks.

Recommendations

Serialize writes with a mutex or read-write lock.
After population, concurrent reads (hashmap_get) are safe without locks.

API Reference

Concise, alphabetical reference for every public function, macro, typedef, and struct in hashmap.h.

Macros

HM_INITIAL_CAPACITY

Default bucket count for a new hashmap.
Type: size_t
Value: 16

HM_LOAD_FACTOR

Maximum load factor before automatic resizing.
Type: double
Value: 0.75

Typedefs

hm_alloc_fn

Signature: void *(*)(size_t size)
Custom allocator for internal memory.

hm_cmp_fn

Signature: int (*)(const void *a, const void *b)
Returns non-zero if keys a and b are equal.

hm_free_fn

Signature: void (*)(void *ptr)
Custom deallocator for internal memory.

hm_hash_fn

Signature: size_t (*)(const void *key)
Computes hash code for a given key.

Structs

struct hm_hashmap

Opaque handle for a hashmap instance.
Fields (internal):

buckets array of key/value slots
size current entry count
capacity current bucket count
hash_fn, cmp_fn, alloc_fn, free_fn function pointers

struct hm_iter

Iterator state for traversing a hashmap.
Fields (internal):

map pointer to target hm_hashmap
index current bucket index

Functions

hm_clear

Remove all entries from a hashmap.
Signature:

void hm_clear(hm_hashmap *map);

Parameters:

map — pointer to target hashmap.
Returns: nothing.

hm_free

Destroy a hashmap and release all resources.
Signature:

void hm_free(hm_hashmap *map);

Parameters:

map — pointer to target hashmap.
Returns: nothing.

hm_get

Retrieve a value by key.
Signature:

void *hm_get(const hm_hashmap *map, const void *key);

Parameters:

map — pointer to target hashmap.
key — lookup key.
Returns:
pointer to stored value, or NULL if not found.

hm_iter_init

Initialize an iterator for a hashmap.
Signature:

void hm_iter_init(const hm_hashmap *map, hm_iter *iter);

Parameters:

map — pointer to target hashmap.
iter — pointer to iterator state.
Returns: nothing.

hm_iter_next

Advance iterator and retrieve next key/value pair.
Signature:

int hm_iter_next(hm_iter *iter, const void **key, void **value);

Parameters:

iter — pointer to initialized iterator.
key — output pointer for next key.
value — output pointer for next value.
Returns:
1 if a pair was returned, 0 if iteration is complete.

hm_new

Create a new hashmap with custom callbacks.
Signature:

hm_hashmap *hm_new(
    hm_hash_fn hash_fn,
    hm_cmp_fn cmp_fn,
    hm_alloc_fn alloc_fn,
    hm_free_fn free_fn,
    size_t initial_capacity
);

Parameters:

hash_fn — key hashing function.
cmp_fn — key comparison function.
alloc_fn — memory allocation function.
free_fn — memory deallocation function.
initial_capacity — starting number of buckets (use HM_INITIAL_CAPACITY).
Returns:
pointer to new hm_hashmap, or NULL on allocation failure.

hm_remove

Delete an entry by key.
Signature:

int hm_remove(hm_hashmap *map, const void *key);

Parameters:

map — pointer to target hashmap.
key — key to remove.
Returns:
1 if key was found and removed, 0 otherwise.

hm_resize

Manually adjust the bucket count.
Signature:

int hm_resize(hm_hashmap *map, size_t new_capacity);

Parameters:

map — pointer to target hashmap.
new_capacity — desired bucket count.
Returns:
1 on success, 0 on allocation failure.

hm_set

Insert or update an entry.
Signature:

int hm_set(hm_hashmap *map, const void *key, void *value);

Parameters:

map — pointer to target hashmap.
key — pointer to entry key.
value — pointer to entry value.
Returns:
1 if a new key was inserted, 0 if an existing key was updated, -1 on failure.

hm_size

Return the number of entries in a hashmap.
Signature:

size_t hm_size(const hm_hashmap *map);

Parameters:

map — pointer to target hashmap.
Returns:
current entry count.

Documentation

Contents

Quick Actions

Contents

Quick Actions

Chat about this codebase

Chat about this codebase

Project Overview

Key Features

Performance Characteristics

When to Choose This Library

Quick Start Example

Common Operations

Advanced Usage & Customization

Custom Hash and Compare Functions

Example: Composite Key with xxHash3

Custom Memory Allocators

Controlling Load Factor

Iterating Over Items

Thread-Safety Considerations

API Reference

Macros

HM_INITIAL_CAPACITY

HM_LOAD_FACTOR

Typedefs

hm_alloc_fn

hm_cmp_fn

hm_free_fn

hm_hash_fn

Structs

struct hm_hashmap

struct hm_iter

Functions

hm_clear

hm_free

hm_get

hm_iter_init

hm_iter_next

hm_new

hm_remove

hm_resize

hm_set

hm_size