如何創建一個散列表

我想在繼續之前提到我已經看過其他問題，在本網站以及其他網站上詢問同樣的事情。我希望我能得到一個很好的答案，因爲我的目標是雙重的：如何創建一個散列表

首先，我想了解如何創建一個哈希表。
其次，我發現Stack Overflow上的很多答案傾向於假設對某個主題的某種程度的知識，而這個主題經常不存在，特別是對於較新的類型。話雖如此，我希望編輯我的主要信息，以便在我自己弄清楚的情況下，更深入地解釋這一過程。

到主過程：

正如我理解他們到目前爲止，哈希表是列出的陣列（或類似的數據結構），該希望，最佳，具有少碰撞以儘可能地保持它被稱讚的O（1）複雜性。以下是我的當前進程：

所以我的第一步是建立一個指針數組：

Elem ** table; 
table = new Elem*[size];//size is the desired size of the array

我的第二個步驟是創建一個散列函數（一個非常簡單的一個）。

int hashed = 0; 
hashed = (atoi(name.c_str()) + id) % size; 
//name is a std string, and id is a large integer. Size is the size of the array.

我的第三個步驟是創建一些檢測碰撞，這是目前在我的部分。

下面是一些僞代碼：

while(table[hashedValue] != empty) 
    hashedValue++ 

else 
    put in the list at that index.

這是比較粗俗，但我仍然在「這是什麼」的階段。忍受着我。

還有別的嗎？我錯過了什麼或者做錯了什麼？

由於

來源

2011-11-20 Joshua

看起來不錯，有點。散列值索引到一個固定數組中，每個數組元素是一個實際值列表。 –

手柄發現沒有空閒時隙，並調整表。

來源

2011-11-20 23:42:28

你錯過了Elem的定義。這不是微不足道的，因爲它取決於你是想要一個chaining還是一個探測哈希表。

來源

2011-11-20 23:44:01

對不起，我有一個我沒有提供的定義。這是一個鏈表。 – Joshua

@Joshua：假設你不想存儲重複數據，那麼碰撞檢測只是一個走這個列表的問題。 –

散列函數爲相同的數據產生相同的值。然而，您的碰撞檢查會修改該值，這意味着哈希值不僅取決於輸入，還取決於哈希映射中其他元素的存在。這很糟糕，因爲您幾乎永遠無法通過遍歷地圖來實際訪問之前放入的元素。其次，你的碰撞檢查容易出現溢出/範圍錯誤，因爲你只是增加散列值而不檢查映射的大小（儘管如前所述，你甚至不應該這樣做）。

來源

2011-11-21 00:44:59 Xeo

我想我沒有提供足夠的信息，對不起。我哈希的對象有一個私有名稱和ID，所以它們都始終存在於對象中。 – Joshua

@Joshua：這不是我的意思。在你的碰撞檢查中，如果你的計算點不是免費的（只要下一個點不是免費的），就可以改變哈希值。這意味着，根據哈希映射的負載，對於相同的數組大小，如果在生成相同哈希值之前插入的另一個元素（即發生衝突），則可以將該元素插入到不同的位置。這將不允許您通過插入它的同一個鍵訪問該元素。 – Xeo

如何創建一個散列表

回答

相關問題