[ python-Patches-1772851 ] Decimal and long hash, compatibly and efficiently

Patches item #1772851, was opened at 2007-08-13 04:48
Message generated for change (Tracker Item Submitted) made by Item Submitter
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1772851&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: None
Group: None
Status: Open
Resolution: None
Priority: 5
Private: No
Submitted By: Mark Dickinson (marketdickinson)
Assigned to: Nobody/Anonymous (nobody)
Summary: Decimal and long hash, compatibly and efficiently

Initial Comment:
Make hash of int/long periodic with period 2**32-1 (or 2**64-1 on 64-bit systems).  This is makes it possible to define an efficient Decimal hash.

Hash for int/long is already close to periodic with period 2**32-1;  it's a small change to make it genuinely periodic.  With this change, it's possible to write a Decimal __hash__ such that:

(1) hash(Decimal(n))==hash(n) for all integers n, and
(2) Decimal hash can be computed without gross inefficiencies.

The current implementation of Decimal hash is almost unusable for very large Decimals:  hash(Decimal("1E999999999")) first converts its argument to a long, taking gigabytes of memory and a lot of time.
It's simple to satisfy either (1) or (2) above, but it seems impossible to satisfy both without touching the long hash.

The patch alters int_hash and long_hash to make them periodic, adds some tests to Lib/test/test_hash.py, and implements an efficient Decimal.__hash__.  If there's any chance of the patch being accepted I'll write some additional tests in Lib/test/test_decimal.py to check hash compatibility between longs and Decimals.

This patch fixes (most of) bug 1770416.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1772851&group_id=5470