Zilong Tan has kindly shared his observation that using a power-of-2 bucket count may dramatically improve the speed for integer keys. He implemented this idea in his ulib library. He is right. Here is a tiny benchmark done on my laptop (Intel Core 2 Duo; Mac OS X 10.6; gcc 4.2.1; program khash_test.c).
where “0.2.6” is the new version and “0.2.6 linear” indicates that linear probing is in use (by default, khash uses double hashing for stability). We can see that 0.2.6 is nearly twice as fast as 0.2.5 for integer hash set. Linear probing is even faster than the default double hashing due to the better cache performance and a little fewer CPU instructions, but double hashing tends to be more robust to certain non-random input.
The new version is available here.
Update: Note that due to rehashing the performance of a hash table as a function of input size is not a smooth curve. Rehashing may take time. Thus I added two more data points to show that the speedup is not due to this caveat.