燕郊做网站公司,网站建设能赚钱吗,西安手机网站建设,医疗行业网站策划一、引言
开放寻址法是解决散列表中冲突的一种重要方法#xff0c;当发生冲突#xff08;即两个不同的键通过散列函数计算得到相同的散列值#xff09;时#xff0c;它会在散列表中寻找下一个可用的存储位置。而探测序列就是用于确定在发生冲突后#xff0c;依次尝试哪些…一、引言
开放寻址法是解决散列表中冲突的一种重要方法当发生冲突即两个不同的键通过散列函数计算得到相同的散列值时它会在散列表中寻找下一个可用的存储位置。而探测序列就是用于确定在发生冲突后依次尝试哪些存储位置的规则。下面详细介绍线性探测、二次探测和双重散列这三种常见的探测序列。
二、线性探测Linear Probing
1. 原理
线性探测是最简单的开放寻址法探测序列。当插入一个键值对计算出的散列值对应的存储位置已被占用时它会按照顺序依次检查下一个存储位置通常是逐个向后检查直到找到一个空的存储位置为止。如果检查到散列表的末尾还没有找到空位置就会从散列表的开头继续检查。其探测函数的公式为 h ( k , i ) ( h ′ ( k ) i ) m o d m h(k, i) (h(k)i) \bmod m h(k,i)(h′(k)i)modm 其中 h ( k , i ) h(k, i) h(k,i) 是经过 i i i 次探测后得到的存储位置 h ′ ( k ) h(k) h′(k) 是初始的散列值即通过散列函数直接计算得到的位置 i i i 是探测次数 i 0 , 1 , 2 , ⋯ i 0, 1, 2, \cdots i0,1,2,⋯ m m m 是散列表的大小。
2. 示例
假设散列表的大小 m 10 m 10 m10散列函数 h ′ ( k ) k m o d 10 h(k)k \bmod 10 h′(k)kmod10。现在要依次插入键 23 23 23、 33 33 33、 43 43 43。
插入键 23 23 23 h ′ ( 23 ) 23 m o d 10 3 h(23)23 \bmod 10 3 h′(23)23mod103位置 3 3 3 为空直接插入。插入键 33 33 33 h ′ ( 33 ) 33 m o d 10 3 h(33)33 \bmod 10 3 h′(33)33mod103位置 3 3 3 已被占用进行第一次探测 i 1 i 1 i1 h ( 33 , 1 ) ( 3 1 ) m o d 10 4 h(33, 1)(3 1)\bmod 10 4 h(33,1)(31)mod104位置 4 4 4 为空插入到位置 4 4 4。插入键 43 43 43 h ′ ( 43 ) 43 m o d 10 3 h(43)43 \bmod 10 3 h′(43)43mod103位置 3 3 3 已被占用进行第一次探测 i 1 i 1 i1 h ( 43 , 1 ) ( 3 1 ) m o d 10 4 h(43, 1)(3 1)\bmod 10 4 h(43,1)(31)mod104位置 4 4 4 也被占用进行第二次探测 i 2 i 2 i2 h ( 43 , 2 ) ( 3 2 ) m o d 10 5 h(43, 2)(3 2)\bmod 10 5 h(43,2)(32)mod105位置 5 5 5 为空插入到位置 5 5 5。
3. 优缺点
优点实现简单只需要进行简单的加法和取模运算。缺点容易产生“聚集”现象即连续被占用的存储位置会越来越长导致后续插入和查找操作的效率降低。
三、二次探测Quadratic Probing
1. 原理
二次探测通过二次函数来确定探测序列它在发生冲突时不是像线性探测那样逐个向后检查而是按照二次方的步长来检查存储位置。其探测函数的公式为 h ( k , i ) ( h ′ ( k ) c 1 i c 2 i 2 ) m o d m h(k, i)(h(k)c_1i c_2i^2) \bmod m h(k,i)(h′(k)c1ic2i2)modm 其中 c 1 c_1 c1 和 c 2 c_2 c2 是正的常数 h ′ ( k ) h(k) h′(k) 是初始散列值 i i i 是探测次数 i 0 , 1 , 2 , ⋯ i 0, 1, 2, \cdots i0,1,2,⋯ m m m 是散列表的大小。常见的情况是 c 1 c 2 1 c_1 c_2 1 c1c21。
2. 示例
同样假设散列表的大小 m 10 m 10 m10散列函数 h ′ ( k ) k m o d 10 h(k)k \bmod 10 h′(k)kmod10 c 1 c 2 1 c_1 c_2 1 c1c21。要插入键 23 23 23、 33 33 33、 43 43 43。
插入键 23 23 23 h ′ ( 23 ) 23 m o d 10 3 h(23)23 \bmod 10 3 h′(23)23mod103位置 3 3 3 为空直接插入。插入键 33 33 33 h ′ ( 33 ) 33 m o d 10 3 h(33)33 \bmod 10 3 h′(33)33mod103位置 3 3 3 已被占用进行第一次探测 i 1 i 1 i1 h ( 33 , 1 ) ( 3 1 × 1 1 × 1 2 ) m o d 10 5 h(33, 1)(31\times1 1\times1^2)\bmod 10 5 h(33,1)(31×11×12)mod105位置 5 5 5 为空插入到位置 5 5 5。插入键 43 43 43 h ′ ( 43 ) 43 m o d 10 3 h(43)43 \bmod 10 3 h′(43)43mod103位置 3 3 3 已被占用进行第一次探测 i 1 i 1 i1 h ( 43 , 1 ) ( 3 1 × 1 1 × 1 2 ) m o d 10 5 h(43, 1)(31\times1 1\times1^2)\bmod 10 5 h(43,1)(31×11×12)mod105位置 5 5 5 也被占用进行第二次探测 i 2 i 2 i2 h ( 43 , 2 ) ( 3 1 × 2 1 × 2 2 ) m o d 10 9 h(43, 2)(31\times2 1\times2^2)\bmod 10 9 h(43,2)(31×21×22)mod109位置 9 9 9 为空插入到位置 9 9 9。
3. 优缺点
优点一定程度上缓解了线性探测的“聚集”问题因为它的探测步长是变化的。缺点仍然可能出现二次聚集的情况即不同的初始散列值可能会产生相同的探测序列。
四、双重散列Double Hashing
1. 原理
双重散列使用两个散列函数来确定探测序列。当发生冲突时它会根据第二个散列函数计算出的步长来依次检查存储位置。其探测函数的公式为 h ( k , i ) ( h 1 ( k ) i × h 2 ( k ) ) m o d m h(k, i)(h_1(k)i\times h_2(k)) \bmod m h(k,i)(h1(k)i×h2(k))modm 其中 h 1 ( k ) h_1(k) h1(k) 是第一个散列函数计算得到的初始散列值 h 2 ( k ) h_2(k) h2(k) 是第二个散列函数 i i i 是探测次数 i 0 , 1 , 2 , ⋯ i 0, 1, 2, \cdots i0,1,2,⋯ m m m 是散列表的大小。为了保证能够遍历散列表中的所有位置 h 2 ( k ) h_2(k) h2(k) 的值必须与 m m m 互质。
2. 示例
假设散列表的大小 m 10 m 10 m10第一个散列函数 h 1 ( k ) k m o d 10 h_1(k)k \bmod 10 h1(k)kmod10第二个散列函数 h 2 ( k ) 7 − ( k m o d 7 ) h_2(k)7-(k \bmod 7) h2(k)7−(kmod7)。要插入键 23 23 23、 33 33 33、 43 43 43。
插入键 23 23 23 h 1 ( 23 ) 23 m o d 10 3 h_1(23)23 \bmod 10 3 h1(23)23mod103位置 3 3 3 为空直接插入。插入键 33 33 33 h 1 ( 33 ) 33 m o d 10 3 h_1(33)33 \bmod 10 3 h1(33)33mod103位置 3 3 3 已被占用 h 2 ( 33 ) 7 − ( 33 m o d 7 ) 7 − 5 2 h_2(33)7-(33 \bmod 7)7 - 5 2 h2(33)7−(33mod7)7−52进行第一次探测 i 1 i 1 i1 h ( 33 , 1 ) ( 3 1 × 2 ) m o d 10 5 h(33, 1)(31\times2)\bmod 10 5 h(33,1)(31×2)mod105位置 5 5 5 为空插入到位置 5 5 5。插入键 43 43 43 h 1 ( 43 ) 43 m o d 10 3 h_1(43)43 \bmod 10 3 h1(43)43mod103位置 3 3 3 已被占用 h 2 ( 43 ) 7 − ( 43 m o d 7 ) 7 − 1 6 h_2(43)7-(43 \bmod 7)7 - 1 6 h2(43)7−(43mod7)7−16进行第一次探测 i 1 i 1 i1 h ( 43 , 1 ) ( 3 1 × 6 ) m o d 10 9 h(43, 1)(31\times6)\bmod 10 9 h(43,1)(31×6)mod109位置 9 9 9 为空插入到位置 9 9 9。
3.优缺点
优点是开放寻址法中最好的方法之一能更均匀地分布键减少聚集现象使插入、查找和删除操作的平均性能更接近理想情况。缺点需要设计两个散列函数实现相对复杂计算开销也会稍微大一些。
