B树和B树B树一B树的基本概念定义一棵m.ppt

9.4 哈希查找表 若干术语 冲突现象举例： 在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。 二、哈希函数的构造方法 1、直接定址法 2、除留余数法 三、冲突处理方法 1、开放定址法（开地址法） 讨论： 2. 二次探测法 2、链地址法(拉链法） 3、再哈希法（双哈希函数法） 四、哈希表的查找及分析 讨论： Hash(key) = a·key + b (a、b为常数) 优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突. 缺点：要占用连续地址空间，空间效率低。 例：关键码集合为{100，300，500，700，800，900}， 选取哈希函数为Hash(key)=key/100， 则存储结构（哈希表）如下： 0 1 2 3 4 5 6 7 8 9 900 800 700 500 300 100 Hash(key)=key mod p (p是一个整数) 特点：以关键码除以p的余数作为哈希地址。 关键：如何选取合适的p？ 技巧：若设计的哈希表长为m，则一般取p≤m且为质数 （也可以是不包含小于20质因子的合数）。 常见的冲突处理方法有： 开放定址法（开地址法） 链地址法（拉链法） 再哈希法（双哈希函数法） 建立一个公共溢出区 设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。 具体实现： Hi=(Hash(key)+di) mod m ( 1≤i m ) 其中： Hash(key)为哈希函数 m为哈希表长度 di 为增量序列 1，2，…m-1，且di=i 1.线性探测法 含义：一旦冲突，就找附近（下一个）空地址存入。 例：关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表如下： 内容 10 9 8 7 6 5 4 3 2 1 0 地址 例：关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表如下： 47 内容 10 9 8 7 6 5 4 3 2 1 0 地址 47 mod 11=3 例：关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表如下： 7 47 内容 10 9 8 7 6 5 4 3 2 1 0 地址 7 mod 11=7 例：关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表如下： 7 47 内容 10 9 8 7 6 5 4 3 2 1 0 地址 29 mod 11=7 29 冲突，后移1 例：关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表如下： 29 7 47 内容 10 9 8 7 6 5 4 3 2 1 0 地址 29 mod 11=7 例：关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表如下： 29 7 47 11 内容 10 9 8 7 6 5 4 3 2 1 0 地址 11 mod 11=0 例：关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表如下： 29 7 16 47 11 内容 10 9 8 7 6 5 4 3 2 1 0 地址 16 mod 11=5 例：关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表如下： 29 7 16 92 4