先简单了解下哈希函数和哈希冲突的概念。
哈希函数：在元素关键字k和位置p之间建立一种映射关系f，使得f(k) = p;创建哈希表时，通过哈希函数将元素k存在地址为f(k)的位置；查找元素也是通过哈希函数找到元素的存放位置，然后取出值；
哈希冲突：关键字的集合很多的时候，就有可能将两个关键字k1,k2的哈希函数计算结果相等，k1和k2的值肯定不能存放在同一个位置，就产生了哈希冲突；哈希冲突是不可避免的，只能尽量减少哈希冲突；
冲突的解决办法有三种：
1>开放定址法或者叫再散列法：
基本思想是，当产生哈希冲突时，即关键字key的地址p=hash(key)上已经有值了，那么这是以p为基础，产生另外一个哈希地址p1,如果p1不冲突了，那么就将元素key存在位置p1,如果p1也冲突，就计算hash(p1)=p2，不冲突就存在p2,冲突继续计算；
再散列有几种方式：
1>线性探测再散列：冲突发生时，查看下个位置是否空，然后遍历下去找到个空的地方存放；
2>二次探测再散列：冲突发生时，在表的左右进行跳跃探测，di=12 -12 22 -22….k2 -k2;
3>伪随机探测再散列：di=伪随机序列；
例子：hash表长度11，哈希函数是：
h(key) = key%11;那么h(47)=3,h(26)=4,h(60)=5;下一个关键字69，h(69)=3,与47冲突了
1>线性探测的解决方法：往后遍历找到个空的位置
0 1 2 3 4 5 6 7 8 9 10
47 26 60 69
2>二次探测再散列：下个哈希地址是h1 = (3+12)%11 = 4,冲突，再找下一个哈希地址，(3-12)%11 = 2，就放在第二个位置
3>再看看伪随机数的处理办法，假设随机数是：2 5 9 ，下一个哈希地址（3+2）%11 = 5，冲突，再找下一个，（3+5）%11 = 8，就放在8的位置了。
2> 再哈希法：
这种方法是同时构造多个不同的哈希函数：hi = rhi(key) i=1,2…k
当哈希地址rh1(key)冲突时，再计算hi = rh2(key)….直到不再冲突
3>拉链法
hashmap处理冲突的解决方法：将所有冲突的地址放在一个链表中，通过链表链接起来；
例如: 已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表长度为13，哈希函数为：H（key）= key % 13，则存放的位置如图所示
位置 Entry
0
1 –> 40 –> 27 –> 53
2
3 –> 16 –> 42
4
5
6 –> 32 –> 71
7
8
9
10 –> 36 –> 49
11 –> 24
12 –> 64
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/179311.html原文链接：https://javaforall.net
