title: Java Hash Symbol Table Implementation
body: <p>I built a symbol table using an array list filled with an object "pairs" that are singly-linked chains and hold a word and the number of times it occurs in a text file.  I need to use this for the FrequencyCounter program that counts the number of words in a file.  For some reason, I'm getting this error when running the the FrequencyCounter with the HashST:  </p>
  
  <pre><code>Processed 1215985 words (19 sec; 19710 msec
  Exception in thread "main" java.lang.NullPointerException
  
  at HashST.hashIndex(HashST.java:60)
  at HashST.get(HashST.java:105)
  at FrequencyCounter.main(FrequencyCounter.java:112)
  </code></pre>
  
  <p>I have an idea that there's something wrong with my HashST and its not putting the pairs in the ArrayList like I wanted it to.  Any suggestions on what is wrong with the implementation would be greatly appreciated.</p>
  
  <p>Here is my code and the code for the FrequencyCounter:</p>
  
  <pre><code>import java.util.LinkedList;
  import java.util.ArrayList;
  import java.util.Iterator;
  
  public class HashST&lt;Key extends Comparable&lt;Key&gt;, Value&gt; implements Iterable&lt;Key&gt; {
  private ArrayList&lt;Pair&gt; chains;
  private int numKeys;
  private int numChains;
  
  
  public class Pair
  {
      Key key;
      Value value;
      Pair(Key k, Value v)
      {
          key = k;
          value = v;
      }
      Pair()
      {}
  
      Pair next;
  }
  
      /**
   * Initialize an empty HashSt with a default of 64 empty chains.
   */
      public HashST()
      {
          this(64);
  
      }
  
  /**
   * Initialize an empty HashST with numChains emptychains.
   * 387911 is a prime number about twice the number of distinct
   * words in the leipzig1M.txt file.
   */
  public HashST(int numChains)
  {
      this.numChains = numChains;
      chains = new ArrayList&lt;Pair&gt;();
  
      for(int i = 0; i &lt; numChains; i++)
      {
          Pair p = new Pair(null, null);
          chains.add(p);
  
      }
  }
  
  /**
   * compute the hash index for a key k if the number of
   * chains is N
   */
  private int hashIndex(Key k, int N)
  {
      return (k.hashCode() &amp; 0x7fffffff) % N;
  
  }
  /**
   * insert the Pair (k,v) into the appropriate chain and increment 
   * the number of keys counter or 
   * update the value for k if k is already in the hash table.
   *
   */
  public void put(Key k, Value v) {
  
      int i = hashIndex(k, numChains);
      Pair tmp = chains.get(i);
      if(contains(k))
      {
          while(tmp.next != null)
          {
              if(tmp.key == k)
              {
                  tmp.value = v;
                  return;
              }
  
              tmp = tmp.next;
          }
      }
      else
      {
          Pair p = new Pair(k, v);
          tmp.next = p;
          numKeys ++;
  
      }
  
  
  
  
  }
  
  /**
   * return the value for key k if it is in the hash table
   * or else return null if it is not.
   */
  public Value get(Key k) {
  
      int i = hashIndex(k, numChains);
      Pair tmp = chains.get(i);
          while(tmp.next != null)
          {
              if(tmp.key == k)
              {
                  return tmp.value;
  
              }
  
              tmp = tmp.next;
          }
  
  
      return null;
  
  }
  
  /**
   * remove the pair with key k if it is in the hash table
   * otherwise no change.
   */
  public void delete(Key k) {
  
      if(contains(k))
      {
          return;
  
  
      }
  
  }
  
  /**
   * return true if the hash table contains a pair with key 
   * equal to k else return false
   */
  public boolean contains(Key k) {
  
      return (get(k) != null) ? true : false;
  
  }
  
  /**
   * return the number of keys in the hash table
   */
  public int size() {
  
      return numKeys;
  
  }
  
  /**
   * return a LinkedList&lt;Key&gt; containing the keys in the
   * hash table
   */
  public Iterable&lt;Key&gt; keys() {
  
      LinkedList&lt;Key&gt; l = new LinkedList&lt;Key&gt;();
      for(Pair p : chains)
      {
          while(p.next != null)
          {
              l.add(p.key);
              p = p.next;
          }
  
      }
  
  
      return l;
  }
  
  /**
   * return an Iterator&lt;Key&gt; for the keys in the hash table
   */ 
  public Iterator&lt;Key&gt; iterator() {
      return keys().iterator();
  }
  
  }
  </code></pre>
  
  <p>And here is the Frequency Counter: <a href="http://algs4.cs.princeton.edu/31elementary/FrequencyCounter.java.html" rel="nofollow">http://algs4.cs.princeton.edu/31elementary/FrequencyCounter.java.html</a></p>