Add more tests of hash effectiveness.

1 files changed, 24 insertions, 0 deletions

diff --git a/Lib/test/test_set.py b/Lib/test/test_set.py
index 54de508..ade39fb 100644
--- a/Lib/test/test_set.py
+++ b/Lib/test/test_set.py
@@ -10,6 +10,8 @@ import sys
 import warnings
 import collections
 import collections.abc
+import itertools
+import string
 
 class PassThru(Exception):
     pass
@@ -711,6 +713,28 @@ class TestFrozenSet(TestJointOps, unittest.TestCase):
             addhashvalue(hash(frozenset([e for e, m in elemmasks if m&i])))
         self.assertEqual(len(hashvalues), 2**n)
 
+        def letter_range(n):
+            return string.ascii_letters[:n]
+
+        def zf_range(n):
+            # https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers
+            nums = [frozenset()]
+            for i in range(n-1):
+                num = frozenset(nums)
+                nums.append(num)
+            return nums[:n]
+
+        def powerset(s):
+            for i in range(len(s)+1):
+                yield from map(frozenset, itertools.combinations(s, i))
+
+        for n in range(18):
+            t = 2 ** n
+            mask = t - 1
+            for nums in (range, letter_range, zf_range):
+                u = len({h & mask for h in map(hash, powerset(nums(n)))})
+                self.assertGreater(4*u, t)
+
 class FrozenSetSubclass(frozenset):
     pass