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.
"08-10-12 - cbhashtable"
No comments yet. -