uthash User Guide

This software supports these operations on items in a hash table:

Add, find and delete are normally constant-time operations. This is influenced by your key domain and the hash function.

This hash aims to be minimalistic and efficient. It’s around 900 lines of C. It inlines automatically because it’s implemented as macros. It’s fast as long as the hash function is suited to your keys. You can use the default hash function, or easily compare performance and choose from among several other built-in hash functions.

No, it’s just a single header file: uthash.h. All you need to do is copy the header file into your project, and:

Since uthash is a header file only, there is no library code to link against.

This software can be used in C and C++ programs. It has been tested on:

Windows users: as of 2013 it’s been a while since I had the environment to test uthash under Visual Studio. If someone wants to run the unit tests under the latest Visual Studio and confirm that its still clean, that’d be appreciated.

This software is made available under the revised BSD license. It is free and open source.

Follow the links on https://github.com/troydhanson/uthash to clone uthash or get a zip file.

I encourage people to use the public Google Group to ask questions:

You can browse it at:

If you are experienced with uthash and like to answer questions, please join the group and chime in when someone asks a question. That would be a great help!

If you add a new feature or fix something in uthash or in the extras, please make a pull request on Github. For anything other than a trivial change, include a unit test and documentation if you possibly can. (And don’t be discouraged if it takes weeks or even months for me to merge it. Sorry, my life is busy!) Thanks!

Three "extras" come with uthash. These provide lists, dynamic arrays and strings:

The author has a blog for software updates . You can also follow @troydhanson on Twitter for updates.

Uthash was downloaded around 30,000 times between 2006-2013 then transitioned to GitHub. It’s been incorporated into commercial software, academic research, and into other open-source software. It has also been added to the native package repositories for a number of Unix-y distros.

When uthash was written, there were fewer options for doing generic hash tables in C than exist today. There are faster hash tables, more memory-efficient hash tables, with very different API’s today. But, like driving a minivan, uthash is convenient, and gets the job done without drawing a lot of attention to itself.

There are no restrictions on the data type or name of the key field. The key can also comprise multiple contiguous fields, having any names and data types.

The UT_hash_handle field must be present in your structure. It is used for the internal bookkeeping that makes the hash work. It does not require initialization. It can be named anything, but you can simplify matters by naming it hh. This allows you to use the easier "convenience" macros to add, find and delete items.

Some have asked how uthash cleans up its internal memory. The answer is simple: when you delete the final item from a hash table, uthash releases all the internal memory associated with that hash table, and sets its pointer to NULL.

Your hash must be declared as a NULL-initialized pointer to your structure.

Allocate and initialize your structure as you see fit. The only aspect of this that matters to uthash is that your key must be initialized to a unique value. Then call HASH_ADD. (Here we use the convenience macro HASH_ADD_INT, which offers simplified usage for keys of type int).

The first parameter to HASH_ADD_INT is the hash table, and the second parameter is the name of the key field. Here, this is id. The last parameter is a pointer to the structure being added.

HASH_REPLACE macros are equivalent to HASH_ADD macros except they attempt to find and delete the item first. If it find and deletes and item, it will also return that items pointer as an output parameter.

To look up a structure in a hash, you need its key. Then call HASH_FIND. (Here we use the convenience macro HASH_FIND_INT for keys of type int).

Here, the hash table is users, and &user_id points to the key (an integer in this case). Last, s is the output variable of HASH_FIND_INT. The final result is that s points to the structure with the given key, or is NULL if the key wasn’t found in the hash.

To delete a structure from a hash, you must have a pointer to it. (If you only have the key, first do a HASH_FIND to get the structure pointer).

Here again, users is the hash table, and user is a pointer to the structure we want to remove from the hash.

The number of items in the hash table can be obtained using HASH_COUNT:

Incidentally, this works even the list (users, here) is NULL, in which case the count is 0.

You can loop over the items in the hash by starting from the beginning and following the hh.next pointer.

There is also an hh.prev pointer you could use to iterate backwards through the hash, starting from any known item.

We’ll repeat all the code and embellish it with a main() function to form a working example.

If this code was placed in a file called example.c in the same directory as uthash.h, it could be compiled and run like this:

Follow the prompts to try the program.

This program is included in the distribution in tests/example.c. You can run make example in that directory to compile it easily.

The preceding examples demonstrated use of integer keys. To recap, use the convenience macros HASH_ADD_INT and HASH_FIND_INT for structures with integer keys. (The other operations such as HASH_DELETE and HASH_SORT are the same for all types of keys).

If your structure has a string key, the operations to use depend on whether your structure points to the key (char *) or the string resides within the structure (char a[10]). This distinction is important. As we’ll see below, you need to use HASH_ADD_KEYPTR when your structure points to a key (that is, the key itself is outside of the structure); in contrast, use HASH_ADD_STR for a string key that is contained within your structure.

Your key can be a pointer. To be very clear, this means the pointer itself can be the key (in contrast, if the thing pointed to is the key, this is a different use case handled by HASH_ADD_KEYPTR).

Here is a simple example where a structure has a pointer member, called key.

This example is included in tests/test57.c. Note that the end of the program deletes the element out of the hash, (and since no more elements remain in the hash), uthash releases its internal memory.

Your key field can have any data type. To uthash, it is just a sequence of bytes. Therefore, even a nested structure can be used as a key. We’ll use the general macros HASH_ADD and HASH_FIND to demonstrate.

This usage is nearly the same as use of a compound key explained below.

Note that the general macros require the name of the UT_hash_handle to be passed as the first argument (here, this is hh). The general macros are documented in Macro Reference.

Your key can even comprise multiple contiguous fields.

This example is included in the distribution in tests/test22.c.

If you use multi-field keys, recognize that the compiler pads adjacent fields (by inserting unused space between them) in order to fulfill the alignment requirement of each field. For example a structure containing a char followed by an int will normally have 3 "wasted" bytes of padding after the char, in order to make the int field start on a multiple-of-4 address (4 is the length of the int).

When dealing with a multi-field key, you must zero-fill your structure before HASH_ADD'ing it to a hash table, or using its fields in a HASH_FIND key.

In the previous example, memset is used to initialize the structure by zero-filling it. This zeroes out any padding between the key fields. If we didn’t zero-fill the structure, this padding would contain random values. The random values would lead to HASH_FIND failures; as two "identical" keys will appear to mismatch if there are any differences within their padding.

A multi-level hash table arises when each element of a hash table contains its own secondary hash table. There can be any number of levels. In a scripting language you might see:

The C program below builds this example in uthash: the hash table is called items. It contains one element (bob) whose own hash table contains one element (age) with value 37. No special functions are necessary to build a multi-level hash table.

While this example represents both levels (bob and age) using the same structure, it would also be fine to use two different structure definitions. It would also be fine if there were three or more levels instead of two.

The example above is included in tests/test59.c.

A structure can be added to more than one hash table. A few reasons you might do this include:

Your structure needs to have a UT_hash_handle field for each hash table to which it might be added. You can name them anything. E.g.,

You might create a hash table keyed on an ID field, and another hash table keyed on username (if usernames are unique). You can add the same user structure to both hash tables (without duplication of the structure), allowing lookup of a user structure by their name or ID. The way to achieve this is to have a separate UT_hash_handle for each hash to which the structure may be added.

In the example above, the structure can now be added to two separate hash tables. In one hash, id is its key, while in the other hash, username is its key. (There is no requirement that the two hashes have different key fields. They could both use the same key, such as id).

Notice the structure has two hash handles (hh1 and hh2). In the code below, notice that each hash handle is used exclusively with a particular hash table. (hh1 is always used with the users_by_id hash, while hh2 is always used with the users_by_name hash table).

It comes as no suprise that two hash tables can have different sort orders, but this fact can also be used advantageously to sort the same items in several ways. This is based on the ability to store a structure in several hash tables.

Extending the previous example, suppose we have many users. We have added each user structure to the users_by_id hash table and the users_by_name hash table. (To reiterate, this is done without the need to have two copies of each structure). Now we can define two sort functions, then use HASH_SRT.

Now iterating over the items in users_by_id will traverse them in id-order while, naturally, iterating over users_by_name will traverse them in name-order. The items are fully forward-and-backward linked in each order. So even for one set of users, we might store them in two hash tables to provide easy iteration in two different sort orders.

Programs that generate a fair miss rate (HASH_FIND that result in NULL) may benefit from the built-in Bloom filter support. This is disabled by default, because programs that generate only hits would incur a slight penalty from it. Also, programs that do deletes should not use the Bloom filter. While the program would operate correctly, deletes diminish the benefit of the filter. To enable the Bloom filter, simply compile with -DHASH_BLOOM=n like:

where the number can be any value up to 32 which determines the amount of memory used by the filter, as shown below. Using more memory makes the filter more accurate and has the potential to speed up your program by making misses bail out faster.

Bloom filters are only a performance feature; they do not change the results of hash operations in any way. The only way to gauge whether or not a Bloom filter is right for your program is to test it. Reasonable values for the size of the Bloom filter are 16-32 bits.

An experimental select operation is provided that inserts those items from a source hash that satisfy a given condition into a destination hash. This insertion is done with somewhat more efficiency than if this were using HASH_ADD, namely because the hash function is not recalculated for keys of the selected items. This operation does not remove any items from the source hash. Rather the selected items obtain dual presence in both hashes. The destination hash may already have items in it; the selected items are added to it. In order for a structure to be usable with HASH_SELECT, it must have two or more hash handles. (As described here, a structure can exist in many hash tables at the same time; it must have a separate hash handle for each one).

Now suppose we have added some users, and want to select just the administrator users who have id’s less than 1024.

The first two parameters are the destination hash handle and hash table, the second two parameters are the source hash handle and hash table, and the last parameter is the select condition. Here we used a macro is_admin() but we could just as well have used a function.

If the select condition always evaluates to true, this operation is essentially a merge of the source hash into the destination hash. Of course, the source hash remains unchanged under any use of HASH_SELECT. It only adds items to the destination hash selectively.

The two hash handles must differ. An example of using HASH_SELECT is included in tests/test36.c.

Internally, a hash function transforms a key into a bucket number. You don’t have to take any action to use the default hash function, currently Jenkin’s.

Some programs may benefit from using another of the built-in hash functions. There is a simple analysis utility included with uthash to help you determine if another hash function will give you better performance.

You can use a different hash function by compiling your program with -DHASH_FUNCTION=HASH_xyz where xyz is one of the symbolic names listed below. E.g.,

A utility called hashscan is included in the tests/ directory. It is built automatically when you run make in that directory. This tool examines a running process and reports on the uthash tables that it finds in that program’s memory. It can also save the keys from each table in a format that can be fed into keystats.

Here is an example of using hashscan. First ensure that it is built:

Since hashscan needs a running program to inspect, we’ll start up a simple program that makes a hash table and then sleeps as our test subject:

Now that we have a test program, let’s run hashscan on it:

If we wanted to copy out all its keys for external analysis using keystats, add the -k flag:

Now we could run ./keystats /tmp/9711-0.key to analyze which hash function has the best characteristics on this set of keys.

Internally this hash manages the number of buckets, with the goal of having enough buckets so that each one contains only a small number of items.

You don’t need to use these hooks- they are only here if you want to modify the behavior of uthash. Hooks can be used to change how uthash allocates memory, and to run code in response to certain internal events.

If a program that uses this hash is compiled with -DHASH_DEBUG=1, a special internal consistency-checking mode is activated. In this mode, the integrity of the whole hash is checked following every add or delete operation. This is for debugging the uthash software only, not for use in production code.

In the tests/ directory, running make debug will run all the tests in this mode.

In this mode, any internal errors in the hash data structure will cause a message to be printed to stderr and the program to exit.

The UT_hash_handle data structure includes next, prev, hh_next and hh_prev fields. The former two fields determine the "application" ordering (that is, insertion order-- the order the items were added). The latter two fields determine the "bucket chain" order. These link the UT_hash_handles together in a doubly-linked list that is a bucket chain.

Checks performed in -DHASH_DEBUG=1 mode:

You can use uthash in a threaded program. But you must do the locking. Use a read-write lock to protect against concurrent writes. It is ok to have concurrent readers (since uthash 1.5).

For example using pthreads you can create an rwlock like this:

Then, readers must acquire the read lock before doing any HASH_FIND calls or before iterating over the hash elements:

Writers must acquire the exclusive write lock before doing any update. Add, delete, and sort are all updates that must be locked.

If you prefer, you can use a mutex instead of a read-write lock, but this will reduce reader concurrency to a single thread at a time.

An example program using uthash with a read-write lock is included in tests/threads/test1.c.

The convenience macros do the same thing as the generalized macros, but require fewer arguments.

In order to use the convenience macros,

These macros add, find, delete and sort the items in a hash. You need to use the general macros if your UT_hash_handle is named something other than hh, or if your key’s data type isn’t int or char[].