• HashMap(2)正文源码分析

    序、慢慢来才是最快的方法。

    1.简介


    HashMap的底层结构是基于分离链表发解决散列冲突的动态散列表。

    • 在Java7中使用数组+链表，发生散列冲突的键值对会使用头插法添加到单链表中；
    • 在Java8中使用数组+链表+红黑树，发生散列冲突的键值对会用尾插发添加到单链表中。如果单链表的长度大于8时且散列表容量大于64，会将链表树转化为红黑树。在扩容再散列时，如果红黑树的长度低于6则会还原给链表。
    • HashMap的数组长度保证是2的整数次幂，默认数组容量是16，默认装载因子上限是0.75，扩容阈值是12（16*0.75）
    • 在创建HashMap对象时，并不会创建底层数组，这是一种懒初始化机制。直到第一次put操作时才会通过resize()扩容操作初始化数组。
    • HashMap的key和value都支持null，key为null的键值对会映射到数组下表为0的桶中。
       

    2.源码分析

    2.1 HashMap构造函数

    HashMap 有 4 个构造方法：

    • 1、带初始容量和装载因子的构造方法： 检查初始容量和装载因子的有效性，并计算初始容量最近的 2 的整数幂；
    • 2、带初始容量的构造方法： 使用默认负载因子 0.75 调用上一个构造方法；
    • 3、无参构造方法： 设置默认装载因子 0.75；
    • 4、带 Map 参数的构造方法： 设置默认装载因子 0.75，并逐个添加 Map 中的映射关系。
    1. // 带初始容量和装载因子的构造方法 
    2. public HashMap(int initialCapacity, float loadFactor) {
    3.         if (initialCapacity < 0)
    4.             throw new IllegalArgumentException("Illegal initial capacity: " +
    5.                                                initialCapacity);
    6.         if (initialCapacity > MAXIMUM_CAPACITY)
    7.             // 最大容量限制
    8.             initialCapacity = MAXIMUM_CAPACITY;
    9.         if (loadFactor <= 0 || Float.isNaN(loadFactor))
    10.             throw new IllegalArgumentException("Illegal load factor: " +
    11.                                                loadFactor);
    12.         // 装载因子上限
    13.         this.loadFactor = loadFactor;
    14.     // 扩容阈值（此处不是真正的阈值，仅仅只是将传入的容量转化最近的 2 的整数幂，该阈值后面会重新计算）
    15.         this.threshold = tableSizeFor(initialCapacity);
    16.     }
    17.  
    18.    
    19.     // 带初始容量的构造方法
    20.     public HashMap(int initialCapacity) {
    21.         this(initialCapacity, DEFAULT_LOAD_FACTOR);
    22.     }
    23.  
    24.    
    25.     // 无参构造方法
    26.     public HashMap() {
    27.         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    28.     }
    29.     
    30.     //带 Map 的构造方法
    31.     public HashMap(Map m) {
    32.         this.loadFactor = DEFAULT_LOAD_FACTOR;
    33.         putMapEntries(m, false);
    34.     }
    35.  
    36.  
    37. // 获取最近的 2 的整数幂
    38. static final int tableSizeFor(int cap) {
    39.     // 先减 1，让 8、16 这种本身就是 2 的整数幂的容量保持不变
    40.     // 在 ArrayDeque 中没有先减 1，所以容量 8 会转为 16
    41.     int n = cap - 1;
    42.     n |= n >>> 1;
    43.     n |= n >>> 2;
    44.     n |= n >>> 4;
    45.     n |= n >>> 8;
    46.     n |= n >>> 16;
    47.     return (n < 0) ? 1 /*tableSizeFor() 方法外层已经检查过超过 2^30 的值，应该不存在整型溢出的情况*/
    48.         : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    49. }
    50.

    2.2 HashMap 的哈希函数

    将 HashMap#put 方法中，有一个重要的步骤就是使用 Hash 函数计算键值对中键（Key）的散列值。HashMap#put 的执行流程非常复杂，为了降低理解难度，我们先分析 HashMap#hash 方法。

    Hash 函数是散列表的核心特性，Hash 函数是否足够随机，会直接影响散列表的查询性能。在 Java 7 和 Java 8 中，HashMap 会在 Object#hashCode() 的基础上增加 “扰动”：

    • Java 7： 做 4 次扰动，通过无符号右移，让散列值的高位与低位做异或；
    • Java 8： 做 1 次扰动，通过无符号右移，让高 16 位与低 16 位做异或。在 Java 8 只做一次扰动，是为了在随机性和计算效率之间的权衡。
    1. public V put(K key, V value) {
    2.     return putVal(hash(key) /*计算散列值*/, key, value, false, true);
    3. }
    4.  
    5. // Java 7：4 次位运算 + 5次异或运算
    6. static final int hash(int h) {
    7.     h ^= k.hashCode(); 
    8.     h ^= (h >>> 20) ^ (h >>> 12);
    9.     return h ^ (h >>> 7) ^ (h >>> 4);
    10.  }
    11.  
    12. // 疑问 9：为什么 HashMap 要在 Object#hashCode() 上增加扰动，而不是要求 Object#hashCode() 尽可能随机？
    13. // 为什么让高位与低位做异或就可以提高随机性？
    14. // Java 8：1 次位运算 + 1次异或运算
    15. static final int hash(Object key) {
    16.     int h;
    17.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    18. }

    PS：为什么 HashMap 要在 Object#hashCode() 上增加扰动，而不是要求 Object#hashCode() 尽可能随机？

    这是兜下限，以保证所有使用 HashMap 的开发者都能获得良好的性能。而且，由于数组的长度有限，在将散列值映射到数组下标时，会使用数组的长度做取余运算，最终影响下标位置的只有散列值的低几位元素，会破坏映射的随机性（即散列值随机，但映射到下标后不随机）。

    因此，HashMap 会对散列值做位移和异或运算，让高 16 位与低 16 位做异或运算。等于说在低位中加入了高位的特性，让高位的数值也会影响到数组下标的计算。

    2.3 HashMap 的添加方法

    HashMap 直接添加一个键值对，也支持批量添加键值对：

    • put： 逐个添加或更新键值对
    • putAll： 批量添加或更新键值对

    不管是逐个添加还是批量添加，最终都会先通过 hash 函数计算键（Key）的散列值，再通过 putVal 添加或更新键值对。

    putValue 的流程非常复杂，我将主要步骤概括为 5 步：

    • 1、如果数组为空，则使用扩容函数创建（说明数组的创建时机在首次 put 操作时）；
    • 2、(n - 1) & hash：散列值转数组下标，与 Java 7 的 indexFor() 方法相似；
    • 3、如果是桶中的第一个节点，则创建并插入 Node 节点；
    • 4、如果不是桶中的第一个节点（即发生哈希冲突），需要插入链表或红黑树。在添加到链表的过程中，遍历链表找到 Key 相等（equals）的节点，如果不存在则使用尾插法添加新节点。如果链表节点数超过树化阈值 8，则将链表转为红黑树。
    • 5、如果键值对数量大于扩容阈值，则触发扩容。

    HashMap#put

    1. // 添加或更新键值对
    2. public V put(K key, V value) {
    3.     return putVal(hash(key) /*计算散列值*/, key, value, false, true);
    4. }
    5.  
    6. // 批量添加或更新键值对
    7. public void putAll(Map m) {
    8.     putMapEntries(m, true);
    9. }
    10.  
    11. // 批量添加或更新键值对
    12. // evict：是否驱逐最早的节点（在 LinkedHashMap 中使用，我们先忽略）
    13. final void putMapEntries(Map m, boolean evict) {
    14.     int s = m.size();
    15.     if (s > 0) {
    16.         if (table == null) {
    17.             // 如果数组为空，则先初始化 threshold 扩容阈值
    18.             float ft = ((float)s / loadFactor) + 1.0F;
    19.             // 扩容阈值上限
    20.             int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
    21.             if (t > threshold)
    22.                 threshold = tableSizeFor(t);
    23.         } else if (s > threshold)
    24.             // 参数 Map 的长度大于扩容阈值，先扩容（如果扩容后依然不足，在下面的 putVal 中会再次扩容）
    25.             // 这里应该有优化空间，批量添加时可以直接扩容到满足要求的容量，避免在 for 循环中多次扩容
    26.             resize();
    27.         // 逐个添加 Map 中的键值对
    28.         for (Map.Entryextends K, ? extends V> e : m.entrySet()) {
    29.             K key = e.getKey();
    30.             V value = e.getValue();
    31.             // hash(key)：计算 Key 的哈希值
    32.             // pubVal：添加或更新键值对
    33.             putVal(hash(key), key, value, false, evict);
    34.         }
    35.     }
    36. }
    37.  
    38. // 最终都会走到 putVal方法：
    39.  
    40. // hash：Key 的散列值（经过扰动）
    41. // onlyIfAbsent：如果为 true，不会覆盖旧值
    42. // evict：是否驱逐最早的节点（在 LinkedHashMap 中使用，我们先忽略）
    43. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    44.     // 数组
    45.     Node[] tab; 
    46.     // 目标桶（同一个桶中节点的散列值有可能不同）
    47.     Node p; 
    48.     // 数组长度
    49.     int n;
    50.     // 桶的位置
    51.     int i;
    52.     // 1. 如果数组为空，则使用扩容函数创建（说明数组的创建时机在首次 put 操作时）
    53.     if ((tab = table) == null || (n = tab.length) == 0)
    54.         n = (tab = resize()).length;
    55.     // 2. (n - 1) & hash：散列值转数组下标，与 Java 7 的 indexFor() 方法相似
    56.     if ((p = tab[i = (n - 1) & hash]) == null)
    57.         // 3. 如果是桶中的第一个节点，则创建并插入 Node 节点
    58.         tab[i] = newNode(hash, key, value, null);
    59.     else {
    60.         // 4. 如果不是桶中的第一个节点（即发生哈希冲突），需要插入链表或红黑树
    61.         // e：最终匹配的节点
    62.         Node e; 
    63.         // 节点上的 Key
    64.         K k;
    65.         if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
    66.             // 4.1 如果桶的根节点与 Key 相等，则将匹配到根节点
    67.             // p.hash == hash：快捷比较（同一个桶中节点的散列值有可能不同，如果散列值不同，键不可能相同）
    68.             // (k = p.key) == key：快捷比较（同一个对象）
    69.             // key != null && key.equals(k)：判断两个对象 equals 相同
    70.             e = p;
    71.         else if (p instanceof TreeNode)
    72.         // 4.2 如果桶是红黑树结构，则采用红黑树的插入方式
    73.             e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
    74.         else {
    75.             // 4.3 如果桶是链表结构，则采用链表的插入方式：
    76.             // 4.3.1 遍历链表找到 Key 相等的节点
    77.             // 4.3.2 否则使用尾插法添加新节点
    78.             // 4.3.3 链表节点数超过树化阈值，则将链表转为红黑树
    79.             for (int binCount = 0; ; ++binCount) {
    80.                 // 尾插法（Java 7 使用头插法）
    81.                 if ((e = p.next) == null) {
    82.                     p.next = newNode(hash, key, value, null);
    83.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    84.                         // 链表节点数超过树化阈值，则将链表转为红黑树
    85.                         treeifyBin(tab, hash);
    86.                     break;
    87.                 }
    88.                 // 找到 Key 相等的节点
    89.                 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
    90.                     break;
    91.                 p = e;
    92.             }
    93.         }
    94.         // 4.4 新 Value 替换旧 Value（新增节点时不会走到这个分支）
    95.         if (e != null) {
    96.             V oldValue = e.value;
    97.             if (!onlyIfAbsent || oldValue == null)
    98.                 e.value = value;
    99.             // 访问节点回（用于 LinkedHashMap，默认为空实现）
    100.             afterNodeAccess(e);
    101.             return oldValue;
    102.         }
    103.     }
    104.     // 修改记录
    105.     ++modCount;
    106.     // 5. 如果键值对数量大于扩容阈值，则触发扩容
    107.     if (++size > threshold)
    108.         resize();
    109.     // 新增节点回调（用于 LinkedHashMap，默认为空实现）
    110.     afterNodeInsertion(evict);
    111.     return null;
    112. }
    113.  
    114. // -> 4.2 如果桶是红黑树结构，则采用红黑树的插入方式
    115. final TreeNode putTreeVal(HashMap map, Node[] tab,
    116.                                        int h, K k, V v) {
    117.     ...
    118. }
    119.  
    120. // -> 链表节点数超过树化阈值，则将链表转为红黑树
    121. final void treeifyBin(Node[] tab, int hash) {
    122.     int n, index; Node e;
    123.     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    124.         resize();
    125.     else if ((e = tab[index = (n - 1) & hash]) != null) {
    126.         TreeNode hd = null, tl = null;
    127.         do {
    128.             TreeNode p = replacementTreeNode(e, null);
    129.             if (tl == null)
    130.                 hd = p;
    131.             else {
    132.                 p.prev = tl;
    133.                 tl.next = p;
    134.             }
    135.             tl = p;
    136.         } while ((e = e.next) != null);
    137.         if ((tab[index] = hd) != null)
    138.             hd.treeify(tab);
    139.     }
    140. }
    141.

    2.4 HashMap 的扩容方法

    在 putVal 方法中，如果添加键值对后散列值的长度超过扩容阈值，就会调用 resize() 扩容，主体流程分为 3步：

    • 1、计算扩容后的新容量和新扩容阈值；
    • 2、创建新数组；
    • 3、将旧数组上的键值对再散列到新数组上。

    扩容分为 2 种情况：

    • 1、首次添加元素： 会根据构造方法中设置的初始容量和装载因子确定新数组的容量和扩容阈值在无参构造方法中，会使用 16 的数组容量和 0.75 的扩容阈值；
    • 2、非首次添加： 将底层数组和扩容阈值扩大为原来的 2 倍，如果旧容量大于等于 2^30 次幂，则无法扩容。此时，将扩容阈值调整到整数最大值。
    1. // 扩容
    2. final Node[] resize() {
    3.     // 旧数组
    4.     Node[] oldTab = table;
    5.     // 旧容量
    6.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
    7.     // 旧扩容阈值
    8.     int oldThr = threshold;
    9.     // 新容量
    10.     int newCap = 0;
    11.     // 新扩容阈值
    12.     int newThr = 0;
    13.     // 1. 计算扩容后的新容量和新扩容阈值
    14.     // 旧容量大于 0，说明不是第一次添加元素
    15.     if (oldCap > 0) {
    16.         // 如果旧容量大于等于 2^30 次幂，则无法扩容。此时，将扩容阈值调整到整数最大值
    17.         if (oldCap >= MAXIMUM_CAPACITY) {
    18.             threshold = Integer.MAX_VALUE;
    19.             return oldTab;
    20.         }
    21.         // 数组容量和扩容阈值扩大为原来的 2 倍
    22.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
    23.             newThr = oldThr << 1; // double threshold
    24.     }
    25.     // 旧容量为 0，需要初始化数组
    26.     else if (oldThr > 0)
    27.         // （带初始容量和负载因子的构造方法走这里）
    28.         // 使用构造方法中计算的最近 2 的整数幂作为数组容量
    29.         newCap = oldThr;
    30.     else {
    31.         // （无参构造方法走这里）
    32.         // 使用默认 16 长度作为初始容量
    33.         newCap = DEFAULT_INITIAL_CAPACITY;
    34.         // 使用默认的负载因子乘以容量计算扩容阈值
    35.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    36.     }
    37.     if (newThr == 0) {
    38.         //（带初始容量和负载因子的构造方法走这里）
    39.         // 使用负载因子乘以容量计算扩容阈值
    40.         float ft = (float)newCap * loadFactor;
    41.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    42.     }
    43.     // 最终计算的扩容阈值
    44.     threshold = newThr;
    45.     // 2. 创建新数组
    46.     Node[] newTab = (Node[])new Node[newCap];
    47.     table = newTab;
    48.     // 3. 将旧数组上的键值对再散列到新数组上
    49.     if (oldTab != null) {
    50.         // 遍历旧数组上的每个桶
    51.         for (int j = 0; j < oldCap; ++j) {
    52.             // 桶的根节点
    53.             Node e;
    54.             // 桶的根节点不为 null
    55.             if ((e = oldTab[j]) != null) {
    56.                 oldTab[j] = null;
    57.                 if (e.next == null)
    58.                     // 3.1 桶的根节点，直接再散列
    59.                     newTab[e.hash & (newCap - 1)] = e;
    60.                 else if (e instanceof TreeNode)
    61.                     // 3.2 以红黑树的方式再散列，思路与 3.3 链表的方式相似
    62.                     ((TreeNode)e).split(this, newTab, j, oldCap);
    63.                 else { 
    64.                     // 3.3 以链表的形式再散列
    65.                     Node loHead = null, loTail = null;
    66.                     Node hiHead = null, hiTail = null;
    67.                     Node next;
    68.                     do {
    69.                         next = e.next;
    70.                         // 3.3.1 若散列值新参与映射的位为 0，那么映射到原始位置上
    71.                         if ((e.hash & oldCap) == 0) {
    72.                             if (loTail == null)
    73.                                 loHead = e;
    74.                             else
    75.                                 loTail.next = e;
    76.                             loTail = e;
    77.                         }
    78.                         // 3.3.2 若散列值新参与映射的位为 0，那么映射到原始位置 + 旧数组容量的位置上
    79.                         else {
    80.                             if (hiTail == null)
    81.                                 hiHead = e;
    82.                             else
    83.                                 hiTail.next = e;
    84.                             hiTail = e;
    85.                         }
    86.                     } while ((e = next) != null);
    87.                     if (loTail != null) {
    88.                         loTail.next = null;
    89.                         newTab[j] = loHead;
    90.                     }
    91.                     if (hiTail != null) {
    92.                         hiTail.next = null;
    93.                         newTab[j + oldCap] = hiHead;
    94.                     }
    95.                 }
    96.             }
    97.         }
    98.     }
    99.     return newTab;
    100. }

    2.5 HashMap 的获取方法

    HashMap 的获取方法相对简单，与 put 方法类似：先通过 hash 函数计算散列值，再通过 hash 取余映射到数组下标的桶中，最后遍历桶中的节点，找到与键（Key）相等（equals）的节点。

    1. // 获取 Key 映射的键值对
    2. public V get(Object key) {
    3.     Node e;
    4.     return (e = getNode(hash(key)/*计算散列值*/, key)) == null ? null : e.value;
    5. }
    6.  
    7. // 通过 Key 的散列值和 Key 获取映射的键值对
    8. final Node getNode(int hash, Object key) {
    9.     Node[] tab; Node first, e; int n; K k;
    10.     if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
    11.         // 先检查根节点
    12.         if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
    13.             return first;
    14.         if ((e = first.next) != null) {
    15.             // 以红黑树的方式检索
    16.             if (first instanceof TreeNode)
    17.                 return ((TreeNode)first).getTreeNode(hash, key);
    18.             // 以链表的方式检索
    19.             do {
    20.                 if (e.hash == hash &&
    21.                     ((k = e.key) == key || (key != null && key.equals(k))))
    22.                     return e;
    23.             } while ((e = e.next) != null);
    24.         }
    25.     }
    26.     return null;
    27. }
    28.

    2.6HashMap 的移除方法

    HashMap 的移除方法是添加方法的逆运算，HashMap 没有做动态缩容。

    1. public V remove(Object key) {
    2.     Node e;
    3.     return (e = removeNode(hash(key)/*计算散列值*/, key, null, false, true)) == null ? null : e.value;
    4. }
    5.  
    6. final Node removeNode(int hash, Object key, Object value,
    7.                                boolean matchValue, boolean movable) {
    8.     // 底层数组
    9.     Node[] tab; 
    10.     // 目标桶（同一个桶中节点的散列值有可能不同）
    11.     Node p; 
    12.     int n, index;
    13.     // 定位到散列值对应的数组下标
    14.     if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
    15.         Node node = null, e; K k; V v;
    16.         if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
    17.             // 先检查根节点
    18.             node = p;
    19.         else if ((e = p.next) != null) {
    20.             if (p instanceof TreeNode)
    21.                 // 以红黑树的方式查询节点
    22.                 node = ((TreeNode)p).getTreeNode(hash, key);
    23.             else {
    24.                 // 以链表的方式查询节点
    25.                 do {
    26.                     if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
    27.                         node = e;
    28.                         break;
    29.                     }
    30.                     p = e;
    31.                 } while ((e = e.next) != null);
    32.             }
    33.         }
    34.         // node 不为 null，删除 node 节点
    35.         if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
    36.             if (node instanceof TreeNode)
    37.                 // 以红黑树的方式删除
    38.                 ((TreeNode)node).removeTreeNode(this, tab, movable);
    39.             else if (node == p)
    40.                 // 以链表的方式删除（删除跟节点）
    41.                 tab[index] = node.next;
    42.             else
    43.                 // 以链表的方式删除（删除中间节点）
    44.                 p.next = node.next;
    45.             ++modCount;
    46.             --size;
    47.             // 删除节点回调（用于 LinkedHashMap，默认为空实现）
    48.             afterNodeRemoval(node);
    49.             return node;
    50.         }
    51.     }
    52.     return null;
    53. }
    54.

    参考



    ​​​​​​​​​​​​Java & Android 集合框架 #6 万字 HashMap 详解，基础（优雅）永不过时 —— 源码篇 - 掘金

  • 相关阅读:
    C++ | Leetcode C++题解之第191题位1的个数
    完成学校官网页面制作
    [SWPUCTF 2021 新生赛]
    Java：什么是Quarkus?
    让1个服务开机自启动 有什么方法
    Notepad++插件 Hex-Edit
    java计算机毕业设计基于springboo+vue的医院挂号体检预约系统
    Metaverse Web 3.0 和 DeFi大师班
    探索未来的视觉革命：卷积神经网络的崭新时代（二）
    Another app is currently holding the yum lock； waiting for it to exit...
  • 原文地址：https://blog.csdn.net/qq_37492806/article/details/133773829