哈希函数处理冲突的方法

​ hash存在天然的问题，哈希冲突，又叫哈希碰撞。
开放定址法
​ 也叫再散列法，其基本思想是：当关键字 key 的哈希地址 p=H(key)出现冲突时，以 p 为基础，产生另一个哈希地址 p1 ，如果 p1 仍然冲突，再以 p 为基础，产生另一个哈希地址 p2 ，…，直到找出一个不冲突的哈希地址 pi ，将相应元素存入其中。
​ 这种方法有一个通用的再散列函数形式： Hi=(H(key) + di) % m i=1，2，…，n(n <= m-1) 其中 H(key)为哈希函数，m 为表长，di 称为增量序列。 ​ 增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种： ​ 1、线性探测法，di=1，2，3，…，m-1，简单地说，就是以当前冲突位置为起点，步长为 1 循环查找，直到找到一个空的位置，如果循环完了都没找到，证明容器已经满了； ​ 2、平方探测法，di=±1²，±2²，…，±k

哈希函数处理冲突的方法最先出现在Python成神之路。