哈希冲突，如何解决哈希冲突？

哈希冲突的产生原因

由于哈希函数产生的哈希值是有限的，而数据可能比较多，导致通过哈希函数处理的数据仍对应的相同的值，这就产生了哈希冲突。

哈希冲突解决方法

1.开放定址法

线性探测、再平方探测、伪随机探测。

线性探测：按顺序决定值时，如果某个数据已经存在，则在原来值的基础上往后再加一个单位。

再平方探测：按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。

伪随机探测：按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。

2.链式地址法

这种方法的基本思想是将所有哈希地址相同的元素构成一个称为同义词链的单链表。

3.再哈希法

对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。

4.建立公共溢出区法

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。