[Python-checkins] python/dist/src/Lib/test test_tuple.py,1.2,1.3

[rhettinger at users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Lib/test
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv4903/Lib/test

Modified Files:
	test_tuple.py 
Log Message:
SF bug #942952:  Weakness in tuple hash
(Basic approach and test concept by Tim Peters.)

* Improved the hash to reduce collisions.
* Added the torture test to the test suite.



Index: test_tuple.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/test/test_tuple.py,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** test_tuple.py	18 Jan 2004 21:03:23 -0000	1.2
--- test_tuple.py	1 Jun 2004 06:36:24 -0000	1.3
***************
*** 42,45 ****
--- 42,64 ----
          self.assertEqual(list(tuple(f())), range(1000))
  
+     def test_hash(self):
+         # See SF bug 942952:  Weakness in tuple hash
+         # The hash should:
+         #      be non-commutative
+         #      should spread-out closely spaced values
+         #      should not exhibit cancellation in tuples like (x,(x,y))
+         #      should be distinct from element hashes:  hash(x)!=hash((x,))
+         # This test exercises those cases.
+         # For a pure random hash and N=50, the expected number of collisions
+         #      is 7.3.  Here we allow twice that number.
+         #      Any worse and the hash function is sorely suspect.
+ 
+         N=50
+         base = range(N)
+         xp = [(i, j) for i in base for j in base]
+         inps = base + [(i, j) for i in base for j in xp] + \
+                      [(i, j) for i in xp for j in base] + xp + zip(base)
+         collisions = len(inps) - len(set(map(hash, inps)))
+         self.assert_(collisions <= 15)
  
  def test_main():