我在附带的代码中实现了线性探测。我们如何修改它以便处理负值？例如，如果 -1 是一个条目

Question

我正在尝试实现线性探测。我想知道这种技术是如何处理负值的。在下面的代码中，我编写了一个正值函数。另外，如果 -1 是数组中的一个元素怎么办？我们将如何处理？

int[] linearProbing(int hash_size, int arr[], int sizeOfArray)
    {
        //Your code here
        int []table = new int[hash_size];
        
        for(int i=0;i<hash_size;i++){
            table[i] = -1;
        }
        
        int key = 0;
        for(int i=0;i<sizeOfArray;i++){
            key = arr[i] % hash_size;
            if(table[key] == arr[i]){
                continue;
            }
            
            if(table[key] == -1){
                table[key] = arr[i];
            }
            else{
                int k = 1;
                int j = (key+k) % hash_size;
                while(table[j] != -1){
                    if(j == key){
                        return table;
                    }
                    if(table[j] == arr[i]){
                        break;
                    }
                    else{
                        k++;
                        j = (key+k) % hash_size;
                    }
                }
                table[j] = arr[i];
            }
        }
        return table;
    }

Answer 1

第一个问题是您使用 -1 标记 table 中的空闲位置。为了解决这个问题，您需要一些其他结构来存储空闲插槽。一个想法是 boolean[] 与您的 table.

长度相同

现在，不是使用 table[key] == -1 检查插槽是否空闲，而是使用新的 boolean[] 检查它（false 表示空闲插槽）。如果存储新值，则必须将数组值设置为 true（意味着存储了一个值）。

还有一点你要考虑的是key的生成（key = arr[i] % hash_size），如果要存储的值是负数，key就是负数。问题是您的 table 无法处理否定键。一个简单的解决方案是使用密钥的绝对值。例如：key = Math.abs(arr[i] % hash_size)

如果您实现这些功能，您的函数也将能够处理负值。

我在附带的代码中实现了线性探测。我们如何修改它以便处理负值？例如，如果 -1 是一个条目

I have implemented Linear Probing in the attached code. How can we modify it such that even negative values are handled? For eg if -1 was an entry

java

hash

data-structures

linear-probing