散列方法允许增加桶的数量，而不会弄乱之前的数据映射

Question

是否有一种算法/方法可以让我在不重建数据/重新散列的情况下增加存储桶的数量。

实践中的问题： 假设您有一群由字符串“用户名”标识的用户。 然后，您将这些“用户名”散列到存储桶列表中。

This is done by something like:
String username = "user";
int index = username.hash();
int bucketIndex = index % bucketlist.size();

因此，在这个方案中，如果我想增加“桶”的数量，那么还需要移动桶中的数据。这样它就可以与用不同的数字取模得到的新桶索引相匹配。

这实际上只是一个映射。在哪里可以找到属于给定用户的存储桶。

可能的愚蠢解决方案： 具有旧的存储桶尺寸和新的存储桶尺寸。然后尝试在两个桶中查找。 然后使用 new bucketlist.size() 慢慢移动所有用户，使其匹配。这不需要在散列和移动时完全停止。

需要什么： 确实是所有用户的举动都不好。在许多桶中寻找正确的桶也并不理想。

重点是能够仅通过使用算法来确定要使用列表中的哪个存储桶。

并且不可能将存储桶列表的大小作为用户名的一部分。

如果它的作用大致相同，则不需要像这里所做的那样进行散列。

我不知道这个问题是否有任何明智的答案......

Answer 1

有什么方法可以将哈希集的大小预先调整为适合您的数据的大小 - 从而消除或几乎消除重新哈希的需要？另外，即使出现一些重叠，只要冲突不会太深，每个节点的链表或类似的东西进行散列也不会造成太大的伤害。

Answer 2

我认为您正在寻找线性哈希。

您还可以考虑多种平衡二叉树中的任何一种。它们有一个很好的特性，你可以继续种植它们，而无需在任何时候重新安排世界。