c - 哈希表 : double probe when collision

Question

我目前正在研究哈希表，对双重哈希有点困惑。首先让我从我得到的信息开始。

首先创建一个数组来保存所有数据，并且它们按键排序。我使用公式 K % size 来查找键在数组中的位置。如果您将 key 提交到已经存在 key 的位置，则称为冲突。这就是 double 出现的地方。我使用公式 max(1,(K/size) % size) 来获取一个将从该位置递减的数字。

所以我想出了这些函数:

int hashing(table_t *hash, hashkey_t K)
{
    int item;
    item = K % hash->size;
    return item;
}

int double_hashing(table_t *hash, hashkey_t K)
{
    int item;
    item = K/hash->size % hash->size);
    return item;
}



//This is part of another function which involves the double.
else if(hash->probing_type == 2)
{
   int dec, item;
   item = hashing(hash,K);
   if(hash->table[item] == NULL)
   {
        hash->table[item]->K == K;
        hash->table[item]->I == I;
   }
   else
   {
        dec = double_hashing(hash,K);
        hash->table[item-dec]->K == K;
        hash->table[item-dec]->I == I;
   }

}

所以我使用这两个公式来移动按键。现在我很困惑，如果我减少并降落在已经放置了 key 的另一个位置，会发生什么。我是否会再次递减那么多，直到找到一个位置？

Answer 1

Now I am confused to what happens if I decrement and land on another spot in which a key is already placed. Do I decrement again by that much until I find a place?

是的。如果您的哈希表大小是质数并且该表未满，您最终将为新条目找到可用空间。

您不只是检查条目是否为NULL。您还需要检查它是否包含与正在插入的相同的 key 。将 key 存储在哈希表中至关重要，因此您可以确保您搜索的 key 就是您找到的 key 。

请注意修改表索引而不强制其位于数组范围内。例如，如果 item 为 0，然后减去 1，则会出现越界索引。

您可以像这样更正此问题:

item = (item - dec + hash->size) % hash->size;