1、12345678910所得存储位置称为所得存储位置称为哈希地址哈希地址(又称又称散列地址散列地址)。111213141516标识符的八进制内码表示及其平方值标识符的八进制内码表示及其平方值17181920212223例例假设哈希表长度假设哈希表长度m=13,采用除留余数法哈希函数建立如下采用除留余数法哈希函数建立如下关键字集合的哈希表：关键字集合的哈希表：16,74,60,43,54,90,46,31,29,88,77。解：解：n=11,m=13,除留余数法的哈希函数为除留余数法的哈希函数为f(k)=k mod p,p应为小于等于应为小于等于m的素数的素数,假设假设p取值取值13。则有：。则有
2、：f(16)=3,f(74)=9,f(60)=8,f(43)=4,f(54)=2,f(90)=12,f(46)=7,f(31)=5,f(29)=3,f(88)=10,f(77)=12。注意：存在冲突。注意：存在冲突。2425262728293031012345678910Hashing 表表1760293838H(17)=6H(60)=5H(29)=7 H(38)=5012345678910Hashing 表表012345678910Hashing 表表1760293838H(17)=6H(60)=5H(29)=7 H(38)=5323334例例1假设哈希表长度假设哈希表长度m=13,采用除留
3、余数法哈希函数建立如下采用除留余数法哈希函数建立如下关键字集合的哈希表：关键字集合的哈希表：16,74,60,43,54,90,46,31,29,88,77。35对构造的哈希表采用线性探查法解决冲突。对构造的哈希表采用线性探查法解决冲突。解：解：h(16)=3,h(74)=9,h(60)=8,h(43)=4,h(54)=2,h(90)=12,h(46)=7,h(31)=5,h(29)=3 冲突冲突 d0=3,d1=(3+1)mod 13=4 仍冲突仍冲突 d2=(4+1)mod 13=5 仍冲突仍冲突 d3=(5+1)mod 13=6 h(88)=10 h(77)=12 冲突冲突 d0=12,
4、d1=(12+1)mod 13=036哈希表哈希表ha0.12建立的哈希表建立的哈希表ha0.12如下表所示。如下表所示。373822 67 41 30 53 46 13 0122 67 41 30 22 67 41 30 53 46 13 0153 46 13 01(1)(3)(1)(2)(1)(1)(2)(6)0 1 2 3 4 5 6 78 9 101 8 2 5 3 4 6 722 67 41 30 53 46 13 0122 67 41 30 22 67 41 30 53 46 13 0153 46 13 01(1)(3)(1)(2)(1)(1)(2)(6)0 1 2 3 4 5 6
5、 78 9 101 8 2 5 3 4 6 7390123456789K1K2K3K4K5K6同义链，同一散列地址。同义链，同一散列地址。同义链，同一散列地址。同义链，同一散列地址。0123456789K1K2K3K4K5K6同义链，同一散列地址。同义链，同一散列地址。同义链，同一散列地址。同义链，同一散列地址。40例例.对例对例1构造的哈希表采用拉链法解决冲突。构造的哈希表采用拉链法解决冲突。解：采用拉链法解决冲突建立的链表如下图所示。解：采用拉链法解决冲突建立的链表如下图所示。0 1 2 3 4 5 6 7 8 9 10 11 12 54 74 88 46 60 31 43 29 16 77 90 下标下标 哈希表哈希表 41012345678910K1K2K3K4K5K2K3K5K6基本区（基本区（M 存区存区）公共溢出区公共溢出区012345678910K1K2K3K4K5K2K3K5K6基本区（基本区（M 存区存区）公共溢出区公共溢出区4243
