From 8a7de364639c23d6a08ee07698f7a04b499ccdc5 Mon Sep 17 00:00:00 2001 From: PeterN Date: Sat, 19 May 2018 22:04:25 +0100 Subject: Change [#6689]: Tweak HashTable hash calculation to reduce collisions. (kernigh2) (#6786) --- src/misc/hashtable.hpp | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-) diff --git a/src/misc/hashtable.hpp b/src/misc/hashtable.hpp index 1afe58cac..1078f1861 100644 --- a/src/misc/hashtable.hpp +++ b/src/misc/hashtable.hpp @@ -161,12 +161,10 @@ protected: /** static helper - return hash for the given key modulo number of slots */ inline static int CalcHash(const Tkey &key) { - int32 hash = key.CalcHash(); - if ((8 * Thash_bits) < 32) hash ^= hash >> (min(8 * Thash_bits, 31)); - if ((4 * Thash_bits) < 32) hash ^= hash >> (min(4 * Thash_bits, 31)); - if ((2 * Thash_bits) < 32) hash ^= hash >> (min(2 * Thash_bits, 31)); - if ((1 * Thash_bits) < 32) hash ^= hash >> (min(1 * Thash_bits, 31)); - hash &= (1 << Thash_bits) - 1; + uint32 hash = key.CalcHash(); + hash -= (hash >> 17); // hash * 131071 / 131072 + hash -= (hash >> 5); // * 31 / 32 + hash &= (1 << Thash_bits) - 1; // modulo slots return hash; } -- cgit v1.2.3-54-g00ecf