1

I was studying dictionaries and looking for ways to avoid the worst-case O(n) time complexity for get/set/delete operations due to potential hash collisions (src), and learned that integers always hash to themselves, so collisions shouldn't be an issue if you use ints as the dictionary's keys. However, I was testing this in my terminal and this is what I saw:

>>> print hash(4), hash(3), hash(2), hash(1), hash(0), hash(-1), hash(-2), hash(-3), hash(-4)
4 3 2 1 0 -2 -2 -3 -4
>>> hash(-1) == hash(-2)
True

That's strange, both hash(-1) == -2 and hash(-2) == -2 so I tried it in a dict:

>>> d = {-3: 'a', -2:'b', -1:'c'}
>>> print d
{-1: 'c', -3: 'a', -2: 'b'}

Okay, at least the hash collision is handled properly.

Why are there two ints that have the same hash?

jball037
  • 1,780
  • 1
  • 14
  • 18

1 Answers1

3

This previous question answers the question! Here is the Tl;dr version:

The hash value -1 is reserved (it’s used to flag errors in the C implementation). If the hash algorithm generates this value, we simply use -2 instead.

Reblochon Masque
  • 35,405
  • 10
  • 55
  • 80
ladygremlin
  • 452
  • 3
  • 14