在某些时候我们需要增加散列的大小,通常我们只是重新散列,这会导致整个散列的重新构造。
有没有更好的解决方案,当我们增加尺寸时,我们不需要重新构造整个东西?
最佳答案
你可以使用 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 的表应该准备就绪。对于哈希表的特殊情况,可扩展哈希应该更好。
关于algorithm - rehash 时如何提高性能?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7072672/