Mark Dickinson added the comment:
To help explain what's going on, here's some Python code. The Python function long_hash1 below has the properties that: (1) long_hash1(n) == hash(n) for almost all integers n, with a very small set of exceptions. (The first positive exception is 2**33-1, and the next after that is 3*2**33 - 1. The negative exceptions have the same absolute value as the positive ones, so the first negative exception is n = 1-2**33). (2) long_hash1(n) has a simple closed form, making it possible to compute an equivalent Decimal hash efficiently. (3) The current long_hash in Objects/longobject.c can be changed, by adding a single line of C code, so that hash(n) == long_hash1(n) always. That line is: if ((unsigned long)x < v->ob_digit[i]) x++; added directly after the addition. Explanation: the exceptions in (1) arise precisely when the addition x += v->ob_digit[i] in the long_hash code overflows (in the *unsigned* sense---equivalently, when the addition turns a negative x into a nonnegative one). Since ob_digit[i] only has 15 significant bits, and x has 32 (or 64), such overflow is going to be rare---it'll occur for roughly one addition in every 2**18 (or about 4 additions in every million), for `random' n. So for `most' n, hash(n) and long_hash1(n) are equal. So what about long_hash2(n)? This is what the patched long_hash is actually equivalent to; it's essentially the same as long_hash1(n), but fixed up to be genuinely periodic; that is, long_hash1(n+ULONG_MAX) == long_hash1(n) for any integer n. long_hash1 and long_hash2 are equal almost always for positive n (the exceptions being multiples of ULONG_MAX), equal about half the time for negative n, and off-by-one from each other about half the time. I don't really know whether the periodicity is that useful---the predictability is really what matters, so the 1-line change to produce a hash function equivalent to long_hash1 would do just fine as far as making Decimal work. For what it's worth, I regard this patch as an ugly hack. I don't like the idea of changing something as fundamental as long.__hash__, and I don't like having Decimal.__hash__ depend on knowing exactly how long.__hash__ gets its values. But there's a real problem here, namely that, for example, >>> set([Decimal("1E1000000")]) takes several minutes to complete. (Try it!) And I can't think of any other easy way to solve this. Alternative suggestions welcomed! LONG_BITS = 32 W = 2**LONG_BITS HW = W // 2 ULONG_MAX = W - 1 def long_hash1(n): if n == 0: h = 0 else: h = (1 + (abs(n)-1) % ULONG_MAX) * (1 if n > 0 else -1) # reduce mod W to lie in the usual range for a (signed) C long h = (h + HW) % W - HW if h == -1: h = -2 return int(h) def long_hash2(n): h = n % ULONG_MAX h = (h + HW) % W - HW if h == -1: h = -2 return int(h) _____________________________________ Tracker <[EMAIL PROTECTED]> <http://bugs.python.org/issue1772851> _____________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com