冰冻非一日之寒
哈希冲突是不可避免的，所以我们在设计哈希函数的同时，也要设计解决哈希冲突的办法。
哈希表本质就是一个数组。
通过上一篇知识求出关键字所对应的索引，存储到数组中即可。素数M也是数组的长度
哈希表&数组
通过哈希函数求得的哈希值可能会是一个负数，对哈希值求绝对值即可。有时我们也会见到以下表达式
关键字&索引
哈希值按位与上一个16进制数。
原理：这个16进制数转化为2进制就是一个0，三十一个1。计算机中对整型的表示，第一个数字表示符号位(0代表整数，1代表负数)
将一个整数与之按位与后，第一位肯定是0(代表整数)，后面是整数原来的数字。即最后只是改变了整数的符号位，并将这个整数变成正整数
求绝对值
这样，就得到了一个正整数。
当两个不同的关键字求得的索引相同时，该如何存储呢？
哈希表—链地址法
开辟一个数组，有M个空间，在每一个空间中存储一个链表，这个链表实际上就是一个查找表，可以存储多个数据
哈希表—链地址法
查找表可以使用一个平衡树(红黑树)结构。
TM的底层实现是红黑树
这样，数组中的每一个空间就有一个TreeMap数组(红黑树)了。
在Java8之前，数组中每一个空间对应的就是一个链表
Java8，当哈希冲突达到一定程度后，每一个空间从链表转成红黑树
JAVA
在Java8中，为什么要有这一步的转化操作呢？
因为，当我们的数据规模比较小的时候，也就是哈希冲突比较小，使用链表可以更快的进行增删改查等操作。而使用红黑树的话，还要进行旋转操作，这反而让操作更复杂。
以上就是解决哈希冲突最常用的链地址法
网友评论