线性探测再散列
例如 哈希函数为: H(key) = key %13,key 为关键字,采用开放地址法中的线性探测再散列解决冲突,依次输入
11 个关键字,16,74,60,43,54,90,46,31,29,88,77,构造哈希表
如图,例如 16%13=3,将16放入3号位置,29%13 = 3,将29放入3号位置,而此时3号位已经有元素。
就顺着表往后放,直到6号没有元素,29放入6号。
二次探测再散列
例如 哈希函数为: H(key) = key %13,key 为关键字,采用开放地址法中的二次探测再散列解决冲突,依次输入
10 个关键字,36,21,45,17,29,55,35,61,40,78,构造哈希表
对于29%13=3,将29放入3号位置, 55%13=3,此时3号位置已经有元素,
则查找 3 + 1^2 = 4,有元素
查找 3 - 1^2 = 2 ,没有则放入,如果还有元素则查找3 + 2^2, 3-2^2.... 3+k^2, 3 - k^2。