Hash table based key/value dictionary in C++ with murmur hash function, linked list buckets in 200 LOC

hashdic.h -- suggested for direct include or copy paste to your project.

#include "string.h" // memcpy/memcmp

typedef __uint32_t u32;
typedef __int8_t i8;
typedef __uint8_t u8;

u32 MurMur(const char* key, int count) {
#define muR(x, r) (((x) << r) | ((x) >> (32 - r)))
u32 seed = 0x8e96a8f2;
int n = count >> 2;
u32 k, mur = seed, c1 = 0xcc9e2d51, c2 = 0x1b873593,
*b = (u32*) (key + n * 4);
for(int i = -n; i != 0; i++) {
k = (muR(b[i] * c1, 15) * c2);
mur = muR(mur^k, 13)*5+0xe6546b64;
}
u8 * tail = (u8*)(key + (n<<2));
k = 0;
switch(count & 3) {
case 3: k ^= tail[2] << 16;
case 2: k ^= tail[1] << 8;
case 1: k ^= tail[0];
k = mur ^ muR(k*c1,15)*c2;
}

mur ^= count;
mur ^= (mur ^ mur >> 16) * 0x85ebca6b >> 13;
return mur ^ (mur * 0xc2b2ae35 >> 16);
#undef muR
}

#define hash MurMur

int initial_size = 1024;
float growth_threshold = 2.0; //when to resize, for example 0.5 means "if number of inserted keys is half of table length then resize". My experiments on english dictionary shows balanced performance/memory savings with 1.0.
float growth_factor = 10; // grow the size of hash table by N, suggested number is between 2 (conserve memory) and 10 (faster insertions).

int dups = 0, resizes = 0, mem_count = 0, slots=0; // count some stats

typedef bool (*enumFunc)(void *key, int count, int *value, void *user);

template <typename value_t> struct jshash {
struct keynode {

char *key;
short len;
keynode *next;
value_t value;

keynode(char*k, int l) {
len = l;
key = new char[l];
memcpy(key, k, l);
next = 0;
value = -1;
}

~keynode() {
delete[] key;
mem_count += sizeof(keynode) + len;
if (next) delete next;
}

bool cmp(char*k, int l) {
if (len != l) return false;
return memcmp(key, k, l) == 0;
}
};

struct entry {
keynode *k;
entry():k(0) {}
~entry() {
mem_count += sizeof(entry);
if (k) delete k;
}
};

entry **table;
int length, count;

jshash() {
length = initial_size;
count = 0;
table = new entry*[initial_size]();
}

~jshash() {
for (int i = 0; i < length; i++) if (table[i]) delete table[i];
delete[] table;
mem_count += sizeof(entry*) * length;
}

void resize(int newsize) {
dups = 0; resizes++; slots = 0;
int o = length;
entry **old = table;
table = new entry*[newsize]();
length = newsize;
for (int i = 0; i < o; i++) {
if (old[i]) {
keynode *k = old[i]->k;
while (k) {
keynode *next = k->next;
k->next = 0;
reinsert_when_resizing(k);
k = next;
}
old[i]->k = 0;
}
delete old[i];
}
delete[] old;
}

value_t *result;

bool reinsert_when_resizing(keynode *k2) {
int h = (hash(k2->key, k2->len) >> 2);
int n = h % length;
if (table[n] == 0) {
slots++;
table[n] = new entry;
table[n]->k = k2;
result = &table[n]->k->value;
return false;
}
keynode *k = table[n]->k;
k2->next = table[n]->k;
table[n]->k = k2;
result = &k2->value;
return false;
}

bool add(void *key, int keyn) {
int h = (hash((const char*)key, keyn) >> 2);
int n = h % length;
if (table[n] == 0) {
slots++;
double f = (double)count / (double)length;
if (f > growth_threshold) {
resize(length * growth_factor);
}

table[n] = new entry;
table[n]->k = new keynode((char*)key, keyn);
result = &table[n]->k->value;
count++;
return false;
}
keynode *k = table[n]->k;
while (k) {
if (k->cmp((char*)key, keyn)) {
result = &k->value;
return true;
}
k = k->next;
}
dups++;
count++;
keynode *k2 = new keynode((char*)key, keyn);
k2->next = table[n]->k;
table[n]->k = k2;
result = &k2->value;
return false;
}

bool find(void *key, int keyn) {
int h = (hash((const char*)key, keyn) >> 2);
int n = h % length;
//      __builtin_prefetch(table[n]);
if (table[n] == 0) {
return false;
}
keynode *k = table[n]->k;
while (k) {
if (k->cmp((char*)key, keyn)) {
result = &k->value;
return true;
}
k = k->next;
}
return false;
}
/* Enumerate all inserted key/value pairs */
void forEach(enumFunc f, void *user) {
for (int i = 0; i < length; i++) {
if (table[i] != 0) {
keynode *k = table[i]->k;
while (k) {
if (!f(k->key, k->len, &k->value, user)) return;
k = k->next;
}
}
}
}
};


Example usage:

//clang++ hello.cpp -o hello
#include "iostream"
#include "hashdic.h"

using namespace std;

/*
enumeration callback
make sure you set right type for value and user data.
*/
bool callback(void *key, int count, int *value, void *user) {
cout << (char*)user << (char*) key << " = " << *value << endl;
return true;
}

int main() {
jshash<int> H; // specify your value type, (here int).

/*
Keys are void* (any binary data).
As you notice, there is no value parameter, you set it later.
*/

*H.result = 111; // set value of the most recent added/found pair

cout << "key already exists, modifying" << endl;
*H.result = 555;
}

*H.result = 777;

if (H.find((void*)"hello", 5))
cout << "hello = " << *H.result << endl;
else

if (H.find((void*)"there", 5))
cout << "there = " << *H.result << endl;
else

if (H.find((void*)"world", 5)) {
/*
find and update the value.
*/
*H.result += 1;
}

/*
just iterate over all entries.
user data can be zero (here string).
*/
H.forEach(callback, (char*)"for each: ");
}

• That's a breath taking title right there :P Any particular reason for the line limit? – glampert Jul 19 '15 at 5:45
• @glampert, thanks, not really a limit, just the actual value. But yes, less lines means easier to port to other language or adapt for any framework or environment. – exebook Jul 19 '15 at 9:21

I don't know the exact details about how hashtables work, neither do i know the murmur hash function, so i can't say anything about your algorithm but i'd like to comment your general code a little bit.

typedef __uint32_t u32;
typedef __int8_t i8;
typedef __uint8_t u8;


I personally would use the given typedefs in stdint.h. If you're used to those typedefs, there is nothing against it. But: Other programmers who read your source might not be used to it. Also, if you're not using a full IDE but a texteditor with highlighting (i love sublime), the highlighter does not analyze your code, this means it will not highlight u8, i8, u32 correctly, but it will highlight uint8_t, int8_t and uint32_t as types.

    #define muR(x, r) (((x) << r) | ((x) >> (32 - r)))


Use a function for that. Either declare it as inline, or just don't, the optimizer should inline it anyways. There is no (good) reason to use defines where a inlined function produces exactly the same code.

#define hash MurMur


This could go horribly wrong, and trust me, if it does, you won't find that bug. Either use UPPERCASE or don't use that define at all. Do you really need it?

   keynode(char*k, int l) {
len = l;
key = new char[l];
memcpy(key, k, l);
next = 0;
value = -1;
}


If you pass an invalid char*, this might leak. (I am actually not sure if it will ever return from memcpy) Use a vector<char> instead of the char*:

vector<char> key;
keynode(char*k, int l) {
len = l;
key.resize(l);
memcpy(&key[0], k, l);
next = 0;
value = -1;
}


TLDR: Raw pointers are hard to handle and it isn't necessary. std::vector, std::array, std::shared_ptr/unique_ptr are doing a great job handling this stuff for you.

typedef bool (*enumFunc)(void *key, int count, int *value, void *user);


I am almost sure, those c-like function typedefs don't allow a functor to be passed. Use a std::function<bool(void*,int,int*,void*)> instead to allow something like this:

H.forEach([&](void* key,int count,int* value, void* user){
//Do something. Since i pass all local variables as reference
// (with [&]) i can access every local variable from outside of this functor
}, (char*)"for each: ");


One last notice:

H.add((void*)"hello", 5);


Every pointer is implicit convertible to a void* in C++. It might warn you or error out, because a string-literal is a const char*, let your method take a const void* if it doesn't change the value. This helps to remove the unneeded casts to remove the const and allows better optimisation (the optimizer might see it itself that you don't change this value...). Also, C++ has its own casts. A (T*)something to remove a const becomes a const_cast<T*>(something). Not only is this the recommended way to cast in C++, also it lets the reader see exactly what you're doing. (Are you casting a void* to a T*? reinterpret_cast Tells you, you're changing the pointer type. Or just removing the constness? const_cast tells you, you're only removing the constness but keep the same type)

A few more things complementing the other reviews:

1. If you're aiming for portability, then the first thing to do is change the use of those compiler-specific types to the standard sized integer types of <cstdint>, as it was correctly suggested by @tkausl. Also note that in C++ those types are members of namespace std, so the correct portable usage would be, for instance: std::uint32_t. It is incidental that those types happen to be visible at the global scope due to the fact that compilers usually "recycle" the C header files for C++, so we can imagine a hypothetical C++-only compiler where those types would only be visible inside the std namespace.

2. Make sure to include the standard headers between < >, e.g.: #include <iostream>. By using double-quotes, you force the compiler to look first in the current working directory, which is a waste of compile-time.

3. Forgive my honesty, but those global variables are awful. I can understand the table having a couple stats counters, but then make those class members. The first three, initial_size, growth_threshold and growth_factor are clearly constants, so you should definitely make them static const, and also members of the class to avoid polluting the global scope.

4. Overall, your hash-table is implemented in a very C-ish way. Even though it is a template structure, I doubt it will function properly for non Plain Old Data - POD types, since you are memcopying and memcomping stuff. If that's really what you want, then I'd suggest adding a static assertion to make sure this class is not used accidentally on some non-POD type, yielding undefined behavior. You're using clang, so just enable C++11 with -std=c++11:

// Somewhere inside the declaration of jshash:
static_assert(std::is_pod<value_t>::value, "This container requires a POD type!");

5. The way find is implemented is also unusual. It doesn't return the requested value, but rather, sets and internal pointer with the result. That's counter-intuitive. Why not return the pointer if found and nullptr if not found? Or keep the boolean return and add an extra output parameter to the function, if you prefer.

6. Now I'm no hash-table guru, but I have implemented a hash-table before, and I didn't do that shifting by two on the result of my hash function:

int h = (hash(k2->key, k2->len) >> 2);
int n = h % length;


What exactly is the reason behind that? The modulo operator will properly wrap the hash to the size of the table, so why bring down the value first, possibly wasting valuable hash bits in the process?

7. The entry->keynode indirection seems useless, only forcing you to allocate memory twice at every new insertion, probably also making your CPU cache usage way less efficient than it could be, and adding more memory overhead per block.

8. The way mem_count is used seems suspicious. It starts as 0, but then you increment it whenever something is deallocated. By its name, I'd think it is counting the number of allocated bytes, but rather it seems to keep track of the number of deallocated bytes. If you keep it that way, a better name would be in order, if not, then it would make more sense for it to hold the number of bytes currently allocated.

9. I see that you are assigning zero to pointers. This is old-style C++. C++11 has been around for some time now and it's not even the most recent standard anymore, so you can start using nullptr instead.

10. You're missing the rule of three. Your struct can be copied by the implicit copy-constructor and assignment operator, resulting on shallow copies of the same object that share the same pointers. That would result in several destructors trying to free the same memory. Simplest possible fix is to disallow copy and assignment by either making the copy-constructor/operator private and unimplemented or by deleting them both.