Hash（散列）冲突解决 线性探测再散列和二次探测再散列
2019-07-03 本文已影响0人
魏鹏飞
线性探测再散列
例如 哈希函数为： H（key） = key %11,key 为关键字，采用开放地址法中的线性探测再散列解决冲突，依次输入
9 个关键字，19，01，23，14，55，68，11，82，36，构造哈希表（表长=11）
| 散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 55 | 01 | 23 | 14 | 68 | 11 | 82 | 36 | 19 | ||
| 探测次数 | 1 | 1 | 2 | 1 | 3 | 6 | 2 | 5 | 1 |
如上表，例如 14%11=3，将14放入3号位置，11%11 = 0，将11放入0号位置，而此时3号位已经有元素。
就顺着表往后放，直到5号没有元素，11放入5号。
二次探测再散列
例如 哈希函数为： H（key） = key %11,key 为关键字，采用开放地址法中的二次探测再散列解决冲突，依次输入
9 个关键字，19，01，23，14，55，68，11，82，36，构造哈希表（表长=11）
| 散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 55 | 01 | 23 | 14 | 36 | 82 | 68 | 19 | 11 | ||
| 探测次数 | 1 | 1 | 2 | 1 | 2 | 1 | 4 | 1 | 3 |
对于01%11=1，将01放入1号位置， 11%11=0，此时0号位置已经有元素，
则查找 0 + 1^2 = 1,有元素
查找 0 - 1^2 = -1 ,没有则放入，如果还有元素则查找0 + 2^2, 0-2^2.... 0+k^2, 0 - k^2。
