HashMap 底层是怎么样的

JDK1.8 之前

JDK1.8 前，HashMap 底层是 数组+链表，也就是 链表散列。 HashMap 通过 key 先计算 hashCode，再经过 扰动函数 处理后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（n 指的是数组长度）；如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同；如果相同，直接覆盖；如果不同，就通过 拉链法 解决冲突。

扰动函数：指的是 HashMap 的 hash 方法，扰动函数是为了减少碰撞，防止一些实现比较差的 hashCode() 方法

JDK1.8 的 hash() 方法 相比于 JDK1.7 hash() 方法更加简化，但是原理不变。

JDK1.8 HashMap 的 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.7 的 hash() 方法性能会稍差些，毕竟扰动动作做了 4 次。

拉链法： 是将链表与数组相结合，也就是创建一个链表数组，数组的每一格就是一个链表，若遇到哈希冲突，则将冲突的值加到链表中。

链表数组

JDK1.8 之后

相比于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，链表将转化为红黑树，以减少搜索时间。

JDK1.8 之后的 HashMap 底层数据结构

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树，就是为了解决二叉查找树的在某些情况下，会退化成线性结构的缺陷。推荐阅读： 《Java 8系列之重新认识HashMap》