java - 无法让我的哈希算法正常工作

Question

问题已解决（尚不能接受答案，我更改了我的 while 循环，现在它可以工作了，我在下面为任何未来的观众回答了它）：我的散列算法让我头疼。我从文件中读取键的输入，并且使用少量键，我的代码就可以工作，一旦我把它写成 300 个字，我就有问题了。散列函数在底部，而这个 while 循环在我的 main 函数的主体中，它是用 java 编写的。散列函数运行良好，主体也运行良好，直到我愚蠢地更改了主体并丢失了原始代码。我想我涵盖了溢出问题，但任何帮助将不胜感激，谢谢！

如何计算 tSize：

//Calcking tSize
tSize = (int)(items*tSizeFactor);

//Making tSize prime
while(!isPrime((int)tSize))
    tSize++;

当我从文件中读取时循环：

while(line != null) {
                //Getting the address to place the value in
                position = hash(line.toCharArray(), (int)tSize);

                //If there is something there we enter the if statement
                if(hashTable[position][0] != null) {
                    //while we haven't found a spot and i < tableSize we update the last position we were at and move through the array
                    for(int i = 1; i < (int)tSize && hashTable[position][0] != null; i++) {
                        //prevPosition is used to update the link in the spot just before our final destination, allows wrap around in the array
                        prevPosition = position;
                        //we add +i to the original position and modulo the table size allowing wrap around in the array
                        position = (position+i)%(int)tSize;
                    }
                    //finally when we found a spot we update the previous position to link to the new item
                    hashTable[prevPosition][1] = Integer.toString(position);
                }

                //Adding the values to the hash table and setting the link to -1
                hashTable[position][0] = new String(line);
                hashTable[position][1] = new String(Integer.toString(-1));

                line = reader.readLine();
            }

public static int hash(char ch[],final int TSIZE) {
        int sum = 7;
        for(int i = 0; i < ch.length; i++) {
            sum = sum*31+ch[i];
            sum <<= 3;
        }

        if(sum < 0)
            sum *= -1;

        return sum%TSIZE;
    }

score 0 · Accepted Answer

new String(line) 没用。
for(int i = 1; i < (int)tSize && hashTable[position][0] != null; i++)

没有使用位置 0？
prevPosition 可以在本地进行if(hashTable[position][0] != null) {阻止。
将 Prev 位置存储到哈希表中看起来毫无用处。

UPD
位置 = (位置+i)%(int)tSize;

试试这个 http://en.wikipedia.org/wiki/Quadratic_probing

score 0 · Accepted Answer

首先，一个问题，为什么不使用内置哈希表？

通过阅读您的代码，我发现了一些问题。它们可能不正确，因为从您当前的代码中无法知道更多信息。例如tSize.

你有一个tSize，我认为它是哈希表的容量。但我没有看到你什么时候增加它。这将是一个问题，至少是性能问题。但在您的实施中，这是功能问题。例如，如果您的 tSize 为 100。那么您的哈希表中最多可以有 100 个元素。

看看这个 for 循环：

for(int i = 1; i < (int)tSize && hashTable[position][0] != null; i++) {
    prevPosition = position;
    position = (hash(line.toCharArray(), (int)tSize)+i)%((int)tSize);
}

这将在发生碰撞时执行。（我不明白，为什么你再次调用哈希函数。你可以循环找到一个空闲槽。）你想保留原来的key，并让它引用一个空闲位置。但是，如果在更糟糕的情况下，在您再次调用哈希函数后，新position的仍然被占用（再次发生冲突），您会覆盖prePosition原来的key. 当您从哈希表中获取数据时，这将是一个问题。

由于以上两点。当您的哈希表已满时，您的代码只是不断覆盖最后一个元素。

score 0 · Accepted Answer

我改变的while循环解决了这个问题：

while(line != null) {
                    //Getting the address to place the value in
                    position = hash(line.toCharArray(), (int)tSize);

                    //If there is something there we enter the if statement
                    if(hashTable[position][0] != null) {

                        //Go to the end of the chain
                        while(hashTable[position][1].compareTo("-1") != 0)
                            position = Integer.parseInt(hashTable[position][1]);

                        //Save the position of the end of the chain
                        prevPosition = position;

                        //while we haven't found a spot and i < tableSize we update the last position we were at and move through the array
                        for(int i = 1; i < (int)tSize && hashTable[position][0] != null; i++) {
                            //we add +i to the original position and modulo the table size allowing wrap around in the array
                            position = (position+i)%(int)tSize;
                            System.out.println("Position: " + position);
                        }

                        //finally when we found a spot we update the previous position to link to the new item
                        hashTable[prevPosition][1] = Integer.toString(position);
                    }

                    //Adding the values to the hash table and setting the link to -1
                    hashTable[position][0] = new String(line);
                    hashTable[position][1] = new String(Integer.toString(-1));

                    line = reader.readLine();
                }

java - 无法让我的哈希算法正常工作

3 回答 3

Related

Reference