The Google Dense Hashtable Library

Google dense hash table (google-dense) implements an open addressing hash table with quardric probing. It requires users to set an empty element and a deleted element which are distinct from all the other valid keys in the hash table. Google-dense tests whether a bucket is empty or deleted by performing key comparisons. It is fast [...]

Read Full Post »

Implementing Generic Hash Library in C

Synopsis
Here is an simple example showing how to use khash.h library:

#include "khash.h"
KHASH_MAP_INIT_INT(32, char)
int main() {
int ret, is_missing;
khiter_t k;
khash_t(32) *h = kh_init(32);
k = kh_put(32, h, 5, &ret);
if (!ret) kh_del(32, h, k);
kh_value(h, k) = 10;
k = kh_get(32, h, 10);
is_missing = (k == kh_end(h));
k = kh_get(32, h, 5);
kh_del(32, h, k);
for (k = kh_begin(h); k != kh_end(h); ++k)
if (kh_exist(h, [...]

Read Full Post »

Comparison of Hash Table Libraries

As a Perl programmer, I enjoy a lot using hash tables. I keep this habit in C/C++ programming. Then what C/C++ hash libraries are available? How are they compared to each other? In this post, I will give a brief review of hash libraries and present a small benchmark showing their practical performance.
Hash table libraries
In [...]

Read Full Post »