Implement better hash functions for integer types

The hash function provides rather good mixing of the input bits.
It spreads numbers out evenly through the uint range, a change of
one bit in the input changes around half the output bits, and it is
pretty fast.

Using this as a hash function over the simple hash(int) == int has the
advantage that it reduces the amount of collisions for badly distributed
keys. In addition, it allows us to always use power of two sizes for the
hash table, leading to better performance for inserts and lookups.

the 32 and 64 bit hash functions where chosen from
https://nullprogram.com/blog/2018/07/31/. I selected the ones that give
a very good distribution of the hash values while using the integer for
both multiplication steps. This should be slighty faster than using two
different numbers.

While the result is still being cast to a uint, the method is prepared
so it can handle 64 bit keys and seeds.

Fixes: QTBUG-29009
Change-Id: Id7a1b97b3c0d219e65de2e6e1fe6faf092f8ce16
Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

1 files changed, 44 insertions, 14 deletions

diff --git a/src/corelib/tools/qhashfunctions.h b/src/corelib/tools/qhashfunctions.h
index 2ff3464912..2e62e93ac4 100644
--- a/src/corelib/tools/qhashfunctions.h
+++ b/src/corelib/tools/qhashfunctions.h
@@ -68,25 +68,55 @@ class QLatin1String;
 Q_CORE_EXPORT int qGlobalQHashSeed();
 Q_CORE_EXPORT void qSetGlobalQHashSeed(int newSeed);
 
-Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qHashBits(const void *p, size_t size, uint seed = 0) noexcept;
+namespace QHashPrivate {
 
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(char key, uint seed = 0) noexcept { return uint(key) ^ seed; }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(uchar key, uint seed = 0) noexcept { return uint(key) ^ seed; }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(signed char key, uint seed = 0) noexcept { return uint(key) ^ seed; }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(ushort key, uint seed = 0) noexcept { return uint(key) ^ seed; }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(short key, uint seed = 0) noexcept { return uint(key) ^ seed; }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(uint key, uint seed = 0) noexcept { return key ^ seed; }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(int key, uint seed = 0) noexcept { return uint(key) ^ seed; }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(ulong key, uint seed = 0) noexcept
+Q_DECL_CONST_FUNCTION constexpr uint hash(size_t key, uint seed) noexcept
 {
-    return (sizeof(ulong) > sizeof(uint))
-        ? (uint(((key >> (8 * sizeof(uint) - 1)) ^ key) & (~0U)) ^ seed)
-        : (uint(key & (~0U)) ^ seed);
+    key ^= seed;
+    if constexpr (sizeof(size_t) == 4) {
+        key ^= key >> 16;
+        key *= UINT32_C(0x45d9f3b);
+        key ^= key >> 16;
+        key *= UINT32_C(0x45d9f3b);
+        key ^= key >> 16;
+        return key;
+    } else {
+        key ^= key >> 32;
+        key *= UINT64_C(0xd6e8feb86659fd93);
+        key ^= key >> 32;
+        key *= UINT64_C(0xd6e8feb86659fd93);
+        key ^= key >> 32;
+        return uint(key);
+    }
+}
+
 }
-Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(long key, uint seed = 0) noexcept { return qHash(ulong(key), seed); }
+
+Q_CORE_EXPORT Q_DECL_PURE_FUNCTION uint qHashBits(const void *p, size_t size, uint seed = 0) noexcept;
+
+Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(char key, uint seed = 0) noexcept
+{ return QHashPrivate::hash(size_t(key), seed); }
+Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(uchar key, uint seed = 0) noexcept
+{ return QHashPrivate::hash(size_t(key), seed); }
+Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(signed char key, uint seed = 0) noexcept
+{ return QHashPrivate::hash(size_t(key), seed); }
+Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(ushort key, uint seed = 0) noexcept
+{ return QHashPrivate::hash(size_t(key), seed); }
+Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(short key, uint seed = 0) noexcept
+{ return QHashPrivate::hash(size_t(key), seed); }
+Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(uint key, uint seed = 0) noexcept
+{ return QHashPrivate::hash(size_t(key), seed); }
+Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(int key, uint seed = 0) noexcept
+{ return QHashPrivate::hash(size_t(key), seed); }
+Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(ulong key, uint seed = 0) noexcept
+{ return QHashPrivate::hash(size_t(key), seed); }
+Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(long key, uint seed = 0) noexcept
+{ return QHashPrivate::hash(size_t(key), seed); }
 Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(quint64 key, uint seed = 0) noexcept
 {
-    return uint(((key >> (8 * sizeof(uint) - 1)) ^ key) & (~0U)) ^ seed;
+    if (sizeof(quint64) > sizeof(size_t))
+        key ^= (key >> 32);
+    return QHashPrivate::hash(size_t(key), seed);
 }
 Q_DECL_CONST_FUNCTION Q_DECL_CONSTEXPR inline uint qHash(qint64 key, uint seed = 0) noexcept { return qHash(quint64(key), seed); }
 Q_CORE_EXPORT Q_DECL_CONST_FUNCTION uint qHash(float key, uint seed = 0) noexcept;