如何搜索哈希表？

我刚开始学习哈希表，我知道如何插入，但不知道如何搜索。这是我将立足这个问题，关闭算法：如何搜索哈希表？

哈希键

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

线性探测的冲突解决。

假设我打电话的钥匙1，11插入两次，和21这将返回插槽1为所有3个按键。在冲突解决之后，表格将在插槽1，插槽2和插槽3中具有值1,11和21.这是我对插入的理解会发生的事情。

这样做后，我将如何得到插槽2和3，如果我搜索键11和21？从我读过的内容来看，搜索哈希表应该与插入操作完全相同，除非当您到达期望的插槽时，您将返回该插槽的值而不是插入某个值。

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

我与这个挣扎，即使我使用单独的链接。所有3个密钥将存储在时隙1，但使用相同的算法进行搜索将返回时隙1，而不是链接列表中的哪个节点。

来源

2012-10-22 TreeTree

每个槽都存储一个键/值对。在您搜索每个插槽时，请检查密钥是否与您正在搜索的密钥相同。停止搜索并在找到相同的密钥时返回值。

设有独立的链接，你可以通过列表做线性搜索，检查，对列表中的每个关键的关键。

来源

2012-10-22 23:30:43 fgb

我不知道为什么我不认为我可以使用密钥本身。 – TreeTree

咦？我太想你的问题了。 –

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

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-22 23:28:42

如何搜索哈希表？

回答

相关问题