From 44528c546359a95c57e8a0e4b3703c5086b15f24 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Thu, 22 Oct 2009 12:58:41 -0700 Subject: [PATCH] hash: Improve hash function for integers. As previously defined, the following both returned the same value for given values of 'basis': hash_int(0, hash_int(1, basis)) hash_int(1, hash_int(0, basis)) because hash_int(0, basis) evaluated to basis and hash_int(1, basis) evaluated to c + basis for some constant c. This commit fixes the problem, by eliminating any simple linear relationship between basis and the hash value. We should write some tests for hash function quality. --- lib/hash.h | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/lib/hash.h b/lib/hash.h index 33c5c427..3f140381 100644 --- a/lib/hash.h +++ b/lib/hash.h @@ -65,10 +65,11 @@ static inline uint32_t hash_int(uint32_t x, uint32_t basis) x ^= x >> 17; x -= x << 9; x ^= x << 4; + x += basis; x -= x << 3; x ^= x << 10; x ^= x >> 15; - return x + basis; + return x; } /* An attempt at a useful 1-bit hash function. Has not been analyzed for -- 2.30.2