# hashmap.c is a hash map in two files of C

> The hashmap.c project is a generic hash table with open addressing and Robin Hood hashing, built in SipHash, MurmurHash3 and xxHash, with custom allocators and no external dependencies. What makes it worth reading is not the table but the contract in the documentation, which is unusually explicit about pointer invalidation and about where you have to put your locks.

**tidwall/hashmap.c** — Hash map implementation in C. 

- Repository: https://github.com/tidwall/hashmap.c
- Stars: 1,063 · Forks: 141
- Language: C
- License: MIT
- Published: 2026-10-19 · Updated: 2026-10-19 · Language: en
- Canonical page: https://hysenlabs.com/projects/tidwall-hashmap-c

## A whole data structure in two files

The repository listing is as short as it gets: a LICENSE file, the README, a .gitignore, a .package file, hashmap.c and hashmap.h. There is no build system, no dependency, no subproject, and the primary language is C.

The feature list is what makes it interesting. It is an open addressing implementation using Robin Hood hashing, with a generic interface that supports variable sized items. It has built in SipHash, MurmurHash3 and xxHash, and it allows alternative algorithms. It supports C99 and up, it supports custom allocators, and the performance claim in the readme is characteristically understated, calling it pretty darn good performance.

Two of those deserve a word each. Variable sized items is the design decision that makes the library generic: the map stores a fixed size record of a size you declare up front, and the record is yours to design, so it can hold a key and a value of any shape. Custom allocators matter in a different way, because a C data structure that always calls malloc cannot be used in a program that has its own memory management, and cannot be tested without wrapping the allocator.

The open addressing with Robin Hood hashing choice is about how the table handles collisions. Instead of chaining, every entry lives in an array, and the Robin Hood rule makes insertion order matter: an entry that would travel further than the one before it moves along, which keeps probe sequences short and reduces clustering.

The audience is a C developer who needs a hash table and does not want a dependency, and who is comfortable with the trade-offs that a hand written table implies, which are spelled out in the documentation and are not small.

## You supply the hash and the compare function

The library does not know anything about your data, and the API is shaped around that fact.

The documentation describes an item as a structure of your design that contains a key and a value. You load your structure with the key and value and set it in the table, which copies the contents of your structure into a bucket in the table. When you get an item out, you load your structure with the key data, call hashmap_get, and it looks up the key and returns a pointer to the item stored in the bucket. The passed in item is not modified.

So the contract is three callbacks. You must provide compare and hash functions which access the structure's key properly, and if you want to use hashmap_scan you must also provide an iter function. For the hash function you are welcome to call one of the supplied hash functions, passing the key in your structure.

The example in the readme shows all three. A compare function that casts both pointers to the item type and calls strcmp on the name field. An iter function that prints the item and returns true. And a hash function that casts to the item and calls hashmap_sip on the name with its length and the two seeds.

The constructor makes the shape clear:

```c
struct hashmap *map = hashmap_new(sizeof(struct user), 0, 0, 0, 
                                 user_hash, user_compare, NULL, NULL);
```

The first argument is the size of the item, the second is the initial capacity, and the third and fourth are the optional seeds that are passed to the hash function. The last two are the extra callbacks, null in the example.

The API surface is short. The basic functions are hashmap_new, hashmap_free, hashmap_count, hashmap_set, hashmap_get, hashmap_delete and hashmap_clear, where set inserts or replaces an existing item and returns the previous one, and delete deletes and returns an item. Iteration comes in two forms, hashmap_iter for a loop based walk and hashmap_scan for a callback based walk. And the hash helpers are hashmap_sip for SipHash-2-4 and hashmap_murmur for MurmurHash3.

## The pointer rule is the whole contract

There is a paragraph in the API Notes that changes how you write the calling code, and it is worth reading twice.

The functions hashmap_get, hashmap_set and hashmap_delete all return a pointer to an item if found. In all cases the pointer is not guaranteed to continue to point to that same item after subsequent calls to the hashmap. The hashmap can be rearranged by a subsequent call, which can render previously returned pointers invalid, possibly even pointing into freed heap space. The documentation does not soften this: DO NOT RETAIN POINTERS RETURNED BY HASHMAP CALLS. It is common to copy the contents of the item into your storage immediately following a call that returns an item pointer.

So the rule is that a pointer from this API is a loan, not a reference. It is valid until the next call on the same map, and the fix is not a defensive copy somewhere later but a copy at the point of the call.

There is a second property in the same section, and it is the one that catches memory bugs. If your element structure contains pointers, those pointer values are copied into the buckets, so it is a shallow copy of the item, not a deep copy. Anything your entry points to must be maintained for the lifetime of the item in the table. The library copies the record, and the record contains a pointer, so the pointer now refers to memory the map knows nothing about. If the caller frees that memory while the item is still in the table, the map is holding a dangling reference, and nothing in the library will notice.

Together, these two notes describe the entire safety story of the library. The map manages the record, it does not manage anything the record points to, and it can move the record at any time.

## Locking has to wrap the call, not the internals

The documentation is blunt about threading. NOT THREAD SAFE. If you are using hashmap with multiple threads, you must provide locking to prevent concurrent calls.

Then comes the part that is easy to get wrong, and the documentation explains why. It is not sufficient to add the locks to the hashmap code itself. The reason is the pointer rule again. The hashmap calls return pointers to internal structures, which can become invalid after subsequent calls to hashmap. So if you add a lock inside the hashmap functions, by the time the pointer is returned to the caller, that pointer may have already been rendered invalid by another thread's call.

The prescription follows directly: you should lock before the call, make the call, copy out the result, and unlock.

That is a stronger requirement than most libraries impose, because it pushes the lock out to the call site, and it means every caller has to get it right. A wrapper type in your own codebase that does lock, call and copy is the obvious way to make that safe, and once you have it, the pointer invalidation problem disappears with it, because your wrapper never hands out a borrowed pointer at all.

So the design pushes you toward a particular usage. A single threaded program or a program with one owner of the map can use the library as it is, and a concurrent program needs a thin layer over it. That layer is about twenty lines, and the documentation tells you exactly what it has to do.

## You can run the tests and the benchmarks yourself

The testing and benchmarks section gives two commands, and they need no build system at all.

```sh
$ cc -DHASHMAP_TEST hashmap.c && ./a.out              # run tests
$ cc -DHASHMAP_TEST -O3 hashmap.c && BENCH=1 ./a.out  # run benchmarks
```

A compile time flag switches the same source file into a test and benchmark binary, which is a neat trick for a library that wants to ship two files and nothing else.

The benchmark output in the readme also tells you what to expect and, more usefully, what the numbers mean. The benchmarks were run on a 2019 MacBook Pro, 2.4 GHz 8-Core Intel Core i9, using gcc-9. The items are simple 4-byte ints, the hash function is MurmurHash3, and the test set is 5,000,000 items. The rows marked (cap) are hashmaps created with an initial capacity of 5,000,000, and the rest are grown from nothing.

That is the interesting comparison in the table. Set costs 142 ns per op and 26.84 bytes per op when the map is grown dynamically, and 86 ns per op when the capacity is known up front, and the same pattern holds for delete, 97 ns against 82 ns. Get is 61 ns per op in both cases, because a lookup does not touch the empty space the difference in insertion cost buys.

So the practical lesson from the numbers is that a map that grows under you is paying for rehashes, and if you can predict the size, telling the map up front is cheaper. That is a design decision for the caller, and it is one you would not get from the API names alone.

## Where a hash table in C is the wrong tool

There is a clear line here, and it is about how much of the standard library your target platform already gives you.

If you are writing C for a platform with a working hash table, or with a dynamic array and a sort, then this library buys you a faster lookup and a smaller dependency footprint, and that is genuinely worth it in a hot loop or on a constrained system. If your program already links something that provides ordered maps, then the same choice buys you nothing, and what you are really choosing is between a hash table that does not keep its keys in order and one that does, which is a real functional difference in a program that iterates predictably.

The second limit is the pointer model. A map that returns borrowed pointers into its own storage and can move them on the next call is a library for a program that copies values out. It is not a library for a program that wants to hold references to items in the map, and it is not a library for a program with concurrent access without a wrapper layer of your own.

And the third is the generic interface itself. The item is a fixed size record that you design, and the key is found by your compare function. That is a good fit for a key and a value in one struct, which is what most maps need. It is a bad fit if your key changes, or if you need to store items of different sizes in one table, or if you want the map to own the value and free it on delete, because the shallow copy rule means the memory management of the value stays entirely with you.

None of that is a flaw in the library. It is a clear contract, written down carefully, and the surprise would be if the documentation had not said it.

## Conclusion

hashmap.c is worth adopting when you are writing C and need a hash table with variable sized items, a hash function you control, and no dependencies, because the whole implementation is two files you can read in an afternoon and the API notes tell you exactly where the sharp edges are. It is the wrong choice if you need thread safety out of the box, because the documentation states plainly that it is not thread safe and that locking must wrap the call rather than the internals. Before you adopt it, read the API Notes section in full, because the rule about not retaining returned pointers is the one that turns into a use after free, and note that the last push was on 2026-07-01.

## FAQ

### What is hashmap.c and what hashing does it use?

It is a MIT licensed hash map implementation in C that uses open addressing with Robin Hood hashing and supports variable sized items through a generic interface. SipHash, MurmurHash3 and xxHash are built in, and alternative algorithms can be supplied.

### How do I use hashmap.c with my own data type?

You define a struct holding your key and value, then pass its size, an initial capacity, two seeds, a hash function and a compare function to hashmap_new. If you want to use hashmap_scan you also provide an iter function, and you can call hashmap_sip or hashmap_murmur on your key from your own hash function.

### Is it safe to keep a pointer returned by hashmap_get?

No. The documentation states that hashmap_get, hashmap_set and hashmap_delete return a pointer to an item if found, but that the pointer is not guaranteed to keep pointing to that same item after subsequent calls, because the hashmap can be rearranged and the pointer may end up pointing into freed heap space. The advice is to copy the contents of the item into your storage immediately after the call.

### Is hashmap.c thread safe?

No, the documentation states NOT THREAD SAFE and that you must provide locking yourself. Adding locks inside the hashmap functions is not sufficient, because the returned pointer may already be invalid by the time the caller sees it, so the guidance is to lock before the call, make the call, copy out the result and unlock.

### How do I run the hashmap.c tests and benchmarks?

Compile the source with a compiler and the HASHMAP_TEST define, for example cc -DHASHMAP_TEST hashmap.c and run the result, and add -O3 with the BENCH=1 environment variable to run the benchmarks instead of the tests.

## Sources

- [Issues](https://github.com/tidwall/hashmap.c/issues)
- [License: MIT](https://github.com/tidwall/hashmap.c/blob/master/LICENSE)
- [README](https://github.com/tidwall/hashmap.c/blob/master/README.md)
- [tidwall/hashmap.c on GitHub](https://github.com/tidwall/hashmap.c)

---

Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/tidwall-hashmap-c