解决哈希冲突的方法

解决哈希冲突的方法

（1）      开放定址法

         当冲突发生时使用某种探查技术在散列表中形成一个探查序列。沿此序列逐个单元的查找，直到找到给定的关键字，或者碰到一个开放的地址为止。

         线性探测法：挨个向后找。

         线性补偿探测法：将步长从1改为q，要求q与m互质。J=(j+q)%m

         随机探测法：步长改为随机数。

                双重散列法：又称二度哈希，它是以关键字的另一个散列函数值作为增量。

（2）      拉链法

   将所有关键字为同义词的节点链接在同一个单链表中。

    缺点：需要额外的指针空间，当规模较小时，开放定址法节省空间