java - 在 HashMap 或哈希表中重新哈希的成本

Question

我已经研究过这个相关问题 Rehashing process in hashmap or hashtable .但是我需要知道重新散列过程的执行情况。例如，如果负载系数是 .75；

1- 这是否意味着我们忘记了现有的哈希表，对于每个现有的条目，我们都将它们一个一个地获取，这次使用新的哈希函数将它们重新输入到一组新的桶中？

2- 如果是这样，那么重新散列的性能如何，比如说当有 n 个条目退出时。它是 O(n) 摊销的吗？

Answer 1

Does this mean that we forget about the existing hashTable and for every existing entry we get them one by one and reenter them into new set of buckets this time with a new hash function?

是的，当底层数组被认为太小时就会发生这种情况。我们必须重新计算每个条目的哈希值，因为新的哈希表根据其大小具有不同的压缩函数。

If that's so then what is the performance of rehashing, say when there are n entries exited. Is it O(n) amortized?

是的，对于前一个数组中的每个条目，都会计算一个新的哈希值并重新输入该条目。所以 O(n) 摊销了。根据桶链表的实现方式，最坏的情况可能是 O(n^2)，因为所有条目都可能进入同一个桶。