我一直在尝试进行双重散列,但是我对使用双重散列函数h'时发生的事情感到困惑。
当第一个散列函数发生冲突时,是否会将辅助散列函数的值添加到第一个散列函数的值中?
我已经尝试了很多方法,还没有能够弄清楚这一点,问题是在以下链接的图像:
http://postimg.org/image/k6ko6e0gp/
如何通过双哈希解决这个问题?数组中已经有3个元素,需要插入另外3个元素
双散列是一种解决冲突的方法(将多个键散列到单个索引)。在双散列中,将使用两个散列函数;在冲突的情况下,将使用第二个散列函数来查找表的步长,以查找放置键的空单元格。此链接提供了可能的冲突解决方法的概述。http://www.cs.utexas.edu/users/mitra/csSpring2016/cs313/lectures/hash.html
在您的情况下,在检查附加的图像后,很明显键16会与索引6中的其他键发生冲突,因此,您必须应用第二个散列函数来确定步长。从第一个散列的索引开始,应检查每个(步长)th元素是否有空单元格。一旦找到空单元格,则应将键放在该单元格中。例如,第一个散列索引为0,步长为2,然后应检查索引0、2、4…。请记住,有时,探测需要环绕到表的开头才能找到空单元格。
因此,根据所附图片,键16将获得步长为2的步长。因此,从6开始,步长为2,下一个可用槽位是索引1,它是免费的:)
如果在这种情况下找不到空单元格,则应使用新容量调整哈希表的大小。这被称为重新散列,这通常是一个昂贵的操作,因为它需要重新散列表中的所有元素。应该在表达到一定大小阈值后完成一次。