title: Memory efficient int-int dict in Python
body: <p>I need a memory efficient int-int dict in Python that would support the following operations in <em>O(log n)</em> time:</p>
  
  <pre><code>d[k] = v  # replace if present
  v = d[k]  # None or a negative number if not present
  </code></pre>
  
  <p>I need to hold ~250M pairs, so it <strong>really</strong> has to be tight.</p>
  
  <p>Do you happen to know a suitable implementation (Python 2.7)?</p>
  
  <p><em><strong>EDIT</strong> Removed impossible requirement and other nonsense.  Thanks, Craig and Kylotan!</em></p>
  
  <hr>
  
  <p>To rephrase.  Here's a trivial int-int dictionary with 1M pairs:</p>
  
  <pre><code>&gt;&gt;&gt; import random, sys
  &gt;&gt;&gt; from guppy import hpy
  &gt;&gt;&gt; h = hpy()
  &gt;&gt;&gt; h.setrelheap()
  &gt;&gt;&gt; d = {}
  &gt;&gt;&gt; for _ in xrange(1000000):
  ...     d[random.randint(0, sys.maxint)] = random.randint(0, sys.maxint)
  ... 
  &gt;&gt;&gt; h.heap()
  Partition of a set of 1999530 objects. Total size = 49161112 bytes.
   Index  Count   %     Size   % Cumulative  % Kind (class / dict of class)
       0      1   0 25165960  51  25165960  51 dict (no owner)
       1 1999521 100 23994252  49  49160212 100 int
  </code></pre>
  
  <p>On average, a pair of integers uses <strong>49 bytes</strong>.</p>
  
  <p>Here's an array of 2M integers:</p>
  
  <pre><code>&gt;&gt;&gt; import array, random, sys
  &gt;&gt;&gt; from guppy import hpy
  &gt;&gt;&gt; h = hpy()
  &gt;&gt;&gt; h.setrelheap()
  &gt;&gt;&gt; a = array.array('i')
  &gt;&gt;&gt; for _ in xrange(2000000):
  ...     a.append(random.randint(0, sys.maxint))
  ... 
  &gt;&gt;&gt; h.heap()
  Partition of a set of 14 objects. Total size = 8001108 bytes.
   Index  Count   %     Size   % Cumulative  % Kind (class / dict of class)
       0      1   7  8000028 100   8000028 100 array.array
  </code></pre>
  
  <p>On average, a pair of integers uses <strong>8 bytes</strong>.</p>
  
  <p>I accept that 8 bytes/pair in a dictionary is rather hard to achieve in general.  <strong>Rephrased question: is there a memory-efficient implementation of int-int dictionary that uses considerably less than 49 bytes/pair?</strong></p>