假设一个数组中表示位置key={0,1,2,3,4,5,6,...},对应存储的哈希函数为hash(key)==H,key的个数为m
开放定址法:(H+di)%m
1,线性探测再散列:(H+i) % m;i=0,1,2,...,m-1,即di为1,2,3,4,5,6,......
2,平方探测再散列:(H+pow(-1,r)*(i-r)/2)%m,r=i%2;即key,key+1*1,key-1*1,key+2*2,key-2*2,...直到结果对应的数组有空间.di为1,-1,4,-4,9,-9,16,-16... --------之所以用平方,是为了避免键值对的聚集成群。通俗的说就是产生冲突的键值对在表的一团成群出现。 使用二次探查法可以有效减少冲突出现的次数。
3,伪随机探测再散列:di为伪随机数
链地址法:将所有哈希地址相同的记录都链接在同一链表里.
每个存储哈希值的空间,实际上存储了一个链表的节点,有hash相同的值存入时,就将这个新值作为一个节点写在链表中.