哈希值,又称:散列函式(或散列算法,又称哈希函式,英语:Hash Function)是一种从任何一种数据中创建小的数字“指纹”的方法。想要了解哈希值,就需要了解哈希函数的性质。

哈希表的消除哈希冲突——双散列

 哈希表的消除哈希冲突——双散列
以一个例子讲解双散列的应用:
 
如下表,采用的散列函数均是key%(talesize)。
 
当插入49时,与已经插入的89产生哈希冲突,则采用双散列函数来处理这样的哈希冲突,这里双散列函数采用的是。这里采用的是hash2(x)=7-(x mod 7)。带入49计算得到hash2(49)=7-0=7。则从第9个位置开始数7次,到了第6个位置,所以49插入到第6个位置。
 
当插入58时,与已经插入的18产生哈希冲突,带入hash2(58)=7-(58 mod 7)=7-2=5。则从第8个位置开始数5次到达第3个位置。
 
当插入69时,与已经插入的89产生哈希冲突,带入hash2(69)=7-(69 mod 7)=7-6=1。则从第9个位置开始数1次到达第1个位置。
 
假设插入60,与已经插入的69产生哈希冲突,带入hash2(60)=7-(60 mod 7)=7-4=3。则从第1个位置开始数3次到达第3个位置发现已有数据58,冲突,则f(2)=2*3=6,数6次到达第6个位置,与49冲突,则f(3)=3*3=9,数9次到达第9个位置,则与89冲突。则f(4)=4*3=12,12-10=2(减去tablesize),则数两次可以插入到无数据的第2个位置。
 
 
 

哈希世界创造了一个平行世界,只为你们而存在,而你们可以在其中与你们接触。
Copyright © 2022 www.57jianzhi.com 哈希hash论坛 版权所有