title: Implementing a generic map using a hash table in Java
body: <p><strong>Post Details</strong><br />
  In a data structures course, I was given Java source code for a "quadratic probing hash table" class and asked to implement a generic map (with <em>get</em> and <em>put</em> methods) and store the key/definition pairs in a hash table.  I understand the material when reading the book but find it difficult to implement in a programming language (Java).  I think part of the problem is understanding exactly what the question requires and part is deficiency in Java programming experience.  I'm hoping to receive some suggestions for how I can approach problems like this and fill in whatever Java knowledge I'm missing.</p>
  
  <p><strong>Some questions I've had</strong><br />
  What is the function of the hash table class in relation to the generic map I'm supposed to create?  The hash table has several methods including <em>get</em>, <em>insert</em>, <em>remove</em>, <em>rehash</em>, etc...  Is the purpose of the hash table to generate a hash value to use as a key in the map class?  Are keys and definitions stored in the hash table or will they be stored in the map?  What's the point of making a map if the hash table already does all of this?</p>
  
  <p>Can someone help me understand how to approach problems like this?  What are some references that might help me, either specifically with this question or with understanding how to effectively and methodically complete this type of exercise?</p>
  
  <p>I appreciate whatever help I can get.  I'm including code from the book to help illustrate the problem.</p>
  
  <p><strong>Quadratic Probing Hash Table Code From Textbook</strong></p>
  
  <pre><code>public class QuadraticProbingHashTable&lt;AnyType&gt; {
  
      public QuadraticProbingHashTable() {
           this(DEFAULT_TABLE_SIZE);
       }
  
       public QuadraticProbingHashTable(int size) {
           allocateArray(size);
           doClear();
       }
  
       public boolean insert(AnyType x) {
           int currentPos = findPos(x);
           if(isActive(currentPos)) return false;
  
           array[currentPos] = new HashEntry&lt;&gt;(x, true);
           theSize++;
  
           if(++occupied &gt; array.length / 2) rehash();
  
           return true;
       }
  
       private void rehash() {
           HashEntry&lt;AnyType&gt;[] oldArray = array;
  
           allocateArray(2 * oldArray.length);
           occupied = 0;
           theSize = 0;
  
           for(HashEntry&lt;AnyType&gt; entry : oldArray)
               if(entry != null &amp;&amp; entry.isActive) insert(entry.element);
       }
  
       private int findPos(AnyType x) {
           int offset = 1;
           int currentPos = myhash(x);
  
           while(array[currentPos] != null &amp;&amp; !array[currentPos].element.equals(x)) {
               currentPos += offset;
               offset += 2;
               if(currentPos &gt;= array.length) currentPos -= array.length;
           }
  
           return currentPos;
       }
  
       public boolean remove(AnyType x) {
           int currentPos = findPos(x);
           if(isActive(currentPos)) {
               array[currentPos].isActive = false;
               theSize--;
               return true;
           } else return false;
       }
  
       public int size() {
           return theSize;
       }
  
       public int capacity() {
           return array.length;
       }
  
       public boolean contains(AnyType x) {
           int currentPos = findPos(x);
           return isActive(currentPos);
       }
  
       public AnyType get(AnyType x) {
          int currentPos = findPos(x);
          if(isActive(currentPos)) return array[currentPos].element;
          else return null;
       }
  
       private boolean isActive(int currentPos) {
           return array[currentPos] != null &amp;&amp; array[currentPos].isActive;
       }
  
       public void makeEmpty() {
           doClear( );
       }
  
       private void doClear() {
           occupied = 0;
           for(int i = 0; i &lt; array.length; i++) array[i] = null;
       }
  
       private int myhash(AnyType x) {
           int hashVal = x.hashCode();
  
           hashVal %= array.length;
           if(hashVal &lt; 0) hashVal += array.length;
  
           return hashVal;
       }
  
       private static class HashEntry&lt;AnyType&gt; {
           public AnyType  element;
           public boolean isActive;
  
           public HashEntry(AnyType e) {
               this(e, true);
           }
  
           public HashEntry(AnyType e, boolean i) {
               element = e;
               isActive = i;
           }
       }
  
       private static final int DEFAULT_TABLE_SIZE = 101;
  
       private HashEntry&lt;AnyType&gt;[] array;
       private int occupied;
       private int theSize;
  
       private void allocateArray(int arraySize) {
           array = new HashEntry[nextPrime(arraySize)];
       }
  
       private static int nextPrime(int n) {
           if(n % 2 == 0) n++;
  
           for(; !isPrime(n); n += 2) ;
  
           return n;
       }
  
       private static boolean isPrime( int n ) {
           if(n == 2 || n == 3) return true;
  
           if(n == 1 || n % 2 == 0) return false;
  
           for(int i = 3; i * i &lt;= n; i += 2)
               if(n % i == 0) return false;
  
           return true;
       }
   }
  </code></pre>
  
  <p><strong>Map Skeleton From Textbook</strong></p>
  
  <pre><code>class Map&lt;KeyType,ValueType&gt; {
      public Map()
  
      public void put(KeyType key, ValueType val)
      public ValueType get(KeyType key)
      public boolean isEmpty()
      public void makeEmpty()
  
      private QuadraticProbingHashTable&lt;Entry&lt;KeyType,ValueType&gt;&gt; items;
  
      private static class Entry&lt;KeyType,ValueType&gt; {
          KeyType key;
          ValueType value;
      }
  }
  </code></pre>