title: When is hash(n) == n in Python?
body: <p>I've been playing with Python's <a href="https://docs.python.org/3/library/functions.html#hash" rel="noreferrer">hash function</a>. For small integers, it appears <code>hash(n) == n</code> always. However this does not extend to large numbers:</p>
  
  <pre><code>&gt;&gt;&gt; hash(2**100) == 2**100
  False
  </code></pre>
  
  <p>I'm not surprised, I understand hash takes a finite range of values. What is that range?</p>
  
  <p>I tried using <a href="http://codejamhelpers.readthedocs.io/en/latest/#codejamhelpers.binary_search" rel="noreferrer">binary search</a> to find the smallest number <code>hash(n) != n</code></p>
  
  <pre><code>&gt;&gt;&gt; import codejamhelpers # pip install codejamhelpers
  &gt;&gt;&gt; help(codejamhelpers.binary_search)
  Help on function binary_search in module codejamhelpers.binary_search:
  
  binary_search(f, t)
      Given an increasing function :math:`f`, find the greatest non-negative integer :math:`n` such that :math:`f(n) \le t`. If :math:`f(n) &gt; t` for all :math:`n \ge 0`, return None.
  
  &gt;&gt;&gt; f = lambda n: int(hash(n) != n)
  &gt;&gt;&gt; n = codejamhelpers.binary_search(f, 0)
  &gt;&gt;&gt; hash(n)
  2305843009213693950
  &gt;&gt;&gt; hash(n+1)
  0
  </code></pre>
  
  <p>What's special about 2305843009213693951? I note it's less than <code>sys.maxsize == 9223372036854775807</code></p>
  
  <p>Edit: I'm using Python 3. I ran the same binary search on Python 2 and got a different result 2147483648, which I note is <code>sys.maxint+1</code></p>
  
  <p>I also played with <code>[hash(random.random()) for i in range(10**6)]</code> to estimate the range of hash function. The max is consistently below n above. Comparing the min, it seems Python 3's hash is always positively valued, whereas Python 2's hash can take negative values.</p>