08-10-12 - cbhashtable

cbhashtable is a single file standalone hash table. It is a power-of-two-size reprobing hash table (aka "open addressing" or "closed hashing") which uses special values for empty & deleted slots (not separate flags). It optionally stores the hash value in the table to accelerate finding when the key comparison is slow.

Download : cbhashtable.h at cbloom.com

cbhashtable was ripped out of cblib . I recently improved the cblib version so that the hash table entries can be {hash,key,data} or {hash,data} (key==data) or {key,data} (no stored hash) or just {data} (key==data and no stored hash). (or whatever you want I guess, though those are the only 4 that make sense I think).

cbhashtable is built on a vector to store its entries; you can use std::vector, or your own, or use cbvector .

See previous posts on hash tables :

cbloom rants 10-17-08 - 1
cbloom rants 10-19-08 - 1
cbloom rants 10-21-08 - 4
cbloom rants 10-21-08 - 5
cbloom rants 11-23-08 - Hashing & Cache Line Size
cbloom rants 11-19-10 - Hashes and Cache Tables
cbloom rants 11-29-10 - Useless hash test

Commentary :

I'm pretty happy with the implementation of cbhashtable now, but setting it up is still a bit awkward. (using it once its set up is fine). You have to create an "ops" functor which knows how to make & detect the special empty & deleted keys. I may try to improve this some day.