title: Why are hash table expansions usually done by doubling the size?
body: <p>I've done a little research on hash tables, and I keep running across the rule of thumb that when there are a certain number of entries (either max or via a load factor like 75%) the hash table should be expanded.</p>
  
  <p>Almost always, the recommendation is to double (or double plus 1, i.e., 2n+1) the size of the hash table.  However, I haven't been able to find a good reason for this.</p>
  
  <p>Why double the size, rather than, say, increasing it 25%, or increasing it to the size of the next prime number, or next k prime numbers (e.g., three)?</p>
  
  <p>I already know that it's often a good idea to choose an initial hash table size which is a prime number, at least if your hash function uses modulus such as universal hashing.  And I know that's why it's usually recommended to do 2n+1 instead of 2n (e.g., <a href="http://www.concentric.net/~Ttwang/tech/hashsize.htm" rel="noreferrer">http://www.concentric.net/~Ttwang/tech/hashsize.htm</a>)</p>
  
  <p>However as I said, I haven't seen any real explanation for why doubling or doubling-plus-one is actually a good choice rather than some other method of choosing a size for the new hash table.</p>
  
  <p>(And yes I've read the Wikipedia article on hash tables :) <a href="http://en.wikipedia.org/wiki/Hash_table" rel="noreferrer">http://en.wikipedia.org/wiki/Hash_table</a></p>