我已经在所附代码中实现了线性探测。我们如何修改它以便处理负值？例如，如果 -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 来标记表中的空闲槽。为了解决这个问题，您需要一些其他结构来存储空闲槽。一种想法是使用与表长度相同的 boolean[] 。

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

您必须考虑的另一点是密钥的生成（key = arr[i] % hash_size），如果要存储的值为负数，则该密钥将为负数。问题是您的表无法处理负键。一个简单的解决方案是使用密钥的绝对值。例如： key = Math.abs(arr[i] % hash_size)

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