data-structures - 如何在我的哈希表中保持较小的负载因子？

Question

我正在学习哈希表和特别是二次探测。我已经读过，如果负载因子 <= 0.5 并且表的大小是素数，则二次探测将始终找到一个空槽，并且不会多次访问任何键。然后继续说，为了确保有效插入，我应该始终保持负载因子 <= 0.5。这是什么意思？当然，如果我们继续添加项目，无论我们是否愿意，负载因子都会增加直到等于 1。那么当我的教科书说我应该保持一个小的负载因子时，这意味着什么？

Answer 1

这意味着在某些时候（在这种情况下，当您将超过 0.5 的负载因子时），您将不得不分配一个新表（它比某个因子大，可能是 1.5 或 2，然后四舍五入到最接近的素数）并将旧表中的所有元素复制到其中（这不是直接复制，项目的新位置通常与旧位置不同）。