[Python-checkins] cpython: Add more tests of hash effectiveness.

[raymond.hettinger]

https://hg.python.org/cpython/rev/1d0038dbd8f8
changeset:   97337:1d0038dbd8f8
user:        Raymond Hettinger <python at rcn.com>
date:        Sun Aug 09 00:35:00 2015 -0700
summary:
  Add more tests of hash effectiveness.

files:
  Lib/test/test_set.py |  24 ++++++++++++++++++++++++
  1 files changed, 24 insertions(+), 0 deletions(-)


diff --git a/Lib/test/test_set.py b/Lib/test/test_set.py
--- a/Lib/test/test_set.py
+++ b/Lib/test/test_set.py
@@ -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
 

-- 
Repository URL: https://hg.python.org/cpython