Collision Resolution in a HashTable

Question

I am attempting to build my own implementation of a hash table in Java in order to gain a better grasp on how hashing works. I am using separate chaining and growing the table and rehashing everything when the load gets over 75% or I have a single chain over 20 in length. I'm hashing strings. I've tried everything I can think of but when I attempt to build the table it runs for a few seconds and then throws a StackOverflowError in my grow method.

Here is the code for the actual HashTable this include the arrayList for the actual table and some ints to keep track of the longest chain the number of collisions and the size. It also includes methods to insert, grow (rehash everything in new arrayList), hash a string, and to find a prime number higher than a given number as well the getter/setters.

    import java.util.ArrayList;
import java.util.LinkedList;

public class HashTable {
    private ArrayList<LinkedList<String>> hashes;
    private int collisionCounter; //the total amount of collisions that have occurred
    private int longest; //the length collision
    private int size;

    public HashTable(int size) {
        this.hashes = new ArrayList<LinkedList<String>>();
        for (int i = 0; i < size; i++) {
            hashes.add(new LinkedList<String>());
        }
        this.collisionCounter = 0;
        this.longest = 0;
        this.size = size;
    }

    public int getCollisionCounter() {
        return collisionCounter;
    }

    public int size() {
        return this.size;
    }

    public int getLongest() {
        return this.longest;
    }

    //grows array to a new size
    public void grow(int newSize, int numElements) {
        ArrayList<LinkedList<String>> oldHashes = new ArrayList<LinkedList<String>>(this.hashes);
        this.hashes = new ArrayList<LinkedList<String>>();
        this.collisionCounter = 0;
        this.longest = 0;
        this.size = newSize;
        for (int i = 0; i < this.size; i++) {
            hashes.add(new LinkedList<String>());
        }
        for (int i = 0; i < oldHashes.size(); i++) {
            LinkedList<String> currentList = oldHashes.get(i);
            for (int q = 0; q < currentList.size(); q++) {
                this.insert(currentList.get(q));
            }
        }
        if (this.longest > 20 || this.load(numElements) > .75) {
            newSize = newSize + 20;
            newSize = this.findPrime(newSize);
            this.grow(newSize, numElements);
        }

    }

    //inserts into hashtable keeps track of collisions and the longest chain
    public void insert(String element) {
        int index = this.hash(element);
        this.hashes.get(index).add(element);
        if (index < this.size) {
            if (this.hashes.get(index).size() > 1) {
                this.collisionCounter++;
                if (this.hashes.size() > this.longest) {
                    this.longest++;
                }
            }
        }

    }

    //finds the first prime number that is larger that the starting number or the original number if that is prime
    //if used to find a new table size the int in the parameters will need to be incremented 
    public int findPrime(int startInt) {
        int newNum = startInt++;
        boolean isFound = false;
        while (!isFound) {
            boolean isPrime = true;
            int divisor = 2;
            while (isPrime && divisor < newNum / 2) {
                if (newNum % divisor == 0) {
                    isPrime = false;
                } else {
                    divisor++;
                }
            }
            if (isPrime) {
                isFound = true;
            } else {
                newNum++;
            }
        }
        return newNum;
    }

    public double load(int numElements) {
        return (numElements + 0.0) / (this.size + 0.0); //int division may be a problem
    }

    //helper method for insert and search creates hash value for a word
    public int hash(String ele) {
        char[] chars = ele.toCharArray();
        double hashCode = 0;
        for (int i = 0; i < chars.length; i++) {
            hashCode += chars[i] * Math.pow(5521, chars.length - i);
        }
        if (hashCode < 0) {
            hashCode = hashCode + this.size;
        }
        return (int) (hashCode % this.size);
    }

    //method to search for a word in hashtable finds a string in the hastable return true if found false if not found
    public boolean search(String goal) {
        int index = this.hash(goal);
        LinkedList<String> goalList = this.hashes.get(index);
        for (int i = 0; i < goalList.size(); i++) {
            if (goalList.get(i).equals(goal)) {
                return true;
            }
        }
        return false;
    }
}

Here is the code for the method that actually builds the table it takes an arrayList of all the words and inserts them into the array (hashing them as it goes) and checks the load/collision length and grows it if needed.

public static HashTable createHash(ArrayList<String> words) {
        int initSize = findPrime(words.size());
        HashTable newHash = new HashTable(initSize);
        for (int i = 0; i < words.size(); i++) {
            newHash.insert(words.get(i));

            if (newHash.load(i) > .75 || newHash.getLongest() > 20) {
                int size = newHash.size();
                size = size + 25;
                int newSize = findPrime(size);
                newHash.grow(newSize, i);
            }
        }
        return newHash;
    }

Sorry this is a lot of code to sort through but I cannot figure out what I am doing wrong here and don't know a way to condense it down. Any help is really appreciated!

Answer 1

In your insert method you should have the following instead for keeping track of the longest chain

if(this.hashes.get(index).size() > this.longest) {
    this.longest = this.hashes.get(index).size();
}

that explains why it runs for a few seconds and then hits a StackOverflowError, you are recursing infinitely because the value of longest isn't changing (since this.hashes.size() won't change)