From ab6255393d7a983ae3d008f13c1350cf56d32c33 Mon Sep 17 00:00:00 2001 From: "Peter H. Froehlich" Date: Sun, 2 Nov 2014 22:27:45 -0500 Subject: BB#110 Replace hash function with Dan Bernstein's. This hash function distributes much better than the original one. The effect is not as visible with hashes taken modulo 32 than with a bigger modulus, but it is there. And larger number of buckets migh become possible in the future... Reviewed-by: Michael Adam --- src/hashmap.c | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-) diff --git a/src/hashmap.c b/src/hashmap.c index f46fdcb..0c911a8 100644 --- a/src/hashmap.c +++ b/src/hashmap.c @@ -63,6 +63,9 @@ struct hashmap_s { * The contents of the key are converted to lowercase, so this function * is not case-sensitive. * + * This is Dan Bernstein's hash function as described, for example, here: + * http://www.cse.yorku.ca/~oz/hash.html + * * If any of the arguments are invalid a negative number is returned. */ static int hashfunc (const char *key, unsigned int size) @@ -74,12 +77,8 @@ static int hashfunc (const char *key, unsigned int size) if (size == 0) return -ERANGE; - for (hash = tolower (*key++); *key != '\0'; key++) { - uint32_t bit = (hash & 1) ? (1 << (sizeof (uint32_t) - 1)) : 0; - - hash >>= 1; - - hash += tolower (*key) + bit; + for (hash = 5381; *key != '\0'; key++) { + hash = ((hash << 5) + hash) ^ tolower (*key); } /* Keep the hash within the table limits */ -- cgit v1.2.3