37

I want to use the Python hash() function to get integer hashes from objects. But built-in hash() can give negative values, and I want only positive. And I want it to work sensibly on both 32-bit and 64-bit platforms.

I.e. on 32-bit Python, hash() can return an integer in the range -2**31 to 2**31 - 1. On 64-bit systems, hash() can return an integer in the range -2**63 to 2**63 - 1.

But I want a hash in the range 0 to 2**32-1 on 32-bit systems, and 0 to 2**64-1 on 64-bit systems.

What is the best way to convert the hash value to its equivalent positive value within the range of the 32- or 64-bit target platform?

(Context: I'm trying to make a new random.Random style class. According to the random.Random.seed() docs, the seed "optional argument x can be any hashable object." So I'd like to duplicate that functionality, except that my seed algorithm can't handle negative integer values, only positive.)

Improve this question

5 Answers 5

Reset to default
32

Using sys.maxsize:

>>> import sys
>>> sys.maxsize
9223372036854775807L
>>> hash('asdf')
-618826466
>>> hash('asdf') % ((sys.maxsize + 1) * 2)
18446744073090725150L

Alternative using ctypes.c_size_t:

>>> import ctypes
>>> ctypes.c_size_t(hash('asdf')).value
18446744073090725150L
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

There's no reason whatsoever to use a modulus here. I mean sure it works but it's less efficient and harder to read.
@CraigMcQueen, I added an alternative way. Check it out.
It's dangerous to assume that sys.maxsize will always be 2**31-1 on 32-bit and 2**63-1 on 64-bit platforms. Check for the expected values with if and elif and raise an exception if you encounter an unexpected value.
Note that hash(x) is limited to the 9th Mersenne prime 2**61-1 for integer input on 64 bit. Probably some prime smaller than 2**32 is used on 32 bit. This is all undocumented and should not be relied on.
Use sys.hash_info.width (see my answer) to use the actual hash width rather than assuming it always coincides with the platform word width.
11

Just using sys.maxsize is wrong for obvious reasons (it being `2*n-1 and not 2*n), but the fix is easy enough:

h = hash(obj)
h += sys.maxsize + 1

for performance reasons you may want to split the sys.maxsize + 1 into two separate assignments to avoid creating a long integer temporarily for most negative numbers. Although I doubt this is going to matter much

Improve this answer

4 Comments

You code could produce duplicated value. Try -0x7fffffffffffffff + sys.maxsize + 1 in 64bit system.
Ah yes true enough, shouldn't be conditional. Where's my head today?
Why /2 instead of *2?
Actually it's neither / nor * 2. We have a range of [-2**31, 2**31-1], but we want [-2**31+2**31, 2**31-1+2**31] (example is for 32bit system). So it's just an addition by the lower boundary (2**31).. really confused today I am.
3

(Edit: at first I thought you always wanted a 32-bit value)

Simply AND it with a mask of the desired size. Generally sys.maxsize will already be such a mask, since it's a power of 2 minus 1.

import sys
assert (sys.maxsize & (sys.maxsize+1)) == 0 # checks that maxsize+1 is a power of 2 

new_hash = hash & sys.maxsize
Improve this answer

3 Comments

That's a good idea, although I want a 64-bit (or 32-bit) value, not a 63-bit (or 31-bit) value.
@CraigMcQueen, sorry I thought that maxsize was already the right size.
Like that you check the assumption that sys.maxsize is 2**k-1
2

To support platforms with signed and unsigned hash(), you could use

hash(x) % 2**sys.hash_info.width

This will use the actual hash width as reported by Python rather than a guess from what Python deems to be the maximum size of a list on the platform. The % operation will map negative numbers to positive numbers, e.g. -1 will become 2**sys.hash_info.width - 1.

Note that if x is a positive integer close to 0, hash(x) is the identity function, i.e. it just passes through the value. In general, on 64-bit with Python 3.6, it seems to compute


(abs(x) % m) * (-1 if x<0 else 1)

with m=2**61-1, the 9th Mersenne prime. This can be problematic in some applications, e.g. filling a hash table with 1000 entries with values x = int(time_YYYMMDDhhmm) would result into a higher density of items at indices 0 to 359 than for 400 to 959 (and zero density in any range k*100+60 to k*100 + 99).

Improve this answer

3 Comments

That sounds good. sys.hash_info was new in Python 3.2. At the time this question was originally asked in 2013, we had to consider Python versions where this didn't exist. But now in 2024 it's pretty safe to rely on it.
What is the difference between sys.hash_info.width and sys.hash_info.hash_bits? It sounds as though potentially, the hash output might use a truncation of the internal hash algorithm's output, so sys.hash_info.width ≤ sys.hash_info.hash_bits, and we should use sys.hash_info.width.
@CraigMcQueen Both the C-API and PEP 456 say that hash_bits is internal. It probably is at least width as you say but there is no guarantee. I'd say if these details are important in an application, write your own hash function.
1

How about:

h = hash(o)
if h < 0:
  h += sys.maxsize

This uses sys.maxsize to be portable between 32- and 64-bit systems.

Improve this answer

1 Comment

You could still end up with a value of -1. Other than that corner-case, the resulting values are in the range of a positive 31-bit number (not 32-bit).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.