hashmap源码解析

原理

hashmap使用红黑树+数组+链表，当两个对象的哈希值有冲突时，会放入链表中，为了提高性能，当链表长度大于阙值且当前数组的长度大于64时，会将该位置的所有数据改为红黑树。如果长度大于8，但数组长度小于64，会进行数组扩容，因为转为红黑树，需要进行左旋、右旋、变色等操作来保持平衡。当然，如果没有冲突，发现已经数组容纳的元素已经达到负载因子*数组容量，则也要进行扩容。
hashmap的加载因子（负载因子）：表示hashmap的系数程度，默认是0.75，当hashmap容纳的元素已经达到数组长处的75%时，表示hashmap太拥挤了，需要扩容。如果知道要放入多少元素，自省设置hashmap容量初始值，为 元素个数/加载因子+1

Hashmap初始化

咱们看这个传参最多的这个

  static final int TREEIFY_THRESHOLD = 8;
 static final int MAXIMUM_CAPACITY = 1 << 30
static final float DEFAULT_LOAD_FACTOR = 0.75f
HashMap(int initialCapacity, float loadFactor){
     if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity); // 将初始容量转为2的幂
}

loadFactor：加载因子，默认0.75f ,
initialCapacity ：初始容量，默认16,最大容量是1<<30 ，为什么是这个数呢？因为int总共4字节，最高位是符号位，如果写成(1<<31)就变成负数了。又有人问，为什么设计成2的幂呢？主要是为了减少hash碰撞。如果又有人问，为什么加载因子是0.75？主要是考虑到空间利用率和减少查询成本。
TREEIFY_THRESHOLD:当链表的长度大于等于TREEIFY_THRESHOLD的时候，会转为红黑树。

图片编辑自https://www.sohu.com/a/382360719_505818

put()方法

put方法调用了putval(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict),直接看putval方法

  Node<K,V>[] tab; Node<K,V> p; int n, i;
  if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

1. 先看Node类，实现了Map.Entry<K,V>的getValue、setKey等方法，有一个next变量，Node是一个节点，可以结合图理解。
2. if tab是null或空数组，调用resize()方法，首先看一下这个方法的注释，我来不标准的翻译一下: 初始化或双倍扩容table长度。若为null，则根据初始容量值来分配,否则，因为我们用的2的幂，对于每一个节点必须是相同的下标或在新的table中移动2的幂的距离。这时候数组tab的长度就确定了。
   继续下一句

    if ((p = tab[i = (n - 1) & hash]) == null){
 // (n - 1) & hash相当于使用hash % n（hash后按位与 n-1，比%模运算取余要快）计算在数组中的位置下标, 得到该tab[i]赋值给p。
      tab[i] = newNode(hash, key, value, null); //如果p为null，说明tab[i]还没有任何内容，将要put的数据插入数组中
   }else{ // 如果tab[i]已有数据，也就是说计算的数组位置下标冲突了，需要进入链表或者红黑树中
       Node<K,V> e; K k;
       if(tab[i]的key==要put的数据的key){  
              e = p; //将当前数据赋值给变量e保存起来
       }if (p instanceof TreeNode){ //  如果tab[i]是红黑树的一个节点
           e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 将值put进红黑树中  
       } else {
          // 如果链表中已有该key，将当前位置的数据赋值给e，否则将值插入到链表末尾，如果插入后，链表长度大于等于8且数组长度大于64，会将tab[i]节点的这个链表转为红黑树，如果数组长度小于64，会进行扩容。
          
       }
      if(e!=null){ // 如果计算的位置已经有值
         V oldValue = e.value;
          if (!onlyIfAbsent || oldValue == null){
              e.value = value; //将该位置的value更新为put的value
          }
         return oldValue;  // 返回之前的值
      }
    }
    ++modCount; // 修改次数+1
    if (++size > threshold) // 如果存入这个节点容量大于capacity * load factor，则进行扩容
       resize();
  return null;  // 因为计算的位置之前没有值，所以返回null

这里注意，put方法返回值是前一个值，也就是被重写之前的值。
key判断相等的代码我们放在这里是因为这个点也很重要，先看判断逻辑，

(p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))

可以看到，会首先判断hash值，只有hash一样，才会认为这可能是同一个key，才会继续去判断。因此这里我们可以解释一个问题，为什么重写equals就要重写hashcode。所以hashmap的key判断就是内存地址一样或者hash值一样并且内容相同就可以了。

后记

1. 什么是红黑树？
   红黑树性质：每个节点不是红色就是黑色，不可能有连在一起的两个红色节点，根节点是黑色，每个红色节点的两个子节点都是黑色
2. 为什么要求是2的N次幂？为什么加载因子是0.75？
   2的幂是为了减少hash冲突，0.75是因为大于0.75，加载因子过高，例如为1，虽然减少了空间开销，提高了空间利用率，但同时也增加了查询时间成本；
   加载因子过低，例如0.5，虽然可以减少查询时间成本，但是空间利用率很低，同时提高了rehash操作的次数
   https://www.cnblogs.com/aotemanzhifu/p/9192373.html
   https://www.cnblogs.com/aspirant/p/11470928.html
   3.为什么扩容是2倍？
   保证容量是2的n次幂，可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞，避免形成链表的结构，使得查询效率降低
   为什么hashMap的容量是2的幂次

4.为什么要阙值大于8且数组长度大于64才转为红黑树?
因为转化红黑树需要经过旋转、变色等操作

5. putTreeVal()详解
   https://blog.csdn.net/weixin_42340670/article/details/80635008
6. concurrentHashmap怎么实现线程安全的？
7. 为什么要变成红黑树？红黑树和链表查找的时间复杂度是多少？