如何搜索哈希表？

我剛開始學習哈希表，我知道如何插入，但不知道如何搜索。這是我將立足這個問題，關閉算法：如何搜索哈希表？

哈希鍵

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

如何搜索哈希表？

回答

相關問題