1. JDK1.8 之前
JDK1.8 之前HashMap底层是数组和链表结合在⼀起使⽤也就是链表散列。HashMap通过key的hashCode经过扰动函数处理过后得到hash值，然后通过(n - 1) & hash判断当前元素存放的位置（这⾥的n指的是数组的⻓度），如果当前位置存在元素的话，就判断该元素与要存⼊的元素的hash值以及key是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
所谓扰动函数指的就是HashMap的hash⽅法。使⽤hash⽅法也就是扰动函数是为了防⽌⼀些实现⽐较差的hashCode()⽅法，换句话说使⽤扰动函数之后可以减少碰撞。
JDK 1.8 的 hash ⽅法相⽐于 JDK1.7 hash ⽅法更加简化，但是原理不变。
static final int hash(Object key) {
int h;
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位异或
// >>>:⽆符号右移，忽略符号位，空位都以0补⻬
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}对⽐⼀下 JDK1.7 的HashMap的 hash ⽅法源码：
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}相⽐于 JDK1.8 的 hash ⽅法 ，JDK 1.7 的 hash ⽅法的性能会稍差⼀点点，因为毕竟扰动了 4 次。
所谓“拉链法”就是：将链表和数组相结合。也就是说创建⼀个链表数组，数组中每⼀格就是⼀个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
2. JDK1.8 之后
相⽐于之前的版本，JDK1.8 之后在解决哈希冲突时有了较⼤的变化，当链表⻓度⼤于阈值（默认为 8）（将链表转换成红⿊树前会判断，如果当前数组的⻓度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树）时，将链表转化为红⿊树，以减少搜索时间。
TreeMap、TreeSet以及 JDK1.8 之后的HashMap底层都⽤到了红⿊树。红⿊树就是为了解决⼆叉查找树的缺陷，因为⼆叉查找树在某些情况下会退化成⼀个线性结构。
留言