2

我刚刚开始学习哈希表，我了解如何插入但不了解如何搜索。这些是我将根据这个问题提出的算法：

散列密钥

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

用于解决冲突的线性探测。

假设我使用键 1、11 和 21 调用 insert 两次。这将为所有 3 个键返回插槽 1。解决冲突后，表格在插槽 1、2 和 3 处的值将分别为 1、11 和 21。这是我假设根据我对插入的理解会发生的情况。

这样做之后，如果我搜索键 11 和 21，我将如何获得插槽 2 和 3？从我读过的内容来看，搜索哈希表应该做与插入相同的事情，除非当您到达所需的插槽时，您返回该插槽的值而不是向其中插入一些东西。

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

即使我使用单独的链接，我也在为此苦苦挣扎。所有 3 个键都将存储在插槽 1 中，但使用相同的算法搜索将返回插槽 1，而不是链表中的哪个节点。

4

2 回答 2

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;
}

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

于 2012-10-22T23:28:42.993 回答
1

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

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

于 2012-10-22T23:30:43.370 回答