Why hash function on two different objects return same value?

Question

I used Spyder, run Python 2.7.

Just found interesting things:

hash(-1) and hash(-2) both return -2, is there a problem? I though hash function on different object should return different values. I read previous posts that -1 is reserved as an error in Python.
hash('s') returns 1835142386, then hash(1835142386) returns the same value. Is this another problem?

Thanks.

"I though hash function on different object should return different values" --- nope, it only should return the same value for the same object. — zerkms
– zerkms, Commented Jul 14, 2016 at 0:22
It is curious, though, that other than -1, hash(i) == i for abs(i) <= 1,000,000. — chepner
– chepner, Commented Jul 14, 2016 at 0:59

kindall · Accepted Answer · 2016-07-14 00:35:11Z

4

-1 is not "reserved as an error" in Python. Not sure what that would even mean. There are a huge number of programs you couldn't write simply and clearly if you weren't allowed to use -1.

"Is there a problem?" No. Hash functions do not need to return a different hash for every object. In fact, this is not possible, since there are many more possible objects than there are hashes. CPython's hash() has the nice property of returning its argument for non-negative numbers up to sys.maxint, which is why in your second question hash(hash('s')) == hash('s'), but that is an implementation detail.

The fact that -1 and -2 have the same hash simply means that using those values as, for example, dictionary keys will result in a hash conflict. Hash conflicts are an expected situation and are automatically resolved by Python, and the second key added would simply go in the next available slot in the dictionary. Accessing the key that was inserted second would then be slightly slower than accessing the other one, but in most cases, not enough slower that you'd notice.

It is possible to construct a huge number of unequal objects all with the same hash value, which would, when stored in a dictionary or a set, cause the performance of the container to deteriorate substantially because every object added would cause a hash collision, but it isn't something you will run into unless you go looking for it.

edited Jul 14, 2016 at 0:35

answered Jul 14, 2016 at 0:24

kindall

185k36 gold badges291 silver badges321 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

zerkms Over a year ago

If the -1 value is not reserved (for something) - what is the practical purpose of it being an exception? github.com/python/cpython/blob/…

zerkms Over a year ago

Well, seems like it does denote an error: github.com/python/cpython/blob/… "All the utility functions (_Py_Hash*()) return "-1" to signify an error."

Chenxi Zeng Over a year ago

True, if hash function does not guarantee uniqueness (which makes sense, there are more objects than integers), each time I add a new key, if the hash value returns with a value that is, by coincidence, same as previously key's value, the system will fix this, right? This makes sense. Thanks.

kindall Over a year ago

Aha. I hadn't realized you were looking at the hash function C code. That makes sense that there would be a value used as an error code internally, and also explains why the hash of -1 is not -1. Learned something today! Thank you.

Collectives™ on Stack Overflow

Why hash function on two different objects return same value?

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related