title: Sorted hash table (map, dictionary) data structure design
body: <p>Here's a description of the data structure:</p>
  
  <p>It operates like a regular map with <code>get</code>, <code>put</code>, and <code>remove</code> methods, but has a <code>sort</code> method that can be called to sorts the map. However, the map <em>remembers</em> its sorted structure, so subsequent calls to sort can be much quicker (if the structure doesn't change too much between calls to <code>sort</code>).</p>
  
  <p>For example:</p>
  
  <ul>
  <li>I call the <code>put</code> method 1,000,000 times.<br/></li>
  <li>I call the <code>sort</code> method.<br/></li>
  <li>I call the <code>put</code> method 100 more times.<br/></li>
  <li>I call the <code>sort</code> method.<br/></li>
  </ul>
  
  <p>The second time I call the <code>sort</code> method should be a much quicker operation, as the map's structure hasn't changed much. Note that the map doesn't have to maintain sorted order between calls to <code>sort</code>.</p>
  
  <p>I understand that it might not be possible, but I'm hoping for O(1) <code>get</code>, <code>put</code>, and <code>remove</code> operations. Something like <a href="http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html" rel="nofollow noreferrer">TreeMap</a> provides guaranteed O(log(n)) time cost for these operations, but always maintains a sorted order (no <code>sort</code> method).</p>
  
  <p>So what's the design of this data structure?</p>
  
  <p><strong>Edit 1 - returning the top-K entries</strong></p>
  
  <p>Alhough I'd enjoy hearing the answer to the general case above, my use case has gotten more specific: I don't need the whole thing sorted; just the top K elements.</p>
  
  <p><a href="https://stackoverflow.com/questions/2105146/data-structure-for-efficiently-returning-the-top-k-entries-of-a-hash-table-map">Data structure for efficiently returning the <em>top-K</em> entries of a hash table (map, dictionary)</a></p>
  
  <p>Thanks!</p>