summaryrefslogtreecommitdiffstats
path: root/Lib/fractions.py
diff options
context:
space:
mode:
authorMark Dickinson <dickinsm@gmail.com>2010-05-23 13:33:13 (GMT)
committerMark Dickinson <dickinsm@gmail.com>2010-05-23 13:33:13 (GMT)
commitdc787d2055a7b562b64ca91b8f1af6d49fa39f1c (patch)
treef6a3868e8134c25c662868f19306bfea76b0ab45 /Lib/fractions.py
parent03721133a68814696e3eee75b1eb09f5016ff078 (diff)
downloadcpython-dc787d2055a7b562b64ca91b8f1af6d49fa39f1c.zip
cpython-dc787d2055a7b562b64ca91b8f1af6d49fa39f1c.tar.gz
cpython-dc787d2055a7b562b64ca91b8f1af6d49fa39f1c.tar.bz2
Issue #8188: Introduce a new scheme for computing hashes of numbers
(instances of int, float, complex, decimal.Decimal and fractions.Fraction) that makes it easy to maintain the invariant that hash(x) == hash(y) whenever x and y have equal value.
Diffstat (limited to 'Lib/fractions.py')
-rw-r--r--Lib/fractions.py31
1 files changed, 22 insertions, 9 deletions
diff --git a/Lib/fractions.py b/Lib/fractions.py
index fc8a12c..51e67e2 100644
--- a/Lib/fractions.py
+++ b/Lib/fractions.py
@@ -8,6 +8,7 @@ import math
import numbers
import operator
import re
+import sys
__all__ = ['Fraction', 'gcd']
@@ -23,6 +24,12 @@ def gcd(a, b):
a, b = b, a%b
return a
+# Constants related to the hash implementation; hash(x) is based
+# on the reduction of x modulo the prime _PyHASH_MODULUS.
+_PyHASH_MODULUS = sys.hash_info.modulus
+# Value to be used for rationals that reduce to infinity modulo
+# _PyHASH_MODULUS.
+_PyHASH_INF = sys.hash_info.inf
_RATIONAL_FORMAT = re.compile(r"""
\A\s* # optional whitespace at the start, then
@@ -528,16 +535,22 @@ class Fraction(numbers.Rational):
"""
# XXX since this method is expensive, consider caching the result
- if self._denominator == 1:
- # Get integers right.
- return hash(self._numerator)
- # Expensive check, but definitely correct.
- if self == float(self):
- return hash(float(self))
+
+ # In order to make sure that the hash of a Fraction agrees
+ # with the hash of a numerically equal integer, float or
+ # Decimal instance, we follow the rules for numeric hashes
+ # outlined in the documentation. (See library docs, 'Built-in
+ # Types').
+
+ # dinv is the inverse of self._denominator modulo the prime
+ # _PyHASH_MODULUS, or 0 if self._denominator is divisible by
+ # _PyHASH_MODULUS.
+ dinv = pow(self._denominator, _PyHASH_MODULUS - 2, _PyHASH_MODULUS)
+ if not dinv:
+ hash_ = _PyHASH_INF
else:
- # Use tuple's hash to avoid a high collision rate on
- # simple fractions.
- return hash((self._numerator, self._denominator))
+ hash_ = abs(self._numerator) * dinv % _PyHASH_MODULUS
+ return hash_ if self >= 0 else -hash_
def __eq__(a, b):
"""a == b"""