java - 哈希表中的冲突解决

Question

我正在尝试用 Java 构建自己的哈希表实现，以便更好地掌握哈希的工作原理。我使用单独的链接并增长表，并在负载超过 75% 或我有一条长度超过 20 的链时重新哈希所有内容。我正在散列字符串。我已经尝试了我能想到的一切，但是当我尝试构建表时，它会运行几秒钟，然后在我的增长方法中抛出 StackOverflowError 。

这里是实际 HashTable 的代码，其中包括实际表的 arrayList 和一些用于跟踪最长链、冲突次数和大小的整数。它还包括插入、增长(重新散列新 arrayList 中的所有内容)、散列字符串以及查找高于给定数字的素数以及 getter/setter 的方法。

    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;
    }
}

下面是实际构建表的方法的代码，它采用所有单词的 arrayList 并将它们插入到数组中(对它们进行哈希处理)并检查加载/碰撞长度并在需要时增加它。

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;
    }

抱歉，有很多代码需要整理，但我无法弄清楚我在这里做错了什么，并且不知道如何将其压缩。非常感谢任何帮助!

Answer 1

在您的 insert 方法中，您应该使用以下内容来跟踪最长的链

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

这解释了为什么它运行了几秒钟，然后遇到 StackOverflowError，您无限递归，因为 longest 的值没有改变(因为 this.hashes.size() 不会改变)