changeset:   97337:1d0038dbd8f8
user:        Raymond Hettinger <python@rcn.com>
date:        Sun Aug 09 00:35:00 2015 -0700
files:       Lib/test/test_set.py
description:
Add more tests of hash effectiveness.


diff -r 57032f6ca3ce -r 1d0038dbd8f8 Lib/test/test_set.py
--- a/Lib/test/test_set.py	Sat Aug 08 22:05:05 2015 -0500
+++ b/Lib/test/test_set.py	Sun Aug 09 00:35:00 2015 -0700
@@ -10,6 +10,8 @@
 import warnings
 import collections
 import collections.abc
+import itertools
+import string
 
 class PassThru(Exception):
     pass
@@ -711,6 +713,28 @@
             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