title: Python get random key in a dictionary in O(1)
body: <p>I need a data structure that supports FAST insertion and deletion of (key, value) pairs, as well as "get random key", which does the same thing as random.choice(dict.keys()) for a dictionary.  I've searched on the internet, and most people seem to be satisfied with the random.choice(dict.keys()) approach, despite it being linear time.  </p>
  
  <p>I'm aware that implementing this faster is <em>possible</em>:</p>
  
  <ul>
  <li>I could use a resizing hash table.  If I maintain that the ratio of keys to slots is between 1 and 2, then I can just choose random indices until I hit a non-empty slot.  I only look at 1 to 2 keys, in expectation.</li>
  <li>I can get these operations in guaranteed worst case O(log n) using an AVL tree, augmenting with rank.  </li>
  </ul>
  
  <p>Is there any easy way to get this in Python, though?  It seems like there should be!</p>