HashMap底层实现原理

1. java1.7 以前HashMap底层由数组+链表形式实现。
   1.1 插入数据时首先计算数据key的hash值，根据hash找到对应的数组槽位。
   1.2 找到槽位后，判断当前数组槽位是否为null，null则直接作为链表表头插入，否则判断当前需要插入的key是否已经在当前槽位的链表中存在，存在则直接替换新值，不存在则插入到头结点。

// hash值计算
static final int hash(Object key){
  int h;
  // h = key.hashCode() 取hashCode值
  // h ^ (h >>> 16) 高位运算
  return key == null ? 0 : (h = key.haskCode()) ^ (h >>> 16);
}

  // 计算槽位
  (n-1) & hash

2. java1.8 引入和红黑树，底层由数组+链表+红黑树实现。
   2.1 java1.8中插入元素时，会判断当前槽位对应的链表长度，如果长度大于等于8，会将链表转换为红黑树。当红黑树节点<=6 则会重新转换为链表。
   2.2 java1.8 在链表插入元素时，采用的尾部插入法，即将新节点插入到链表尾部。
   2.3 为什么引入红黑树：jdk1.8以前由于链表的查询效率非常低，当hash冲突严重时，链表过长，严重影响查询性能。散列列表最理想的查询效率为O(1)，但是链表过长时，会导致查询退化为O(n)。为了解决这个问题所以jdk8中的HashMap添加了红黑树来解决这个问题，当链表长度>=8的时候链表就会变成红黑树，红黑树其实就是一颗特殊的二叉排序树，平均时间复杂度为O(log2(n))。