我已经在C语言中实现了自己的哈希表函数,但目前它不支持调整大小。 我想知道除了创建一个新的空哈希表并将所有内容移动到那里的暴力方式之外还存在哪些算法?
有增量调整大小的功能。
来自维基百科:
增量调整大小
一些哈希表实现,特别是在实时系统中,不能承担一次性扩大哈希表的代价,因为它可能会中断时间关键操作。如果无法避免动态调整大小,则解决方案是逐步执行调整大小:
在调整大小期间,分配新哈希表,但保持旧表不变。 在每个查找或删除操作中,检查两个表。 仅在新表中执行插入操作。 每次插入时,从旧表中移动r个元素到新表中。 当旧表中的所有元素都被删除时,释放它。
为确保在需要扩大新表之前完全复制旧表,必须在调整大小期间将表的大小至少增加(r + 1)/ r倍。
因此,这并不是将所有元素从旧表移动到新表的聪明方法(如果有的话,我还没有看到);相反,它通过允许逐步迁移来减轻调整大小的负担。