如何搜索哈希表？

Question

我刚刚开始学习哈希表，我知道如何插入，但不知道如何搜索。以下是我将基于这个问题的算法：

散列密钥

int Hash (int key) {
    return key % 10;  //table has a max size of 10
}

线性探测碰撞分辨率。

假设我用键1、11和21调用两次插入。这将返回所有3个键的槽1。冲突解决后，表在槽1、2和3处将有值1、11和21。这就是我对插入的理解。

完成此操作后，如果搜索键11和21，我将如何获得插槽2和3？从我所读到的内容来看，搜索哈希表应该做与插入完全相同的事情，除非当你到达所需的插槽时，你在该插槽返回值，而不是在其中插入内容。

如果我从字面上理解并应用相同的算法，如果我搜索密钥11，我会到达插槽4，因为它会从插槽1开始，一直向前探测，直到找到一个空插槽。它不会停在插槽2，即使这是我想要的，因为它不是空的。

即使我使用单独的链接，我也在努力解决这个问题。所有3个键都将存储在插槽1，但使用相同的算法搜索将返回插槽1，而不是链表中的哪个节点。

Answer 1

我通常更喜欢把表中的每个条目都做成一个结构，这样我就可以创建一个链表来处理冲突。这大大减少了碰撞。像这样的。

struct hashtable
{
    int key;
    struct hashtable *pList;
};

struct hashtable ht[10];

void Insert(int key);
{
    index = Hash(key);
    if (!ht[index].key)
    {
        ht[index].key = key;
        ht[idnex].pList = 0;
    } 
    else
    {
        struct hashtable *pht;
        pht = ht[index].pList; 
        while (pht->pList)
            pht = pht->pList;
        pht->pList = new struct hashtable;
        pht->pList->key = key;
        pht->pList->pList = 0;
    }
    return;
}

当然，如果查找函数没有找到第一个条目的键匹配项，它就必须遍历列表。如果性能非常关键，您可以使用其他策略来处理链表，例如对它们进行排序和使用二进制搜索。

Answer 2

每个槽存储一个键/值对。当您搜索每个槽时，检查键是否与您搜索的键相等。停止搜索，并在找到相等的键时返回值。

使用单独的链接，您可以对列表进行线性搜索，根据列表中的每个键检查键。