summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJustus Winter <4winter@informatik.uni-hamburg.de>2014-05-08 15:45:00 +0200
committerJustus Winter <4winter@informatik.uni-hamburg.de>2014-05-13 19:08:50 +0200
commit2d898893815a980f1b821fcec267eb8e7ded678e (patch)
tree470a45c1871b6914d8af224fa99838159b0cef65
parent6dcf53606fc7d46447176aab15954a897e19d6e5 (diff)
libihash: use an integer hash function on the keys
Use an integer hash function to derive the index from the key. This should reduce the number of collisions. * libihash/ihash.c (hash_int32): New function. (find_index): Use hash_int32 on the key to derive the index. (add_one): Likewise.
-rw-r--r--libihash/ihash.c17
1 files changed, 15 insertions, 2 deletions
diff --git a/libihash/ihash.c b/libihash/ihash.c
index d670fee2..71ddc26d 100644
--- a/libihash/ihash.c
+++ b/libihash/ihash.c
@@ -81,6 +81,19 @@ static const unsigned int ihash_nsizes = (sizeof ihash_sizes
/ sizeof ihash_sizes[0]);
+/* This is the integer finalizer from MurmurHash3. */
+static inline uint32_t
+murmur3_mix32 (uint32_t h, unsigned int bits)
+{
+ h ^= h >> 16;
+ h *= 0x85ebca6b;
+ h ^= h >> 13;
+ h *= 0xc2b2ae35;
+ h ^= h >> 16;
+
+ return h >> (32 - bits);
+}
+
/* Return 1 if the slot with the index IDX in the hash table HT is
empty, and 0 otherwise. */
static inline int
@@ -111,7 +124,7 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
unsigned int up_idx;
unsigned int down_idx;
- idx = key % ht->size;
+ idx = murmur3_mix32 (key, 32) % ht->size;
if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key)
return idx;
@@ -264,7 +277,7 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key, hurd_ihash_value_t value)
unsigned int idx;
unsigned int first_free;
- idx = key % ht->size;
+ idx = murmur3_mix32 (key, 32) % ht->size;
first_free = idx;
if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key)