data-structures - 链式哈希集的负载因子

Question

我被分配去实现一个链式哈希集:

该集合由一组链表支持(我称之为A[])，如果两个不同的值得到相同的散列值k 它们被添加到列表 A[k]。

该结构在有界负载因子(区间 [0.25, 0.75])下工作正常。

在说明中，他们告诉我们计算负载因子为:

Load Factor = size/capacity

其中“大小”是集合中当前元素的总数，“容量”是数组的长度 (A.length)。

我认为“大小”的这个定义在这种情况下不合适，应该是 A 中使用的列表数。

例如，如果所有值都映射到同一个单元格，比如 A[1]，那么当根据负载因子重新散列时，我们将创建返回数组 A 当实际上只使用第一个单元格时更大。

有人看到我的逻辑有什么错误吗？

Answer 1

散列通常被修改为转换为数组索引，因此，当增加数组的大小时，元素很可能不会再次出现在同一个链表中(至少它们不应该如果您使用适当的哈希函数)。

此外，负载因子的含义将发生相当大的变化。正如它所定义的那样，它将给出链接列表中项目的平均数量的一些指示，这是一个非常重要的数字，因为这是检索项目所需的时间(平均)。

无论好坏，哈希表依赖于合理的哈希分布，因此假设一个列表与其他列表相比不会变得太大。

存储用于指示哈希函数质量的索引数量也很有意义，但我认为没有太大意义。 API对此无能为力(因为它不处理散列函数，它只是调用它)。如果使用错误的散列函数，则在调用代码中动态更改散列函数似乎不太实用。