title: Implementing hash table with both key and index-based access in O(1)
body: <p>There is a data structure called <a href="http://msdn.microsoft.com/en-us/library/ts6a60s4.aspx" rel="nofollow"><code>NameObjectCollectionBase</code></a> in .NET which I'm trying to understand.</p>
  
  <p>Basically, it allows to enter arbitrary string => object key/value-pairs with both the possibility of the key and the value being null. A key may be used by multiple objects. Access is granted through both an index-based and a string-based access, whereas the string-based access returns only the first value with the specified key.</p>
  
  <p>What they promise, is</p>
  
  <pre><code>add(string, object)        O(1) if no relocation, O(n) otherwise
  clear                      O(1)
  get(int)                   O(1) corresponds to getkey(int)
  get(string)                O(1) returns first object found with given key
  getallkeys                 O(n) if objects share a key, it is returned that many times
  getallvalues               O(n)
  getallvalues(type)         O(n) returns only objects of a given type
  getkey(int)                O(1) corresponds to get(int)
  haskeys                    O(1) if there are objects with a non-null key
  remove(string)             O(n) remove all objects of a given key
  removeat(int)              O(n)
  set(int, object)           O(1) 
  set(string, object)        O(1) sets the value of the first found object with given key
  getenumerator              O(1) enumerator over keys
  copyto(array, int)         O(n) 
  </code></pre>
  
  <p>Index-based access does have nothing to do with the insertion order. However, <code>get(int)</code> and <code>getkey(int)</code> have to line up with each other.</p>
  
  <p>I'm wondering how the structure may be implemented. Allowing both index and key-based access at the same time in O(1) seems not trivial to implement. They state on the MSDN page that "The underlying structure for this class is a hash table." However, the C# Hash tables don't allow multiple values per key and alo not null-keys.</p>
  
  <p>Implementing it as a <code>Dictionary&lt;string, List&lt;object&gt;</code> does not seem to be the solution as get(string) would be O(1) but get(int) not since you have to traverse all keys to find out which key has how many items in it.</p>
  
  <p>Implementing it as two separated lists where one is a simple <code>List&lt;string&gt;</code> for the keys and a <code>List&lt;Object&gt;</code> for the values in combination of a <code>Dictionary&lt;string, int&gt;</code> which points for each key to the index of the first value would allow both types of access in O(1) but would not allow removing in an efficient way since all indices would have to be updated in the hashtable (would be possible in O(n) but doesn't seem to be the best solution). Or would there be a more efficient way to remove an entry?</p>
  
  <p>How could such a data structure be implemented?</p>