例3标识符表 序号标识符(key) 1 ABC H(key)=key的第一个字母在 23456 CAD 字母表中的序号 DAT key =ABC CAD DAT FOX YAb ZOO H(key)=13462526 FOX 25 YAB 26200
例3 标识符表 ABC CAD DAT FOX YAB ZOO 1 2 3 4 5 6 25 26 序号 标识符(key) H(key)=key的第一个字母在 字母表中的序号 key =ABC CAD DAT FOX YAB ZOO H(key)=1 3 4 6 25 26
2.除留余数法 设哈希表HT[0..m1]的表长为m,哈希地址为key 除以p所的的余数: H(key)=key MOD p // PASCAL语言 H(key)=key %p //C语言 其中:MOD,%为“取模”或“求余” p<=m,p为接近m的质数(素数),如: 3,5,7,11,13,17,19,23,29,31,37 或不包含小于20的质因子的合数,如: 713(=23*31)
2.除留余数法 设哈希表HT[0..m-1]的表长为m，哈希地址为key 除以p所的的余数： H(key)=key MOD p //PASCAL语言 H(key)=key % p //C语言 其中：MOD,%为“取模”或“求余” p<=m ，p为接近m的质数(素数), 如： 3,5,7,11,13,17,19,23,29,31,37...... 或不包含小于20的质因子的合数，如： 713(=23*31)
例1设m130,取p=127,H(key)=key%127 012 129 例2设m=256取p=251H(key)=key%251 012 255
例1 设 m=130, 取p=127, H(key)=key % 127 0 1 2 ..... 129 例2 设 m=256 取 p=251 H(key)=key % 251 0 1 2 ..... 255
例设哈希表的地址范围为0~20,哈希函数为H(K)=K%19 输入关键字序列:39,22,21,37,36,38,19,解决冲突的 方法为线性探测再散列(哈希),构造哈希表HT[0.20]。 HT[0..20] 关键字KH(K)=K%19 38 3939‰19=1 39 2222%19=3 21 2121‰19=2 22 3737%19=18 345 19 3636‰19=17 3838%19=0 1919%19=0 17 36 19与38冲突,再与39,21 18 37 22冲突,存入HT[4] 19 20
例 设哈希表的地址范围为0～20,哈希函数为H(K)=K % 19 输入关键字序列：39,22,21,37,36,38,19,解决冲突的 方法为线性探测再散列(哈希),构造哈希表HT[0..20]。 38 39 21 22 19 36 37 关键字K H(K)=K%19 39 39%19=1 22 22%19=3 21 21%19=2 37 37%19=18 36 36%19=17 38 38%19=0 19 19%19=0 19与38冲突,再与39,21, 22冲突,存入HT[4] 0 1 2 3 4 5 17 18 19 20 HT[0..20] key