当与列表链接的单独链接时,为什么我们在哈希表中使用线性探测？

Question

我最近了解了处理哈希表中冲突的不同方法.并且看到链接列表的单独链接总是更节省时间,并且为了节省空间,我们为线性探测分配预定义的内存,稍后我们可能不会使用,对于单独的链接我们动态地利用内存,因此是与链表单独链接不比线性探测更有效吗？如果是的话我们为什么要使用线性探测呢？

Answer 1

我很惊讶您看到链式散列比线性探测更快 - 实际上,线性探测通常比链接快得多.这主要是由于参考的局部性,因为在线性探测中执行的访问往往比在链式散列中执行的访问更接近存储器.

线性探测还有其他成功.例如,插入线性探测哈希表不需要任何新的分配(除非你正在重新划分表),因此在内存稀缺的网络路由器等应用程序中,很高兴知道一旦表设置完成,元素可以放入其中,没有malloc失败的风险.

线性探测的一个缺点是,如果哈希函数选择不当,主群集可能会导致表的性能显着下降.虽然链式散列仍然可能受到错误散列函数的影响,但它对具有附近散列码的元素不太敏感,这些散列码不会对运行时产生负面影响.从理论上讲,如果散列函数是5独立的或者密钥中有足够的熵,则线性探测仅给出预期的O(1)查找.有许多方法可以解决这个问题,因为使用罗宾汉散列技术或跳房子散列,这两种方法都比香草线性探测具有明显更好的最坏情况.

线性探测的另一个缺点是,当负载系数接近1时,其性能会显着下降.您可以通过定期重新定位或使用上述Robin Hood散列技术来解决这个问题.

希望这可以帮助!

Answer 2

当哈希表接近满时,线性探测实际上是更高效的内存.

从历史上看,一个内存非常非常少,因此每个字节都很重要(并且仍然存在一些内存非常有限的情况).

为什么它使用更少的内存？

考虑表格的样子:(根据维基百科的单独链接变体- 还有其他变体,但它们通常使用更多内存)

Linear             Separate chaining #1    Separate chaining #2
probing            List head in table      Pointer in table
|------|           |------|---|            |---|    |------|---|
|Object|           |Object|Ptr|            |Ptr| -> |Object|Ptr|
|------|           |------|---|            |---|    |------|---|
|Object|           |Object|Ptr|            |Ptr| -> |Object|Ptr|
|------|           |------|---|            |---|    |------|---|
| NULL |           | NULL |Ptr|            |Ptr|
|------|           |------|---|            |---|
 .                  .                       .
 .                  .                       .
 .                  .                       .

(Ptr代表"指针" - 任何指向不指向某事物的指针都可以考虑NULL)

单独链接#1明显比线性探测(总是)使用更多内存,因为表中的每个元素都大于指针的大小.

当表中没有多少时,单独的链#2可能有一个优势,但是当它变满时,每个元素大约会有另外两个指针浮动.

templatetypedef可能正确的线性探测通常更快(他很少错),但通常教会说单独的链接更快,你可以在主要的API中看到它(例如Java实现),也许是因为这样,可以避免情况下,当线性探测是多慢(有一些精心选择的值,就可以快速获得O(n)具有线性探测而分离链会一直一直还是性能O(1)),或者一些其他原因.