Java魔法解密：HashMap底层机制大揭秘

文章目录

• • 一、 源码深度解析
  • • 1.1 窥探Java集合框架中的设计思想
    • 1.2 逐行解读HashMap的源代码
    • • 1.2.1 类信息
      • 1.2.2 常量属性
      • 1.2.3 变量属性
      • 1.2.4 节点信息
      • 1.2.5 构造方法
      • 1.2.6 put方法
      • • 1.2.6.1 putVal方法
        • 1.2.6.2 putTreeVal方法
        • 1.2.6.3 tieBreakOrder方法
        • 1.2.6.4 treeifyBin方法
        • 1.2.6.5 treeify方法
        • 1.2.7 get方法
        • 1.2.8 remove方法
        • 1.2.9 resize方法
        • 二、 应用与最佳实践
        • • 2.1 在实际项目中如何合理使用HashMap
          • 2.2 最佳实践和注意事项
          • 三、 结论
          • • 3.1 对HashMap的全面总结
            • 3.2 鼓励读者���入学习和实践

              一、 源码深度解析

              1.1 窥探Java集合框架中的设计思想

              Java集合框架是Java编程中非常重要的一部分，提供了各种数据结构和算法，使得开发者能够高效地组织和操作数据。

              Java集合框架的设计思想主要包括以下几个方面：

              1. 通用性（Generality）：
                 • Java集合框架被设计成通用的、可重用的组件。这样一来，同一套集合框架可以用于存储和处理各种类型的对象。
                 • 可扩展性（Scalability）：
                   • 集合框架提供了一系列接口和类，允许开发者实现自定义的集合类型。这种可扩展性使得开发者能够根据具体的需求创建新的集合类。
                   • 高性能（Performance）：
                     • 集合框架在设计时考虑了性能的因素，通过选择合适的数据结构和算法来提高操作的效率。例如，ArrayList和LinkedList都是List接口的实现，但它们在插入和删除操作上有不同的性能表现。
                     • 互操作性（Interoperability）：
                       • 集合框架中的各个接口和类都被设计成可以互相操作的。这种互操作性使得不同的集合类之间能够轻松地进行转换和使用。
                       • 可读性和简洁性（Readability and Simplicity）：
                         • 集合框架的设计追求代码的可读性和简洁性。通过提供一组清晰的接口和方法，开发者可以更容易地理解和使用集合框架。
                         • 线程安全性（Thread Safety）：
                           • 部分集合类（如Hashtable、Vector）被设计成线程安全的，适用于多线程环境。此外，Java提供了一些在多线程环境中使用时更安全的并发集合类，如ConcurrentHashMap。
                           • Fail-Fast机制（快速失败机制）：
                             • 集合框架在迭代过程中使用了快速失败机制，当多个线程对同一集合进行修改时，可能会抛出ConcurrentModificationException，以提醒开发者在迭代过程中不要修改集合。

              总体来说，Java集合框架的设计思想注重通用性、性能、可扩展性和简洁性，为开发者提供了丰富而强大的工具，用于处理各种不同类型的数据。

              1.2 逐行解读HashMap的源代码

              1.2.1 类信息

              1.2.2 常量属性

              1.2.3 变量属性

              1.2.4 节点信息

              1.2.5 构造方法

              1、构造一个具有默认初始容量（16）和默认加载因子（0.75）的空HashMap。

              2、构造一个带指定初始容量和默认加载因子（0.75）的空HashMap。

              3、构造一个带指定初始容量和加载因子的空HashMap。

              4、构造一个映射关系与指定Map相同的新HashMap。

              5、扩展LRU实现方式与思路。

              在实现一个基于LRU策略的缓存时，通常会使用一个数据结构来存储缓存中的数据，并且需要记录数据的访问顺序。常见的数据结构是双向链表和哈希表的结合。

              基于双向链表和哈希表的实现方式：

              1. 使用双向链表：双向链表可以记录数据的访问顺序，当某个数据被访问时，可以将其移动到链表的头部或尾部。头部表示最近访问的数据，尾部表示最久未被访问的数据。
              2. 使用哈希表：哈希表用于快速查找缓存中的数据，可以将数据的键（key）映射到对应的链表节点，以实现快速的查找和插入操作。

              实现LRU缓存的基本思路如下：

              • 当需要访问缓存中的数据时，首先在哈希表中查找该数据是否存在。
              • 如果存在，则将该数据移动到链表的头部，表示最近被访问过。
              • 如果不存在，需要从后端的存储中加载数据，并插入到链表的头部，同时更新哈希表。
              • 当缓存已满时，需要淘汰链表尾部的数据，同时更新哈希表。

                通过这种方式，实现了一个基于LRU淘汰策略的缓存系统，可以确保最近最少被使用的数据会被及时地淘汰，从而保持缓存中的数据是最有用的。

                1.2.6 put方法

                由于put方法代码量偏多，故使用代码+注释形式解读源码。

                1.2.6.1 putVal方法

                /** * HashMap的put操作源码+注释 */public V put(K key, V value) {    // 先根据hash()方法，计算存放元素在table数组中的下标    return putVal(hash(key), key, value, false, true);}// hash方法static final int hash(Object key) {    int h;    // 如果key为null，返回hash=0    // 如果key不为null，那么进行key的hashCode值的高低位异或运算，返回结果作为hash值    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}// putVal方法final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {    Node[] tab; Node p; int n, i;    // 如果第一次插入，table为空或者length等于0    if ((tab = table) == null || (n = tab.length) == 0)        // 调用resize方法进行初始化        n = (tab = resize()).length;    // 通过hash值计算索引位置，将该索引位置的头节点赋值给p且p为空    // 实则进行取余操作 == p=tab[hash%length]    if ((p = tab[i = (n - 1) & hash]) == null)        // 在该索引位置新增一个节点        tab[i] = newNode(hash, key, value, null);    else {        // table表该索引位置不为空，则会发生hash冲突        Node e; K k;        // 当p节点的hash值和key跟传入的相等        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            // p节点即为要查找的目标节点，将p节点赋值给e节点            e = p;        // 当p节点为TreeNode        else if (p instanceof TreeNode)            // 调用红黑树的putTreeVal方法查找目标节点            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);        else {            // 判断完，则p节点为普通链表节点            //遍历节点操作，使用binCount统计链表的节点数            for (int binCount = 0; ; ++binCount) {                // p的next节点为空时，代表找不到目标节点                if ((e = p.next) == null) {                    // 新增一个节点并插入链表尾部                    p.next = newNode(hash, key, value, null);                    // 当binCount节点数超过8个                    // TREEIFY_THRESHOLD - 1：由于循环是从p节点的下一个节点开始的                    if (binCount >= TREEIFY_THRESHOLD - 1)                        // 调用treeifyBin方法将链表节点转为红黑树节点                        treeifyBin(tab, hash);                    break;                }                // e节点的hash值和key值与传入的相同                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    // e节点即为目标节点，跳出循环                    break;                // 将p指向下一个节点，继续往后遍历                p = e;              }        }        // e节点不为空，代表目标节点存在        if (e != null) {            // 使用传入的value覆盖该节点的value，即保留原来元素的value            V oldValue = e.value;            // 当oldValue为空            if (!onlyIfAbsent || oldValue == null)                // 替换value                e.value = value;            // 用于LinkedHashMap            afterNodeAccess(e);            // 返回一个原有的value            return oldValue;        }    }    // 添加操作执行后，对modCount、size做加一操作    ++modCount;    // 插入节点后节点数超过阈值    if (++size > threshold)        // 调用resize方法进行扩容        resize();    // 用于LinkedHashMap    afterNodeInsertion(evict);     return null;}

                1.2.6.2 putTreeVal方法

                /** * 当阈值达到触发红黑树的put的源码+注释 */final TreeNode putTreeVal(HashMap map, Node[] tab,                               int h, K k, V v) {    Class kc = null;    boolean searched = false;    // TreeNode继承于LinkedHashMap.Entry    // parent节点不等于空，则查找根节点    // 即得出索引位置的头节点并不一定为红黑树的根节点    TreeNode root = (parent != null) ? root() : this;    // 将根节点赋值给p节点，开始进行查找    for (TreeNode p = root;;) {        int dir, ph; K pk;        // 当传入的hash值小于p节点的hash值        if ((ph = p.hash) > h)            // 将dir赋值为-1，代表向p的左边查找树            dir = -1;        // 否则传入的hash值大于p节点的hash值        else if (ph