Java魔法解密：HashMap底层机制大揭秘-Toy模板网

这篇具有很好参考价值的文章主要介绍了Java魔法解密：HashMap底层机制大揭秘。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Java魔法解密：HashMap底层机制大揭秘,深入解析源码,java,源代码管理

一、源码深度解析

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

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

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

通用性（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 类信息

Java魔法解密：HashMap底层机制大揭秘,深入解析源码,java,源代码管理

1.2.2 常量属性

Java魔法解密：HashMap底层机制大揭秘,深入解析源码,java,源代码管理

1.2.3 变量属性

Java魔法解密：HashMap底层机制大揭秘,深入解析源码,java,源代码管理

1.2.4 节点信息

Java魔法解密：HashMap底层机制大揭秘,深入解析源码,java,源代码管理

1.2.5 构造方法

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

Java魔法解密：HashMap底层机制大揭秘,深入解析源码,java,源代码管理

2、构造一个带指定初始容量和默认加载因子（0.75）的空HashMap。
Java魔法解密：HashMap底层机制大揭秘,深入解析源码,java,源代码管理

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

Java魔法解密：HashMap底层机制大揭秘,深入解析源码,java,源代码管理

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

Java魔法解密：HashMap底层机制大揭秘,深入解析源码,java,源代码管理

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

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

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

使用双向链表：双向链表可以记录数据的访问顺序，当某个数据被访问时，可以将其移动到链表的头部或尾部。头部表示最近访问的数据，尾部表示最久未被访问的数据。
使用哈希表：哈希表用于快速查找缓存中的数据，可以将数据的键（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<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    // TreeNode<K,V>继承于LinkedHashMap.Entry<K,V>
    // parent节点不等于空，则查找根节点
    // 即得出索引位置的头节点并不一定为红黑树的根节点
    TreeNode<K,V> root = (parent != null) ? root() : this;
    // 将根节点赋值给p节点，开始进行查找
    for (TreeNode<K,V> 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 < h)
            // 将dir赋值为1，代表向p的右边查找树
            dir = 1;
        // 当传入的key值等于p节点的key值
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            // 即p节点为目标节点, 返回p节点
            return p;
        // 当k所属的类没有实现Comparable接口 或 k和p节点的key相等
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            // 由于局部变量初始为false，即当第一次判断是符合条件的
            if (!searched) {
                TreeNode<K,V> q, ch;
                // 查找过后标记为true
                searched = true;
                // 从p节点的左节点和右节点分别调用find方法进行查找
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    // 查找到目标节点则返回
                    return q;
            }
            // 否则使用定义的一套规则来比较k和p节点的key的大小, 用来决定向左还是向右查找
            // dir<0则代表k<pk，则向p左边查找；反之亦然
            dir = tieBreakOrder(k, pk); 
        }
 		// xp赋值为x的父节点,中间变量,用于下面给x的父节点赋值
        TreeNode<K,V> xp = p;   
        // dir<=0则向p左边查找,否则向p右边查找,如果为null
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            // xp的next节点
            Node<K,V> xpn = xp.next;    
            // 创建新的节点, 其中x的next节点为xpn, 即将x节点插入xp与xpn之间
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            // 调整x、xp、xpn之间的属性关系
            // 如果dir <= 0
            if (dir <= 0) 
                //  代表x节点为xp的左节点
                xp.left = x;
            else        
                // 如果dir> 0, 则代表x节点为xp的右节点
                xp.right = x;
            // 将xp的next节点设置为x
            xp.next = x;    
            // 将x的parent和prev节点设置为xp
            x.parent = x.prev = xp; 
            // 当xpn不为空
            if (xpn != null)
                // 将xpn的prev节点设置为x节点,与上文的x节点的next节点对应
                ((TreeNode<K,V>)xpn).prev = x;
            // 进行红黑树的插入平衡调整
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

1.2.6.3 tieBreakOrder方法

/**
 * 使用定义的一套规则来比较k和p节点的key的大小
 */
static int tieBreakOrder(Object a, Object b) {  
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().
         compareTo(b.getClass().getName())) == 0)
        // a < b为-1，a > b为1
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
             -1 : 1);
    return d;
}

1.2.6.4 treeifyBin方法

/**
 * 将链表转为红黑树
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 当tab为空或者tab的长度小于64
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        // 进行扩容
        resize();
    // 根据hash值计算索引值，将该索引位置的节点赋值给e且e不为null
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        // 从e开始遍历该索引位置的链表
        do {
            // 将链表节点转红黑树节点
            TreeNode<K,V> p = replacementTreeNode(e, null);
            // tl为空代表为第一次循环
            if (tl == null)	
                // 将头节点赋值给hd
                hd = p;
            else {
                // 如果不是第一次遍历
                // 当前节点的prev属性设为上一个节点
                p.prev = tl;  
                // 上一个节点的next属性设置为当前节点
                tl.next = p;    
            }
            // 将p节点赋值给tl，用于在下一次循环中作为上一个节点进行一些链表的关联操作（p.prev = tl 和 tl.next = p）
            tl = p;
        } while ((e = e.next) != null);
        // 将tab该索引位置赋值为新的TreeNode的头节点，如果该节点不为空
        if ((tab[index] = hd) != null)
            // 以头节点(hd)为根节点, 构建红黑树
            hd.treeify(tab);
    }
}

// 将链表节点转红黑树节点
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
   return new TreeNode<>(p.hash, p.key, p.value, next);
}

1.2.6.5 treeify方法

/**
 * 将哈希表中的链表结构转换为树形结构，以提高查找效率
 */
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    // 开始一个循环，初始化变量x为当前节点，然后在每次迭代中将x更新为next
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        // next赋值为x的下个节点
        next = (TreeNode<K,V>)x.next;  
        // 将x的左右节点设置为空
        x.left = x.right = null;    
        // 如果还没有根节点
        if (root == null) {
            // 根节点没有父节点，设为null
            x.parent = null; 
            // 根节点必须为黑色,false为黑色
            x.red = false; 
            // 在将x设置为根节点
            root = x;   
        }
        // 如果有根节点
        else {
            // k赋值为x的key
            K k = x.key;
            // h赋值为x的hash值
            int h = x.hash;	
            // 定义一个类型未知的变量kc
            Class<?> kc = null;
            // 开始一个无限循环，初始化变量p为root节点，表示对树进行遍历
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                // 比较当前节点x的哈希值h与节点p的哈希值ph，根据比较结果给变量dir赋值
                // 如果x节点的hash值小于p节点的hash值，则将dir赋值为-1, 代表向p的左边查找
                if ((ph = p.hash) > h)
                    dir = -1;
                // 如果x节点的hash值大于p节点的hash值，则将dir赋值为1, 代表向p的右边查找
                else if (ph < h)
                    dir = 1;
                // x的hash值和p的hash值相等，则比较key值
                // 如果k没有实现Comparable接口 或者 x节点的key和p节点的key相等
                else if ((kc == null && 
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    // 使用定义的一套规则来比较x节点和p节点的大小，用来决定向左还是向右查找
                    dir = tieBreakOrder(k, pk);
 
                // 将p节点的父节点赋值给xp,中间变量用于下面给x的父节点赋值
                TreeNode<K,V> xp = p;   
                // dir<=0则向p左边查找,否则向p右边查找,如果为null,则代表该位置即为x的目标位置
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    // x的父节点即为最后一次遍历的p节点
                    x.parent = xp; 
                    // 如果dir <= 0, 代表x节点为父节点的左节点
                    if (dir <= 0)   
                        xp.left = x;
                    // 如果dir > 0, 代表x节点为父节点的右节点
                    else    
                        xp.right = x;
                    // 进行红黑树的插入平衡(通过左旋、右旋和改变节点颜色来保证当前树符合红黑树的要求)
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    // 如果root节点不在tab索引位置的头节点, 则将其调整为头节点
    moveRootToFront(tab, root);
}

1.2.7 get方法

/**
 * HashMap的get操作源码+注释
 */
public V get(Object key) {
    Node<K,V> e;
    // 调用hash(key)方法计算键key的哈希值，然后调用getNode方法获取与该键对应的节点，将结果赋给变量e
    // 如果e为null，则返回null；否则返回e节点的值e.value
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
 
// 获取与该键对应的节点
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 对table进行校验：table不为空 && table长度大于0 && table索引位置(使用table.length - 1和hash值进行位与运算)的节点不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 检查first节点的hash值和key是否和入参的一样，如果一样则first即为目标节点，直接返回first节点
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 如果first不是目标节点，并且first的next节点不为空则继续遍历
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                // 如果是红黑树节点，则调用红黑树的查找目标节点方法getTreeNode
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 继续遍历
            do {
                // 执行链表节点的查找，向下遍历链表, 直至找到节点的key和入参的key相等时,返回该节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 找不到符合的返回空
    return null;
}

1.2.8 remove方法

/**
 * HashMap的remove操作源码+注释
 */
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
 
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 如果table不为空 && table长度大于0 && 根据hash值计算出来的索引位置不为空, 将该位置的节点赋值给p
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 如果p的hash值和key都与入参的相同, 则p即为目标节点, 赋值给node
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 否则将p.next赋值给e，向下遍历节点
        else if ((e = p.next) != null) {
            // 如果p是TreeNode则调用红黑树的方法查找节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 否则，进行普通链表节点的查找
                do {
                    // 当节点的hash值和key与传入的相同,则该节点即为目标节点
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        // 赋值给node, 并跳出循环
                        node = e;	
                        break;
                    }
                    // p节点赋值为本次结束的e，在下一次循环中，e为p的next节点
                    p = e;  
                    // e指向下一个节点
                } while ((e = e.next) != null); 
            }
        }
        // 如果node不为空，即根据传入key和hash值查找到目标节点，则进行移除操作
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 如果是TreeNode则调用红黑树的移除方法
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 如果node是该索引位置的头节点则直接将该索引位置的值赋值为node的next节点
            // “node == p”只会出现在node是头节点的时候，如果node不是头节点，则node为p的next节点
            else if (node == p)
                tab[index] = node.next;
            // 否则将node的上一个节点的next属性设置为node的next节点
            // 即将node节点移除, 将node的上下节点进行关联(链表的移除)
            else
                p.next = node.next;
            ++modCount;
            --size;
            // 供LinkedHashMap使用
            afterNodeRemoval(node); 
            // 返回被移除的节点
            return node;
        }
    }
    return null;
}

1.2.9 resize方法

/**
 * HashMap的resize操作源码+注释
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 旧表的容量不为0
    if (oldCap > 0) {
        // 判断旧表的容量是否超过最大容量值
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 将阈值设置为Integer.MAX_VALUE，并直接返回旧表
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 将newCap赋值为oldCap的2倍，如果newCap<最大容量小于最大容量值并且oldCap>=16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 将新阈值设置为原来的两倍
            newThr = oldThr << 1; // double threshold
    }
    // 如果旧表的容量的阈值大于0, 是因为初始容量被放入阈值，则将新表的容量设置为旧表的阈值
    else if (oldThr > 0)
        newCap = oldThr;
    else {
        // 旧表的容量为0, 旧表的阈值为0，这种情况是没有传初始容量的new方法创建的空表，将阈值和容量设置为默认值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新表的阈值为空, 则通过新的容量*负载因子获得阈值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 将当前阈值设置为刚计算出来的新的阈值，定义新表，容量为刚计算出来的新容量，将table设置为新定义的表
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 如果旧表不为空，则需遍历所有节点，将节点赋值给新表
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 将索引值为j的旧表头节点赋值给e
            if ((e = oldTab[j]) != null) {  
                // 将旧表的节点设置为空, 以便垃圾收集器回收空间
                oldTab[j] = null; 
                // 如果e.next为空, 则代表旧表的该位置只有1个节点，计算新表的索引位置, 直接将该节点放在该位置
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果是红黑树节点，则进行红黑树的重hash分布(跟链表的hash分布基本相同)
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 如果是普通的链表节点，则进行普通的重hash分布
                    // 存储索引位置为:“原索引位置”的节点
                    Node<K,V> loHead = null, loTail = null; 
                    // 存储索引位置为:“原索引位置+oldCap”的节点
                    Node<K,V> hiHead = null, hiTail = null; 
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 如果e的hash值与旧表的容量进行与运算为0,则扩容后的索引位置跟旧表的索引位置一样
                        if ((e.hash & oldCap) == 0) {
                            // 如果loTail为空
                            if (loTail == null) 
                                // 将loHead赋值为第一个节点
                                loHead = e; 
                            else
                                // 否则将节点添加在loTail后面
                                loTail.next = e;  
                            // 并将loTail赋值为新增的节点
                            loTail = e; 
                        }
                        else {
                             // 如果hiTail为空, 代表该节点为第一个节点
                            if (hiTail == null)
                                // 将hiHead赋值为第一个节点
                                hiHead = e; 
                            else
                                // 否则将节点添加在hiTail后面
                                hiTail.next = e;   
                            // 并将hiTail赋值为新增的节点
                            hiTail = e; 
                        }
                    } while ((e = next) != null);
                    // 如果loTail不为空（说明旧表的数据有分布到新表上“原索引位置”的节点），则将最后一个节点的next设为空，并将新表上索引位置为“原索引位置”的节点设置为对应的头节点
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 如果hiTail不为空（说明旧表的数据有分布到新表上“原索引+oldCap位置”的节点），则将最后一个节点的next设为空，并将新表上索引位置为“原索引+oldCap”的节点设置为对应的头节点
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    // 返回新表
    return newTab;
}

二、应用与最佳实践

2.1 在实际项目中如何合理使用HashMap

合理使用HashMap的建议：

缓存数据：可以使用HashMap作为缓存的数据结构，将计算结果或者频繁访问的数据存储在HashMap中，以提高数据的访问速度。
数据索引：在需要按照某个字段快速查找数据的场景下，可以使用HashMap来构建索引，以便快速定位数据对象。
配置信息存储：可以使用HashMap来存储应用程序的配置信息，例如键值对形式的配置参数。
数据分组：当需要对数据进行分组时，可以使用HashMap来进行分组存储，以便快速获取特定分组的数据。
缓存计算结果：在一些需要频繁计算的场景下，可以使用HashMap来缓存计算结果，避免重复计算。
快速访问和修改：HashMap提供了快速的查找、插入和删除操作，适合于需要频繁进行这些操作的场景。
代替多层嵌套的条件判断：有时候可以使用HashMap代替多层嵌套的条件判断，提高代码的可读性和可维护性。
事件处理：可以在事件驱动的系统中使用HashMap来保存事件处理器，根据事件类型快速找到对应的处理器进行处理。
路由表：在网络相关的应用中，可以使用HashMap来构建路由表，快速查找目标地址对应的路由信息。

2.2 最佳实践和注意事项

最佳实践：

初始化容量： 在创建HashMap时，尽量提供初始容量，以减少扩容操作的频率。这可以通过构造函数中的参数来完成，如 HashMap(int initialCapacity)。
```
Map<String, Integer> map = new HashMap<>(16); // 初始化容量为16
```
负载因子： 负载因子是指哈希表在自动扩容之前可以达到多满的一个度量。默认负载因子是0.75，你可以根据你的需求调整。
```
Map<String, Integer> map = new HashMap<>(16, 0.8f); // 指定负载因子为0.8
```
选择好的哈希函数： 如果你使用自定义对象作为键，确保实现了合适的hashCode()和equals()方法。
线程安全性： 如果在多线程环境下使用HashMap，考虑使用ConcurrentHashMap，它提供了更好的并发性能。
```
Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();
```
遍历方式： 使用entrySet()来遍历HashMap，而不是分别使用keySet()和values()。这可以避免多次计算哈希码。
```
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    // 处理每个键值对
}
```

注意事项：

空指针检查： 在使用get()方法获取值之前，最好先检查键是否存在，以避免空指针异常。

if (map.containsKey(key)) {
    // 避免空指针异常
    Integer value = map.get(key);
    // 处理值
}

键和值的类型： 注意HashMap的键和值的类型，确保它们符合你的预期。使用泛型可以在编译时提供类型检查。
扩容代价： HashMap在达到一定负载因子时会自动扩容，这可能导致性能损失。在性能敏感的场景中，可以考虑手动调整容量以减少扩容的发生。
不要过度使用HashMap： 在某些情况下，可能有更适合的数据结构，如LinkedHashMap、TreeMap等，取决于你的需求。
了解并发限制： 如果在并发环境下使用HashMap，要注意可能出现的并发限制，确保你的代码是线程安全的。

三、结论

3.1 对HashMap的全面总结

HashMap的全面总结：

概述：

定义： HashMap是Java集合框架中的一部分，实现了Map接口，用于存储键值对。
特性： 允许存储null键和null值，非同步（不是线程安全的）。

基本操作：

插入元素： put(key, value)方法用于插入键值对。
获取元素： get(key)方法用于根据键获取值。
删除元素： remove(key)方法用于根据键删除键值对。

内部实现：

数组+链表/红黑树： HashMap内部使用一个数组来存储桶(bucket)，每个桶是一个链表或者红黑树，用于解决哈希冲突。
哈希算法： 通过对键的哈希码进行运算，确定键在数组中的位置。

哈希冲突：

链表解决冲突： 相同哈希码的键值对以链表形式存储在同一桶中。
红黑树优化： 当链表长度过长时，会将链表转换为红黑树，以提高检索效率。

扩容和负载因子：

负载因子： 默认为0.75，表示当HashMap中的元素个数达到容量乘以负载因子时，进行扩容操作。
扩容： 当达到负载因子时，HashMap会创建一个新的容量是原容量两倍的数组，将原有元素重新分配到新的数组中。

性能：

平均时间复杂度： 插入、删除、查找的平均时间复杂度都是O(1)，在理想情况下。
注意： 由于哈希冲突和扩容操作，性能可能会有所下降。

使用注意事项：

线程安全： HashMap不是线程安全的，如果需要在多线程环境中使用，可以考虑使用ConcurrentHashMap。
equals和hashCode方法： 为了正确存储和检索对象，键的类必须正确实现equals和hashCode方法。

JDK版本变化：

JDK 8： 引入了红黑树优化，以提高性能。
JDK 9： 基于树的桶(bin)中的元素现在是按插入顺序排序。

3.2 鼓励读者深入学习和实践

源码分析： 阅读HashMap的源代码是学习其实现原理的一种有效方式。通过查看Java标准库的HashMap源码，你可以深入了解它是如何处理哈希冲突、计算哈希码、扩容等细节的。
实际应用： 将HashMap应用于实际项目中，观察其在不同场景下的性能表现。理解何时使用HashMap以及如何调整其初始容量等参数是很重要的。
深入学习数据结构和算法： 了解哈希表是如何在计算机科学中工作的，并学习其他数据结构和算法，有助于更好地理解HashMap的优势和局限性。
参与开源项目： 如果可能，参与开源项目，特别是与数据结构和算法相关的项目。通过实际的编码和与其他开发者的交流，你可以深化对HashMap以及其他数据结构的理解。

盈若安好，便是晴天文章来源地址https://www.toymoban.com/news/detail-753349.html

到了这里，关于Java魔法解密：HashMap底层机制大揭秘的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

二维码2

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

二维码2

一、源码深度解析

二、应用与最佳实践

三、结论