hash表如何解决哈希冲突

    哈希表也叫做散列表，是根据关键码值而直接进行访问的的数据结构，也就是说，他通过把关键码值映射到表中一个位置来访问相应的数据，以加快查找的速度。
    这个映射函数就叫做散列函数，存放数据的数组叫做散列表。

        **hash冲突，就是：**根据key即经过一个哈希函数计算以后，得到的结果，作为存放数据的地址，去存放当前的数据，但是却发现这个算出来的地址 已经有 数据 了，这就是所谓的hash冲突。

        开放定址法也称**再散列法**，其基本思想是：当关键字key的哈希地址p出现冲突时，通过**再散列方式去再次产生另一个哈希地址p1**，如果p1仍然冲突，则以p为基础，**再继续去产生另一个哈希地址p2，…**，直到找出一个不冲突的哈希地址pi ，将相应数据存入其中。

再散列的方式主要有以下三种：

    1> 线性探测再散列 
     2> 平方探测再散列    
     3> 随机探测再散列

    **当冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。**

用线性探测再散列处理冲突:
下一个哈希地址为：H1=（3 + 1）% 11 = 4，仍然冲突，
再找下一个哈希地址为：H2=（3 + 2）% 11 = 5，还是冲突，
继续找下一个哈希地址为：H3=（3 + 3）% 11 = 6，此时不再冲突，于是将关键字69的数据填入6号单元。

    **冲突发生时，在表的左右进行跳跃式探测，比较灵活。**
    **跳跃式探测的意思是**：加1的平方，减1的平方，加2的平方，减2的平方，加3的平方，减3的平方…加k的平方，减k的平方。

用平方探测再散列处理冲突：
下一个哈希地址为：H1=（3 + 1^2）% 11 = 4，仍然冲突，
再找下一个哈希地址为：H2=（3 - 1^2）% 11 = 2，此时不再冲突，于是将关键字69的数据填入2号单元。

    **通过建立一个伪随机数发生器，来生成一个伪随机数序列。**

用伪随机探测再散列处理冲突：
且生成的伪随机数序列为：2，5，9，…，
则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，
再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，于是将关键字69的数据填入8号单元。

        链地址法的基本思想是：将**所有哈希地址相同 的元素**都链接在同一个链表中，构成一个单链表。

如图： ( 典型的例子就是：Java的HashMap就是这么实现的。)

        再hash法，就是计算哈希值的哈希函数不止一个两个，这一个哈希函数要是算出来的地址重复了，产生哈希冲突了，**就再用另一个哈希函数去算，一直换，直到哈希冲突不再发生为止**。

        建立一个公共溢出区域，就是溢出表，即，将哈希表分为**基本表和溢出表**两部分，**把和基本表发生冲突的元素，都放在溢出表**。

hash表 如何解决哈希冲突