java - 计算合并重复项的哈希表中的负载因子？

Question

对于一个项目，我正在创建一个字符串哈希表。它使用单独的链接，并且为表中的每个填充位置创建一个链表。该链表包含一个节点，该节点存储字符串及其频率。因此，当插入字符串时：

1.) 如果它与另一个字符串的哈希匹配，并且当前字符串不在表中，它将在该哈希值处附加到列表中，并且频率为 1。

2.) 如果表中已有该字符串的副本，则该字符串的频率将增加。

我将如何计算此表的负载因子？它会是哈希表中位置总数的节点数（这不包括列表）。或者，它是频率总和除以哈希表中的位置数吗？-谢谢！

Answer 1

计算负载因子，以便在表格中的元素数量增长过大时表格可以自行调整大小。高负载因子意味着查找可能需要很长时间，因为（平均而言）需要搜索更多元素。

在您的情况下，如果您通过跟踪每个项目的频率来存储重复项，则将重复项包含在负载因子中是没有意义的。毕竟，在每个项目的频率为 10 ¹⁰⁰的桶中查找项目所花费的时间与在每个项目的频率为 1 的桶中查找项目所花费的时间相同。

我会将负载因子计算为唯一项目的数量除以存储桶的数量，因为这可以为您提供有关预期查找时间的最准确信息。

希望这可以帮助！