动态哈希[高速缓存]

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可能值得一看。