hash_map作爲鍵存儲什麼？

Question

我有一個無限的數字流來，我必須檢測第一個重複的元素。我想爲上述問題使用散列表，即每當數字到達時，檢查它是否已經存在於散列表中。如果有，停止，否則將該數字添加到散列表。現在我的問題是哈希表是否存儲整數值或只有對應於這些整數的哈希值作爲關鍵？

在此先感謝

Answer 1

的hash_map是hashed associative container，這意味着它們一鍵的值相關聯。所以是的，你給它的值存儲在hash_map中。通常，你沒有直接訪問散列碼。要使用hash_map解決您的問題，當您獲取myInt時，您將不得不執行類似myHashMap[myInt] = true;的操作。然後對於下一個int，你將不得不檢查你的int是否已經存儲...

因爲你只是要檢查它是否在這裏或不是最好的選擇。一套似乎很合適。您可能必須檢查抓取操作的性能，但我認爲它在STL集合中進行了優化。

MY2C

Answer 2

散列函數是用來放置一對<key,value>，所以當插入數作爲密鑰，它獲得存儲在由與作爲值相關聯的數據的功能分配的位置。

你只需要嘗試獲得該整數作爲一個關鍵，並增加它的價值。

Answer 3

答案取決於實現約束條件，但如果數字是int32或更小，我首選的方法是懶惰分配512MB（因此，如果您使用它，則會分配單個物理頁面，/ dev的私有mmap/zero是unix下的傳統方法）並將其用作bitset。如果字的大小較小，那麼你將不得不求助於某種散列（可能是多層次），k-tree樹的變體或上述的某種組合。

注意，多層次的散列或

如果你正在看什麼比一個Int32你大沒有提供足夠的信息，以提供建議。如果你無法負擔你的bitset的512MB內存，這同樣適用。