QHash: use prime numbers when rebucketing

QHash uses an array representing the difference between 2^i and
the next prime; when growing, it calculates 2^x + array[x] (with
`x' representing the "hash table size in bits").

For some reason lost in history the differences are actually wrong
and the calculation above leads to using composite numbers.

Hence: use the right sequence and always produce primes. The right
sequence is actually A092131 from OEIS: http://oeis.org/A092131

Note that the sequence starts at A(1), but we need A(0) too.
Also we truncate the sequence to when growing too much, just like
the old code did, and use powers of two in that case instead.

Task-number: QTBUG-36866
Change-Id: Id2e3fc9cb567c0fdca305dee38f480e17639ca04
Reviewed-by: Morten Johan Sørvig <morten.sorvig@digia.com>
Reviewed-by: Jędrzej Nowacki <jedrzej.nowacki@digia.com>

1 files changed, 17 insertions, 8 deletions

diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp
index 5320ea1fbf..a5d14a3535 100644
--- a/src/corelib/tools/qhash.cpp
+++ b/src/corelib/tools/qhash.cpp
@@ -337,20 +337,29 @@ uint qt_hash(const QStringRef &key) Q_DECL_NOTHROW
 }
 
 /*
-    The prime_deltas array is a table of selected prime values, even
-    though it doesn't look like one. The primes we are using are 1,
-    2, 5, 11, 17, 37, 67, 131, 257, ..., i.e. primes in the immediate
-    surrounding of a power of two.
+    The prime_deltas array contains the difference between a power
+    of two and the next prime number:
 
-    The primeForNumBits() function returns the prime associated to a
-    power of two. For example, primeForNumBits(8) returns 257.
+    prime_deltas[i] = nextprime(2^i) - 2^i
+
+    Basically, it's sequence A092131 from OEIS, assuming:
+    - nextprime(1) = 1
+    - nextprime(2) = 2
+    and
+    - left-extending it for the offset 0 (A092131 starts at i=1)
+    - stopping the sequence at i = 28 (the table is big enough...)
 */
 
 static const uchar prime_deltas[] = {
-    0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,
-    1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0
+    0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3, 17, 27,  3,
+    1, 29,  3, 21,  7, 17, 15,  9, 43, 35, 15,  0,  0,  0,  0,  0
 };
 
+/*
+    The primeForNumBits() function returns the prime associated to a
+    power of two. For example, primeForNumBits(8) returns 257.
+*/
+
 static inline int primeForNumBits(int numBits)
 {
     return (1 << numBits) + prime_deltas[numBits];