jdk1.8 HashMap put和resize基本原理

数据结构是:数组+链表+红黑树
1、putVal
    插入值:得到数组下标索引值,
        如果数据下标处为null,则放入该位置,
        如果不为空,判断key是否相等,
            如果相等,则覆盖val,
            如果不等,则判断节点类型是否树节点,
                如果是则放入数节点中,
                如果不是,即为链表,循环链表比对key值,
                    如果key相同则覆盖,没有相同的key则插入链表末尾,
        最后取判断是否超过阀值,如果超过则扩容2倍;
    数组下标:
        hash: (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        索引: tab[i = (n - 1) & hash])
2、resize
    创建新数组,将就数组值移动到新数组中;
    容量扩大2倍;
    数据的位置:
        (e.hash & oldCap) == 0 : 在原位置;
        (e.hash & oldCap) != 0: 在原位置+旧容量;

二. 红黑树规则

  1. 节点分为红色或者黑色;
  2. 根节点必为黑色;
  3. 叶子节点都为黑色,且为null;
  4. 连接红色节点的两个子节点都为黑色(红黑树不会出现相邻的红色节点);
  5. 从任意节点出发,到其每个叶子节点的路径中包含相同数量的黑色节点;
  6. 新加入到红黑树的节点为红色节点;

jdk1.8 HashMap put和resize基本原理 

版权声明:玥玥 发表于 2021-03-22 4:52:55。
转载请注明:jdk1.8 HashMap put和resize基本原理 | 女黑客导航