线性探测再散列
例如 哈希函数为: 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。