0

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

您首先创建一个包含所有数据的数组，并按键对它们进行排序。我使用公式 K % size 在数组中找到键所在的位置。如果您将密钥提交到已经存在密钥的位置，则称为冲突。这就是双倍的用武之地。我使用公式 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;
   }

}

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

4

1 回答 1

0

现在我很困惑如果我递减并降落在另一个已经放置了密钥的位置上会发生什么。在找到位置之前，我会再次减少那么多吗？

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

您不只是检查条目是否为NULL. 您还需要检查它是否包含正在插入的相同密钥。将密钥存储在哈希表中是必不可少的，因此您可以确定您搜索的密钥就是您找到的密钥。

请注意修改表索引而不强制它位于数组边界内。例如，如果item是0然后你减去1，你将有一个越界索引。

您可以像这样更正：

item = (item - dec + hash->size) % hash->size;
于 2013-11-26T04:04:33.487 回答