2

假设我有一个包含 59 个元素的哈希表（每个元素值都是一个整数）。索引 15 是空白的，表的其余部分都是数据。根据我要插入的数字，二次探测公式永远不会达到元素 15！

假设我想插入数字 199（应该使用我在下面使用的 hashFunc() 函数散列到 22。：

public int hashFunc(int key)
{
    return key % arraySize; //199 % 59 = 22
}

public void insert(DataItem item)
{
    int key = item.getKey();      // extract the key (199)
    int hashVal = hashFunc(key);  // hash the key (22)
    int i = 1;

    //The while loop just checks that the array index isn't null and isn't equal to -1 which I defined to be a deleted element

    while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1)
    {
        hashVal = hashFunc(key) + (i * i); //This never hits element 15!!!
        i++;
        hashVal %= arraySize;      // wraparound when hashVal is beyond 59
    }

    hashArray[hashVal] = item;    // insert item
}
4

1 回答 1

4

这在二次探测哈希表中是预期的。使用一些模运算，您可以证明只有探测序列中的前 p / 2 个探测位置保证是唯一的，这意味着每个元素的探测序列可能不会访问表中的一半位置。

要解决此问题，您可能应该更新您的代码，以便在任何时候重新散列 p / 2 或更多表位置正在使用中。或者，您可以使用 Wikipedia 文章中建议的技术，即交替使用探针偏移的符号（+1、-4、+9、-16、+25 等），这应确保您可以击中每个可能的位置.

希望这可以帮助！

于 2014-05-27T16:45:26.990 回答