如何在执行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的表格应已准备就绪。对于哈希表的特殊情况，可扩展的哈希应该更好。

Answer 2

任何时候你重新散列，没有什么说明你需要真正地重新散列。事实上，你真正需要做的就是重新修改(即改变所有东西的位置)。

如果你缓存散列(嘿嘿，听起来像是dr的开头。那么你只需要计算一次。因此，将散列与实际数据一起存储，这将使您不必在将来再次计算散列。然而，我假设您还没有这样做，您并没有确切地解释当前的过程。

// Store these instead of the data directly. This assumes immutable data.
struct hashable_item
{
    data dat;
    int32 hash;
}