動態哈希[高速緩存]

Question

無論編程語言如何，我都在想我即將實現的東西不錯。我有數百萬的int64 ID和double值存儲在一個哈希表中。我想先嚐試某種動態哈希。這是我在想什麼：

• 要嘗試一個固定的大小（即100K）的形式<hashedID, value>的哈希值，併爲這個哈希表的每個單元 我店也有同樣的 哈希鍵和一個列表中的另一hastable ，像這樣：<hashedID, [ID,count]>。

• 假設ID_1是第一個和第二個哈希表的特定單元中的駐留元素。現在對於新到達的條目，如果它散列到相同的散列ID，我檢查：如果它具有與現有ID_1相同的ID（我通過第二個散列表檢查），如果是，則增加計數。如果沒有，那麼我減少計數。如果減少計數後計數爲0，我會用剛剛到達的ID替換它。

這樣我希望有流行的東西留在第一個哈希表。

Answer 1

這讓我想起了帶有外部鏈接的哈希表的移動到前端啓發式 - https://en.wikipedia.org/wiki/Hash_table說：「如果加載因子很大，並且某些鍵比其他鍵更有可能出現，則重新排列鏈移動到前端的啓發式可能是有效的，更復雜的數據結構，如平衡搜索樹，只有當負載因子很大（大約10或更多），或者散列分佈可能非常非常或者即使在最糟糕的情況下也必須保證良好的性能，但在這些情況下使用更大的表和/或更好的哈希函數可能會更有效。另請參閱http://www.seg.rmit.edu.au/code/zwh-ipl/。

如果k個條目散列到同一個槽中，則只有其中一個條目可以成爲快速查找的優先條目，因此如果它們都具有大致相同的搜索概率，則使最受歡迎的條目花費0次將獲得只有k /（k-1）的因子。

如果您有興趣實現稍微不標準的散列表例程，https://en.wikipedia.org/wiki/Cuckoo_hashing可能值得一看。