我正在处理一个效率至关重要的项目。由于需要根据键轻松查找节点的内存地址,因此哈希表非常有用。我预见到的唯一问题是这个哈希表将需要处理高达100万个条目。通常哈希表桶是一个链接列表,以便可以处理同一个桶中的多个条目。但在我看来,对于100万个条目,这些列表会变得非常慢。那么,实现这样的东西的常见方法是什么?也许可以将标准链表替换为跳表?
我正在处理一个效率至关重要的项目。由于需要根据键轻松查找节点的内存地址,因此哈希表非常有用。我预见到的唯一问题是这个哈希表将需要处理高达100万个条目。通常哈希表桶是一个链接列表,以便可以处理同一个桶中的多个条目。但在我看来,对于100万个条目,这些列表会变得非常慢。那么,实现这样的东西的常见方法是什么?也许可以将标准链表替换为跳表?
如果每个桶的列表中有超过几个条目,那么散列表就失去了所有优势。通常使散列表扩展到数百万个条目的方法是使主散列数组可调整大小,因此即使有数百万个条目,桶列表也会保持较短的长度。
在每个“桶”中,您可以使用一棵树而不是列表。(AVL或类似)
编辑:跳表也可以。 (看起来更快)- O(log n)是您的目标。
总条目数并不重要,只有每个桶的平均条目数(N / 哈希表大小)才重要。使用具有更大域(例如20位或更大)的哈希函数来确保这一点。
当然,这将占用更多内存,但这是常见的内存与速度之间的权衡。
如果你的键具有正态分布(这是一个非常大的假设),那么用于耗尽哈希表中所有桶的插入次数的期望值为M*logM(自然对数,以e为底),其中M是桶的数量。
很惊讶在网上找不到这个信息!
我已经在我的博客上发布了同样的推导,并使用rand()进行了验证。它似乎是一个相当好的估计。