summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPeterN <peter@fuzzle.org>2018-05-19 22:04:25 +0100
committerGitHub <noreply@github.com>2018-05-19 22:04:25 +0100
commit8a7de364639c23d6a08ee07698f7a04b499ccdc5 (patch)
tree796e177d9fbe837e0d2e5feca3e3f255d8b6192e
parent7bd2fa351653b0140c82fcad96a0f3b16758a0b0 (diff)
downloadopenttd-8a7de364639c23d6a08ee07698f7a04b499ccdc5.tar.xz
Change [#6689]: Tweak HashTable hash calculation to reduce collisions. (kernigh2) (#6786)
-rw-r--r--src/misc/hashtable.hpp10
1 files 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;
}