AK: Use a full-period xorshift PRNG for double_hash

The previous implementation had some pretty short cycles and two fixed
points (1711463637 and 2389024350). If two keys hashed to one of these
values insertions and lookups would loop forever.
This version is based on a standard xorshift PRNG with period 2**32-1.
The all-zero state is usually forbidden, so we insert it into the cycle
at an arbitrary location.

1 files changed, 9 insertions, 5 deletions

diff --git a/AK/HashFunctions.h b/AK/HashFunctions.h
index 951619c4a7..e869b44800 100644
--- a/AK/HashFunctions.h
+++ b/AK/HashFunctions.h
@@ -21,11 +21,15 @@ constexpr unsigned int_hash(u32 key)
 
 constexpr unsigned double_hash(u32 key)
 {
-    key = ~key + (key >> 23);
-    key ^= (key << 12);
-    key ^= (key >> 7);
-    key ^= (key << 2);
-    key ^= (key >> 20);
+    const unsigned magic = 0xBA5EDB01;
+    if (key == magic)
+        return 0u;
+    if (key == 0u)
+        key = magic;
+
+    key ^= key << 13;
+    key ^= key >> 17;
+    key ^= key << 5;
     return key;
 }