Data Structures, Algorithms, & Applications in Java
Chapter 11, Exercise 25

We would like to double the array size in case the new addition will cause the loading factor to exceed the specified threshold. To implement this strategy faithfully, we must first check if the new addition is a duplicate. To avoid the cost of this check, we double the table capacity whenever (size + 1)/capcity exceeds the threshold. The code is given below. 

public class HashTableWithDoubling extends HashTable
{
   // double hash table capacity when loading factor
   // exceeds threshold
   private double threshold;

   public HashTableWithDoubling(int theDivisor)
   {
      super(theDivisor);
      threshold = 0.75;
   }

   public HashTableWithDoubling(double theThreshold)
   {
      super(11);
      threshold = theThreshold;
   }

   /** insert an element with the specified key
     * overwrite old element if there is already an
     * element with the given key
     * double table size when loading factor exceeds threshold
     * overrides HashTable.put
     * return old element (if any) with key theKey */
   public Object put(Object theKey, Object theElement)
   {
      if (((double)(size + 1)) / table.length > threshold)
      {// double table capacity, we assume theKey is not a duplicate
       // doesn't hurt even if theKey is a duplicate
         HashEntry [] oldTable = table;
         // approximately double capacity, keeping length odd 
         table = new HashEntry [oldTable.length * 2 + 1];
         divisor = table.length;
         size = 0;

         // insert old elements into new table
         for (int i = 0; i < oldTable.length; i++)
            if (oldTable[i] != null)
               super.put(oldTable[i].key, oldTable[i].element);
      }

      // insert new item
      return super.put(theKey, theElement);
   }
}


A more efficient version is given below. 

public class HashTableWithDoubling2 extends HashTable
{
   // double hash table capacity when loading factor
   // exceeds threshold
   private double threshold;

   public HashTableWithDoubling2(int theDivisor)
   {
      super(theDivisor);
      threshold = 0.75;
   }

   public HashTableWithDoubling2(double theThreshold)
   {
      super(11);
      threshold = theThreshold;
   }

   /** insert an element with the specified key
     * overwrite old element if there is already an
     * element with the given key
     * double table size when loading factor exceeds threshold
     * overrides hashTable.put
     * return old element (if any) with key theKey */
   public Object put(Object theKey, Object theElement)
   {
      if (((double)(size + 1)) / table.length > threshold)
      {// double table capacity, we assume theKey is not a duplicate
       // doesn't hurt even if theKey is a duplicate
         HashEntry [] oldTable = table;
         // approximately double capacity, keeping length odd 
         table = new HashEntry [oldTable.length * 2 + 1];
         divisor = table.length;

         // insert old elements into new table
         for (int i = 0; i < oldTable.length; i++)
            if (oldTable[i] != null)
            {// enter oldTable[i] into new table
                // find an empty bucket
                int j = Math.abs(oldTable[i].key.hashCode()) % divisor;
                while (table[j] != null)
                   j = (j + 1) % divisor;  // next bucket
      
                table[j] = oldTable[i];
            }
      }

      // insert new item
      return super.put(theKey, theElement);
   }