问调整哈希映射的大小

EN

我建议使用Paul Larson推广的算法，该算法一次拆分一个桶。它的工作原理如下：

您可以确定平均每个哈希桶的条目数。您可以跟踪您拥有的条目数以及您拥有的存储区数量。

假设你有四个水桶。您将每个元素放在一个桶中，方法是使用散列模式4。

现在说每个哈希桶的条目超出了你想要的平均值。你现在从四个桶增加到五个。你这样做如下：

1. 你添加了第五个桶。它开始是空的。
2. 您将算法从更改hash%4为(hash % 8) % 5。
3. 这增加了第五个桶。
4. 您重新搜索第一个存储桶中的所有条目，因为它们中的一半现在需要进入存储桶5.（这通常是一个固定成本，因为您的每个存储桶平均值是一个常量。

这会让你的水桶不均匀。铲斗1和铲斗5的铲斗数量将是铲斗2,3和4的一半。但是当你获得第8个铲斗时，它们将会再次出现。

为简单起见，您可以将每个存储桶实现为链接列表。

另一种方法是很少重新进行重新散列，并重新进行每一个条目的重新散列。