[backport] pseudorandom probing for hash collision (#13418)

2 files changed, 29 insertions, 7 deletions

diff --git a/tests/collections/ttables.nim b/tests/collections/ttables.nim
index 9eccf345a..7459b3f13 100644
--- a/tests/collections/ttables.nim
+++ b/tests/collections/ttables.nim
@@ -8,7 +8,12 @@ And we get here
 '''
 joinable: false
 """
-import hashes, sequtils, tables, algorithm
+import hashes, sequtils, tables, algorithm, testutils
+
+block tableDollar:
+  # other tests should use `sortedPairs` to be robust to future table/hash
+  # implementation changes
+  doAssert ${1: 'a', 2: 'b'}.toTable in ["{1: 'a', 2: 'b'}", "{2: 'b', 1: 'a'}"]
 
 # test should not be joined because it takes too long.
 block tableadds:
@@ -188,6 +193,23 @@ block ttables2:
   run1()
   echo "2"
 
+block allValues:
+  var t: Table[int, string]
+  var key = 0
+  let n = 1000
+  for i in 0..<n: t.add(i, $i)
+  const keys = [0, -1, 12]
+  for i in 0..1:
+    for key in keys:
+      t.add(key, $key & ":" & $i)
+  for i in 0..<n:
+    if i notin keys:
+      t.del(i)
+  doAssert t.sortedPairs == @[(-1, "-1:0"), (-1, "-1:1"), (0, "0"), (0, "0:0"), (0, "0:1"), (12, "12"), (12, "12:0"), (12, "12:1")]
+  doAssert sortedItems(t.allValues(0)) == @["0", "0:0", "0:1"]
+  doAssert sortedItems(t.allValues(-1)) == @["-1:0", "-1:1"]
+  doAssert sortedItems(t.allValues(12)) == @["12", "12:0", "12:1"]
+  doAssert sortedItems(t.allValues(1)) == @[]
 
 block tablesref:
   const
@@ -232,8 +254,8 @@ block tablesref:
     for x in 0..1:
       for y in 0..1:
         assert t[(x,y)] == $x & $y
-    assert($t ==
-      "{(x: 1, y: 1): \"11\", (x: 0, y: 0): \"00\", (x: 0, y: 1): \"01\", (x: 1, y: 0): \"10\"}")
+    assert t.sortedPairs ==
+      @[((x: 0, y: 0), "00"), ((x: 0, y: 1), "01"), ((x: 1, y: 0), "10"), ((x: 1, y: 1), "11")]
 
   block tableTest2:
     var t = newTable[string, float]()
@@ -340,7 +362,7 @@ block tablesref:
   block anonZipTest:
     let keys = @['a','b','c']
     let values = @[1, 2, 3]
-    doAssert "{'c': 3, 'a': 1, 'b': 2}" == $ toTable zip(keys, values)
+    doAssert zip(keys, values).toTable.sortedPairs == @[('a', 1), ('b', 2), ('c', 3)]
 
   block clearTableTest:
     var t = newTable[string, float]()
@@ -369,3 +391,4 @@ block tablesref:
 
   orderedTableSortTest()
   echo "3"
+
diff --git a/tests/collections/ttablesthreads.nim b/tests/collections/ttablesthreads.nim
index 5553b31ef..757a8cebe 100644
--- a/tests/collections/ttablesthreads.nim
+++ b/tests/collections/ttablesthreads.nim
@@ -3,7 +3,7 @@ discard """
   output: '''true'''
 """
 
-import hashes, tables, sharedtables
+import hashes, tables, sharedtables, testutils
 
 const
   data = {
@@ -47,8 +47,7 @@ block tableTest1:
   for x in 0..1:
     for y in 0..1:
       assert t[(x,y)] == $x & $y
-  assert($t ==
-    "{(x: 1, y: 1): \"11\", (x: 0, y: 0): \"00\", (x: 0, y: 1): \"01\", (x: 1, y: 0): \"10\"}")
+  assert t.sortedPairs == @[((x: 0, y: 0), "00"), ((x: 0, y: 1), "01"), ((x: 1, y: 0), "10"), ((x: 1, y: 1), "11")]
 
 block tableTest2:
   var t = initTable[string, float]()