algorithm - rehash 时如何提高性能？

Question

在某些时候我们需要增加散列的大小，通常我们只是重新散列，这会导致整个散列的重新构造。

有没有更好的解决方案，当我们增加尺寸时，我们不需要重新构造整个东西？

Answer 1

你可以使用 http://en.wikipedia.org/wiki/Extendible_hashing ，尽管据我所知，它主要用于磁盘上的数据库。

还有一些通用方法可以平滑一些摊销成本。起点是 http://en.wikipedia.org/wiki/Static_and_dynamic_data_structures和 http://en.wikipedia.org/wiki/Dynamization .将其应用于哈希表的一种应用是始终保留两个表，一个大小为 N，另一个大小为 2N 左右。当较小的溢出时，开始创建一个大小为 4N 的表，但不要立即填充它 - 在使用大小为 2N 的表时逐渐填充它。当大小为 2N 的表已满时，大小为 4N 的表应该准备就绪。对于哈希表的特殊情况，可扩展哈希应该更好。