Bla*_*iev 5 c resize hashtable
我在C中实现了自己的哈希表函数,但目前它不支持调整大小.我想知道除了创建新的空哈希表并将所有内容移动到那里的蛮力方式之外还存在哪些算法？
有增量调整大小.
来自维基百科:
增量调整大小
一些哈希表实现,特别是在实时系统中,不能同时支付扩大哈希表的代价,因为它可能会中断时间关键的操作.如果无法避免动态调整大小,解决方案是逐步执行调整大小:
在调整大小期间,分配新的哈希表,但保持旧表不变.在每个查找或删除操作中,检查两个表.仅在新表中执行插入操作.在每次插入时,还将r元素从旧表移动到新表.从旧表中删除所有元素后,取消分配它.
为了确保在新表本身需要放大之前将旧表完全复制,有必要在调整大小期间将表的大小增加至少(r + 1)/ r.
所以这不是将旧表中的所有元素移动到新表中的巧妙方法(如果有的话,我还没有看到它); 相反,它通过允许迁移逐渐发生来减轻调整大小的负担.