diff options
| author | Peter H. Froehlich <peter.hans.froehlich@gmail.com> | 2014-11-02 22:27:45 -0500 |
|---|---|---|
| committer | Michael Adam <obnox@samba.org> | 2014-12-13 01:20:56 +0100 |
| commit | ab6255393d7a983ae3d008f13c1350cf56d32c33 (patch) | |
| tree | bdf2848b252805f383813e8dfceeb4dd1c4bed61 /src/hashmap.c | |
| parent | 24087f743ae321e76430c171a69e86e8a9726382 (diff) | |
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 <obnox@samba.org>
Diffstat (limited to 'src/hashmap.c')
| -rw-r--r-- | src/hashmap.c | 11 |
1 files 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 */ |