哈希表:为什么桶？

Question

据我所知,哈希函数的关键是尽可能均匀地分配数据,当你遇到碰撞时,你有几个选择:

1. 寻找下一个空位
2. 生成不同的哈希并尝试将其粘贴到其他位置
3. 把它放在溢出容器中(可以是列表,另一个哈希表或其他)
4. 把它放在下一个免费桶槽中

最后一个困扰我,因为,如果你要为每个地址制作一个说2个槽的哈希表,为什么不只是制作两倍大的哈希表呢？这是除非动态分配存储桶.在我的情况下,表的数据位于磁盘上,这意味着另一个磁盘访问+管理可变长度数据.在我看来,虽然水桶仍然是最受青睐的选择,为什么呢？我错过了什么？

Answer 1

从这个问题的评论中的讨论可能很明显,有很多不同的方法可以实现哈希表.每个人都有自己的权衡.

您的问题是为什么您需要使用分段系统(封闭寻址或带链接的散列)而不是将对象放入下一个空闲时隙(线性探测).你指出存储在外部存储器中的存储桶需要在内存中的另一个位置进行查找,如果你将存储在磁盘上,这不是一个好主意.这些都是有效的问题.但是,请记住以下几点.

首先,如果您正在使用分段系统(每个哈希表槽都是一个桶,并且所有具有相同哈希码的对象都被抛入同一个桶中),那么与使用开放寻址的线性探测等系统相比,您有一个优势:只有具有相同哈希码的对象才需要担心的冲突.例如,假设您将三个元素插入到哈希表中,并且它们的哈希码是1,1和2.在封闭寻址(存储桶)中,每当执行1的查找时,您都必须检查两个对象哈希码1,但是如果查找对象2,则根本不需要进行任何冲突解决.另一方面,如果使用线性探测,则在查找三个元素中的任何一个时都可能发生碰撞.假设对象A具有哈希码1,对象B具有哈希码2,对象C也具有哈希码1.以A,C,B的顺序插入对象将给出该表:

[ A ] [ C ] [ B ] [   ] [   ]
  1     2     3

现在,执行C或B的查找将要求您对表进行线性扫描,即使B不与对象A或C发生冲突.根据您的应用程序,这可能是一个真正的问题.

另一方面,如果你使用bucketing,正如你所提到的,你需要做一些外部内存访问,这在主内存中会有些慢(由于引用的位置)和磁盘上的冰.这是一个非常好的论点,解释为什么使用链接进行散列对于磁盘上的哈希表不是一个好主意,而线性探测可能是一个合理的折衷方案.

希望这可以帮助!