有哪些算法可用于调整哈希表的大小?

来自维基百科:

一些哈希表实现, 特别是在实时系统中,不能 一次把所有的东西都放在桌子上,因为它可能 中断时间关键型操作。如果 人们无法避免动态调整大小,例如 解决方案是执行大小调整

在调整大小过程中,分配新的 哈希表,但保留旧表 不变。 在每个查找或删除操作中,选中两个表。 每次插入时,还将r元素从旧表移动到新表 桌子 从旧表中删除所有元素后,将其取消分配。

在新文件之前完全复制过来 这张桌子本身需要放大 是否有必要增加 该表的系数至少为(r+

维基百科有一些 words of wisdom

此外,它不是一个解决方案,但可能是其中的一部分-如果您在windows下,您可能会使用VirtualAlloc函数系列,它允许您保留地址空间,而无需实际提交内存页。也就是说,用外行的话说,你会做一些类似于“malloc”的事情,并告诉它“保留1000MB,但只提供前10个”。因此,如果您写入超过10MB的数据,您将得到通常的崩溃。但当需要扩展时,您只需说“好的,在第一个10MB之后再给我一个10MB”。下一个10MB地址直接位于前一个10MB地址之后。这就像调整数组的大小一样。实际使用的RAM将仅为您所需的数量,但内存地址将提前保留,以便其他内存分配操作不使用它们。

通常的逃避方式是让客户机代码预先猜测最佳桶数。这是可以使用的,客户通常可以合理地猜测表中有多少元素。如果您想自动执行此操作,那么首先必须为桶大小声明一个素数数组。当您看到一个bucket的负载因子变得过高时,选择数组中的下一个素数,重新创建bucket列表,并将元素从旧bucket移动到新表中。