algorithm - 哈希表的数组大小？

Question

我正在阅读一本关于算法的书，以找到更好的列表替代方案。书中提到哈希表的数组大小必须是需要添加的项目大小的两倍。但是，在讨论单独的链接时没有提及数组大小。数组大小是否仍然必须是要添加的项目的两倍？由于每个索引可以包含多个项目，因此它可以与项目的大小相同吗？这会影响性能吗？

Answer 1

如果链接哈希表的大小与探测相比并不重要，但是将键映射到存储桶的哈希函数很重要，因为如果哈希函数不能均匀地分配表中的键，那么您最终可能会进行线性搜索对于一个元素。推荐任何 O(N) 的表大小，如 (1,1/2,1/4..) 以获得 O(1) 搜索和插入提供的哈希函数必须均匀分布表中的数据。

Answer 2

这取决于您的内存/速度权衡要求。对于链式方案，我建议使用哈希表大小作为键数量的 1/2..1/4。如果您保持每个链接列表按键排序，那么每次查找大约有 1-2 次比较。

此外，为了提高性能，您可以使用“屏障元素”。这是一个特殊节点，包含“屏障值，大于所有可能的键”，并且所有 liknkist 的最后一个元素不是指 NULL，而是指那个屏障节点。

通过这种方式，您不需要比较指向“链接列表是否结束”的指针，您只需要比较键（列表已排序）：

for(node *p = table[hash]; p->key < search_key; p = p->next);
return p->key == search_key? p : NULL;