I am making a project using hashtables. I have to use a linked list to handle duplicate hashcodes. The Objects that I am turning into hash tables are State objects with just a String name. I have debugged and tested my entire project and cannot figure out why it is not working. There is 25 State objects withing the txt file. The space available is 29 for the size of the hashtable and I am not able to change that. It is giving me a...

Java Result: 1
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at project5mitchell.HashTable.insert(HashTable.java:68)
at project5mitchell.State_Controller.insert(State_Controller.java:84)
at project5mitchell.Main.main(Main.java:22)

This is the line with the issue in the HashTable.java

hashArray[hashVal].insert(new State(key)); <-------here is causing the problem

Main class

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
*/
package project5mitchell;

import java.io.IOException;

/**
 *
 * @author Taylor
 */
public class Main {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) throws IOException 
{
    State_Controller myStateController = new State_Controller(25);
    myStateController.loadData("Heaps.States.txt");
    myStateController.insert();
    myStateController.displayStates();


}
}

State class

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package project5mitchell;

 /**
 *
 * @author Taylor
 */
 public class State 
{
    private String stateName;       // reference to a State object name
    State leftChild;        // this node’s left child
    State rightChild;       // this node’s right child.
    State next;
    State previous;
    State current;
    /**
     * Constructor
     *
     * @param none
     * @returns void
     */
    public State(String name) 
    {
        stateName = name;
    }// end State()
//------------------------------------------------------------------------------

/**
 * Obtains State Name.
 *
 * @param none
 * @return stateName: String
 */
     public String getStateName() 
    {
         return stateName;
    }//end getStateName
//------------------------------------------------------------------------------
    /**
     * Makes String of states.
     *
     * @param str: String
     * @param stateName: String
     *
     * @return str: String
     */
    @Override
     public String toString() 
    {
        String s = String.format("%15s", stateName); //display States
        return s;
    }// end toSTring()
}

State_Controller Class

/*
     * To change this template, choose Tools | Templates
     * and open the template in the editor.
     */
    package project5mitchell;

    import java.io.BufferedReader;
    import java.io.FileInputStream;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;

    /**
     *
     * @author Taylor
     */
    public class State_Controller 
    {
        private int numStates = 0;
        HashTable hashed = new HashTable(29);
        private State[] myStates;


        /**
         * Creates a new state object
         *
         * @param maxSize: int 
         * @return new state object
         */
        public State_Controller(int maxSize) 
        {
            myStates = new State[maxSize];
        } // end stateController()
    //------------------------------------------------------------------------------    
        /**Method to place States into an ArrayList
         *
         * @param myStates: ArrayList
         * @return numStates: int
         * @throws IOException
         */
        public int loadData(String filename) throws IOException 
        {
        FileInputStream fis1 = new FileInputStream("Heaps.States.txt"); 
        //obtains file statearray.txt
        BufferedReader br1 = new BufferedReader(new InputStreamReader(fis1)); 
        //reads statearray.txt
        String inputString, name;
        inputString = br1.readLine();

        while (inputString != null) 
            //while loop to continually create state objects
        {
            name = inputString; //parses the file for name
            myStates[numStates] = new State(name); 
                //creates a new state object with attributes
            numStates++; //increases state count
            inputString = br1.readLine(); //read next line
        } // end while (inputString != null) 
        br1.close();
        return numStates;
        }//end loadData(String filename) throws IOException
    //------------------------------------------------------------------------------
        /**
         * Routine for displaying state objects.
         * 
         * @param index
         * @return myStates[index]
         */
        public void displayStates() 
        {
            int index; //index is a local variable for state objects

            for (index = 0;
                    index < numStates;
                    index++) //for loop to continue making state objects stopping at numStates(50)
            {
                System.out.println(myStates[index]); //displays state objects(unsorted)
            }//end for loop
        }//end displayStates()
        public void insert()
        {
            for (int i = 0; i < numStates; i++)
            {
            hashed.insert(myStates[i]);
            }
        }
    //------------------------------------------------------------------------------
        public void display()
        {
            hashed.displayTable();
        }
    }

LinkList class

package project5mitchell;

import java.io.*;
/**
 * 
 * @author TaylorMitchell
 * 
 * Explains to Java what methods a Linked List class of State can do
 */
public class LinkList
{
    private State first;               // ref to first item
    private State last;                // ref to last item
    public State current;

    /**
     * Constructor
     * 
     * @param none
     * @return null
     */
    public LinkList()   
    {// constructor        
      first = null;                  // no items on list yet   
      last = null;
    } //end LinkList()
//------------------------------------------------------------------------------
    /**
     * Checks if list is empty
     * @param null
     * @return first = null: boolean
     */
    public boolean isEmpty() // true if no links
    {
        return first == null;
    } //end isEmpty()
//------------------------------------------------------------------------------    
    /**
     * inserts State key into a sorted linked list
     * 
     * @param key: State
     * @return true/false: boolean
     */
    public void insert(State key)
      {       
      State current = first;     // start at beginning   
      State previous = null;     // if starting at beginning previous = null

       while (current != null && key.getStateName().
               compareTo(current.getStateName())>0) 
        { 
        previous = current;
        current = current.next; // go to next item
        }
    if (previous == null) // if beginning of list,
        first = key; 
    else
      // not at beginning,
        previous.next = key; 
        key.next = current;                // found it, did insertion
      } //end insertState key)
//------------------------------------------------------------------------------
    /**
     * Finds states keys in the Linked List and deletes them
     * @param key: State
     * @return true/false: boolean
     */
    public void delete(State key)
    { 
    State previous = null; 
    State current = first;

    while (current != null && !key.equals(current.getStateName())) 
    { 
      previous = current;
      current = current.next; 
    }
    // disconnect link
    if (previous == null) //   if beginning of list delete first link
      first = first.next;       
    else
      //   not at beginning
      previous.next = current.next; //delete current link
  } //end deleteKey(State key)
//------------------------------------------------------------------------------
    /**
     * Displays Linked List forwards
     * 
     * @param none
     * @return void
     */
    public void displayForward()
      {
      State current = first;          // start at beginning
      while(current != null)         // until end of list,
         {
         System.out.println(current.toString());      // display data
         current = current.next;     // move to next link
         } //end while
      System.out.println("\n"); //separates display from other methods
      } //end displayForward()
//------------------------------------------------------------------------------
    public State find(String key) {
    State current = first; 
    while (current != null && current.getStateName().compareTo(key)<=0) 
    { // or key too small,
      if (current.getStateName() == key) // found, return link
        return current;  
      current = current.next; // go to next item
    }
    return null; // cannot find it
  }
} //end LinkList class

HashTable class

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package project5mitchell;

/**
 *
 * @author Taylor
 */
public class HashTable 
{
   private LinkList[ ] hashArray;    // array holds hash table pointer
   private int arraySize;
   private State nonItem;        // for deleted items
// -----------------------------------------------------------------------------
   public HashTable(int size)       // constructor                               
      {
      arraySize = size;
      hashArray = new LinkList[arraySize];  // creates the hash table (array)
      for (int i = 0; i < arraySize; i++)
      hashArray[i] = new LinkList();
      nonItem = new State("-1");       //creates an item (object) with -1 value
      }// end Constructor
// -----------------------------------------------------------------------------
   public void displayTable()
   {   
      System.out.print("Table: ");
      for(int index=0; index<arraySize; index++)
      {
         if(hashArray[index] != null)
            System.out.print(hashArray[index] + " ");              
         else                   
            System.out.print("** ");
      }// end for
      System.out.println("");
      }// end displayTable()
// -----------------------------------------------------------------------------
   public int hashFunc (String key)
{
    int result = 42;
    String inputString = key.toString().toLowerCase();
    char [] characters = inputString.toCharArray();
    for (int i = 0; i < characters.length; i++) 
    {
            char currentChar = characters[i];

            if (currentChar == 'a' || currentChar == 'b' ||currentChar == 'c' ||
                currentChar == 'e' ||currentChar == 'e' || currentChar == 'f') 
            {
                    result += Integer.parseInt(""+currentChar, 16);
            }
            int j = (int)currentChar;
            result += j;
    }
    return (result % arraySize);
} // end hashFunc1()
// -----------------------------------------------------------------------------
 public void insert(State item) // insert a DataItem
   // (assumes table not full)
      {
      String key = item.getStateName(); 
      // extract key from object to be inserted into table
      int hashVal = hashFunc(key);  // hash the key (hopefully, cell is empty).  
      while(hashArray[hashVal] != null &&  // implies location is occupied
                 hashArray[hashVal] != null)
      {                     
          hashArray[hashVal].insert(new State(key)); <-------here is causing the problem
          //insert into current linked list
      }
      hashArray[hashVal] = new LinkList();    // insert item  
      // if open, insert value
      }  // end insert()
// -----------------------------------------------------------------------------
    public LinkList find(String key)       // find item with key
      {
      int hashVal = hashFunc(key);      // hash the key;  get hashVal

      while(hashArray[hashVal] != null)  // until empty cell,
         {
          if((hashArray[hashVal]).current.getStateName().equals(key)) 
              // found the key?          
            return hashArray[hashVal];   // yes, return item;  leave method         
         ++hashVal;                            // go to next cell if occupied.
         hashVal %= arraySize;             // wraparound if necessary
         }
      return null;                                 // can't find item
      }
// -----------------------------------------------------------------------------
    public State delete(String key)  // delete a DataItem
{
      int hashVal = hashFunc(key);  // hash the key

      while(hashArray[hashVal] != null)  // until empty cell,
      {                                 // found the key?
         if(hashArray[hashVal].current.getStateName().equals(key))
            {
            State temp = hashArray[hashVal].current; // save item for return
            hashArray[hashVal].delete(temp);       // delete item;  -1?
            return temp;                                 // return item
            }
         ++hashVal;                      // go to next cell
         hashVal %= arraySize;      // wraparound if necessary
       }// end while()
      return null;                      // can't find item
 }  // end delete()
// -----------------------------------------------------------------------------

   }  // end class HashTable

I only post my entire code because it helps and typically I am asked to give the rest of the code, especially because all of this project is linked. Thank you for your help.

java.lang.OutOfMemoryError: Java heap space

That's usually caused by recursive calls. Check you code to make sure there is no recursion.

How many lines does it read from the input file before the error happens?

You need to post the input file to allow us to test the code.

After the loadData method I display it and they all print out, but once I try to insert the State Objects it gives me this error. I just looked over my file again. I did not put any recursive methods in my program.

The input file is

Maine
New_Hampshire
Vermont
Rhode_Island
Connecticut
Massachusetts
New_York
Pennsylvania
New_Jersey
West_Virginia
Virginia
Maryland
California
Delaware
Colorado
Texas
Oklahoma
Indiana
Illinois
Florida
Alabama
Georgia
Mississippi
Tennessee
Arkansas

How many lines does the program read before the error happens?
How many calls to insert() are made? How many State objects are created?
Try debugging by adding some printlns to show the execution flow and the data that is read.

It is only reading Maine and nothing else. It looks like it is looping only on Maine until it gets this error.

It is reading all the lines. All state objects are created, but insert() is looping Maine.

How many State objects are created in the insert() method? Can you post the debug output that shows what State objects are created?

Why is insert() looping with Maine?
What will stop the looping?

I stopped the looping with changing the insert of the hashTable class

public void insert(State item) // insert a DataItem
   // (assumes table not full)
      {
      String key = item.getStateName(); 
      // extract key from object to be inserted into table
      int hashVal = hashFunc(key);  // hash the key (hopefully, cell is empty).  
      while(hashArray[hashVal] == null &&  // implies location is occupied
                 hashArray[hashVal] == null)
      {
          hashArray[hashVal] = new LinkList();    // insert item

      }// if open, insert value
          hashArray[hashVal].insert(new State(key)); 
          //insert into current linked list
      }  // end insert()

Now I get an output

project5mitchell.LinkList@a90653
project5mitchell.LinkList@de6ced
project5mitchell.LinkList@c17164
project5mitchell.LinkList@1fb8ee3
project5mitchell.LinkList@61de33
project5mitchell.LinkList@14318bb
project5mitchell.LinkList@ca0b6
project5mitchell.LinkList@10b30a7
project5mitchell.LinkList@1a758cb
project5mitchell.LinkList@1b67f74
project5mitchell.LinkList@69b332
project5mitchell.LinkList@173a10f
project5mitchell.LinkList@530daa
project5mitchell.LinkList@a62fc3
project5mitchell.LinkList@89ae9e
project5mitchell.LinkList@1270b73
project5mitchell.LinkList@60aeb0
project5mitchell.LinkList@16caf43
project5mitchell.LinkList@66848c
project5mitchell.LinkList@8813f2
project5mitchell.LinkList@1d58aae
project5mitchell.LinkList@83cc67
project5mitchell.LinkList@e09713
project5mitchell.LinkList@de6f34
project5mitchell.LinkList@156ee8e
project5mitchell.LinkList@47b480
project5mitchell.LinkList@19b49e6
project5mitchell.LinkList@10d448
project5mitchell.LinkList@e0e1c6

It must not be storing them correctly now.

wait that's because my method for display is wrong because of the linked list. I got it fixed and it works. Thanks for your help. For now this is solved.

Quick question: Is it supposed to print out like this because it is a hashtable?

Table:






Indiana






California
New_York
Texas


New_Jersey
Oklahoma


Maine
Mississippi




Illinois
Virginia






Alabama






Colorado
New_Hampshire


Georgia
Pennsylvania




Maryland
West_Virginia




Florida
Rhode_Island




Vermont


Tennessee


Arkansas
Massachusetts






Connecticut
Delaware

Is it supposed to print out like this

What is printed is up to the programmer. What do you want printed?

I am supposed to print out the hashtable data not the codes. I think I was told it will have spaces, but I don't remember. My new display is...

public void displayTable()
{   
  System.out.print("Table:\n");
  for(int index=0; index < arraySize; index++)
  {
     hashArray[index].displayForward();
     System.out.println("\n");
  }// end for
}// end displayTable()

The display Forward is...

 /**
 * Displays Linked List forwards
 * 
 * @param none
 * @return void
 */
public void displayForward()
  {
  State current = first;          // start at beginning
  while(current != null)         // until end of list,
     {
     System.out.println(current.getStateName());      // display data
     current = current.next;     // move to next link
     } //end while
  } //end displayForward()

So I only have one \n so it is a little nicer looking.

Ok I got clarification. If the Hash Table entry has no entries then it will be emptied. I do have to show the hash table indexes 0-29.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.