title: Hashtable collision rehashing - how are values read?
body: <p>I am trying to understand how Hashtables work in C#. I read the MSDN article and I understand that C# Hashtables use 'rehashing' for collisions, i.e. if I try to insert a key/value pair into the hashtable, if using HashFunction H1 results in a collision, then it will try HashFunction H2, H3, etc, until no collisions are found.</p>
  
  <p><a href="http://msdn.microsoft.com/en-us/library/ms379571%28v=vs.80%29.aspx" rel="noreferrer">MSDN</a> quote:</p>
  
  <blockquote>
    <p>The Hashtable class uses a different technique referred to as
    rehasing. (Some sources refer to rehashing as double hashing.)</p>
    
    <p>Rehashing works as follows: there is a set of hash different
    functions, H1 ... Hn, and when inserting or retrieving an item from
    the hash table, initially the H1 hash function is used. If this leads
    to a collision, H2 is tried instead, and onwards up to Hn if needed.
    The previous section showed only one hash function, which is the
    initial hash function (H1). The other hash functions are very similar
    to this function, only differentiating by a multiplicative factor. In
    general, the hash function Hk is defined as:</p>
    
    <p>Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) %
    (hashsize – 1)))] % hashsize</p>
  </blockquote>
  
  <p>However, taking the example from the MSDN site1:</p>
  
  <pre><code>private static Hashtable employees = new Hashtable();
  
  public static void Main()
  {
      // Add some values to the Hashtable, indexed by a string key
      employees.Add("111-22-3333", "Scott");
      employees.Add("222-33-4444", "Sam");
  }
  </code></pre>
  
  <p>Let's assume that adding the second key will result in a collision, so H2 will have to be used. However, when I call employees["222-33-4444"], how does the hashtable know to use H2? Is there a separate mapping? Thanks.</p>