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():