title: Data structure with O(1) lookup time which will allow duplicates
body: <p>My goal is to create a data structure implementing <code>IList&lt;T&gt;</code> interface which will achieve <code>O(1)</code> element lookup time by compromising memory.</p>
  
  <p><strong>Background</strong>
  As you know all array based <code>IList&lt;T&gt;</code> implementations like <code>List&lt;T&gt;</code> have <code>O(n)</code> element lookup time. It means that the operations like <code>int IndexOf(T element)</code> or <code>bool Contains(T element)</code> iterate through the underlaying array until they find a match.</p>
  
  <p>Well known idea achive that is to use a combination of a list and hashtable as underlaying data structures. Values are kept in a list. The hashtable will keep indexes as values and values of list as keys. So lookup can be performed using hashtable.</p>
  
  <p>That's exactly how the <code>KeyedCollection&lt;TKey, TItem&gt;</code> <a href="http://msdn.microsoft.com/en-us/library/ms132438.aspx" rel="nofollow">see MSDN</a> is implemented.</p>
  
  <p><strong>What I have tried so far</strong></p>
  
  <pre><code>internal class MyList&lt;T&gt; : KeyedCollection&lt;T, T&gt;
  {
      protected override T GetKeyForItem(T item)
      {
          return item;
      }
  }
  </code></pre>
  
  <p>This worked so far except one problem. This data structure does not mimic the behavior expected behind <code>List&lt;T&gt;</code> exactly. The point is that the <code>List&lt;T&gt;</code> allows duplicates, <code>MyList</code> does not.</p>
  
  <p><strong>Question</strong></p>
  
  <p>Is there any ready to use data structure or can you recommend an elegant way of implementing the <code>IList&lt;T&gt;</code> so that:</p>
  
  <ol>
  <li>Lookup operations have <code>O(1)</code> time.</li>
  <li>All other operations have same <code>O()</code> performance as <code>List&lt;T&gt;</code></li>
  <li>Memory can be compromised by hashtable overhead (<code>constantA + constantB * n</code> bytes).</li>
  <li><strong>Duplicates must be allowed</strong></li>
  <li>Allowing nulls is optional (they can be boxed into null objects)</li>
  </ol>