Java 基础——HashMap 底层数据结构与源码分析

爱被打了一巴掌 2023-10-09 17:31 17阅读 0赞

#### 目录 ####

*  1.HashMap 简介
 *  2.HashMap 底层数据结构
 *   *  2.1.JDK1.8 之前
     *  2.2.JDK1.8 及以后
     *  2.3.什么是红黑树？红黑树有什么优缺点？
 *  3.常量定义
 *   *  3.1.默认初始化容量
     *  3.2.最大容量
     *  3.3.负载因子
     *  3.4.阈值
 *  4.HashMap 源码分析
 *   *  4.1.构造函数
     *  4.2.Node<K, V>
     *  4.3.hash(Object key)
     *  4.4.put(K key, V value)
     *   *  4.4.1.流程
         *  4.4.2.源码
     *  4.5.get(Object key)
     *   *  4.5.1.流程
         *  4.5.2.源码
     *  4.6.resize()
     *   *  4.6.1.流程
         *  4.6.2.源码
 *  5.相关面试题
 *   *  new Hashmap<1000> 和 new Hashmap<10000> 在数据都塞满的时候有什么区别？（提示：扩容相关）

> 参考文章：  
> [HashMap 源码原理详解][HashMap]

> 相关文章：  
> [Java 基础——HashMap 遍历方式][Java _HashMap]

## 1.HashMap 简介 ##

（1）HashMap 基于哈希表的 `Map 接口`实现，主要用来存放键值对（允许使用 `null 值`和 `null 键`），是非线程安全的。  
（2）HashMap 默认的初始化大小为 `16`。之后每次扩充，容量变为原来的 2 倍。并且， HashMap 总是使用 2 的幂作为哈希表的大小。

![在这里插入图片描述][8b4e181837eb487b8ec603c2804cb5ad.png]

## 2.HashMap 底层数据结构 ##

### 2.1.JDK1.8 之前 ###

（1）JDK1.8 之前 HashMap 底层是**数组 + 链表**结合在一起使用，也就是**链表散列**。HashMap 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值，然后通过 (length - 1) & hash 判断当前元素存放的位置（这里的 length 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过**拉链法**解决冲突。

> 所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法，换句话说使用扰动函数之后可以**减少 hash 冲突，提高效率**。hash 方法的具体分析可以查看第 4 节中的源码分析部分。

（2）拉链法指将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。如果遇到哈希冲突，则将冲突的值加添加到链表中即可，如下图所示：

![在这里插入图片描述][04ad835272e24956bd2879fb33da492b.png]

### 2.2.JDK1.8 及以后 ###

相比于之前的版本， JDK1.8 及以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时：

*  如果数组 table 的长度小于 64，那么会选择进行**数组扩容**，而不是转换为红黑树；
 *  如果数组 table 的长度大于等于 64，那么**将链表转化为红黑树**，以减少搜索时间。

![在这里插入图片描述][e220d8a26c8a453a8485cea2125d6532.png]

> TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了**解决二叉查找树的缺陷**，因为二叉查找树在某些情况下会退化成一个**线性结构**。

### 2.3.什么是红黑树？红黑树有什么优缺点？ ###

（1）红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个额外的属性：颜色（红色或黑色），并通过一些规则来确保树始终保持平衡。红黑树具有以下特点：

*  **节点颜色**：每个节点要么是红色，要么是黑色。
 *  **根节点和叶子节点**：根节点是黑色的，叶子节点（空节点）是黑色的。
 *  **相邻节点颜色**：不能有两个相邻的红色节点。也就是说，红色节点不能连续出现。
 *  **黑色节点计数**：对于任意一个节点，从该节点到其所有后代叶子节点路径上的黑色节点数量是相同的，称为黑色高度。

（2）红黑树相对于普通的二叉搜索树具有以下优点：

*  自平衡性：通过遵循红黑树的定义和旋转操作，保持了树的平衡性，避免了极端情况下的树退化，确保了较稳定的性能。
 *  插入和删除操作相对高效：红黑树的插入和删除操作需要进行旋转和颜色调整，但其时间复杂度仍然保持在O(log N)级别，效率较高。
 *  查找操作比较快：红黑树是二叉搜索树，因此查找操作的平均时间复杂度为O(log N)。

（3）红黑树的缺点包括：

*  相比于普通的二叉搜索树，红黑树的**实现相对复杂**，因为需要维护颜色和平衡性等属性。
 *  在插入和删除节点时，需要**进行颜色调整和旋转操作**，相对比较耗费时间和计算资源。
 *  红黑树的实现相对于简单的数据结构来说，**需要更多的内存空间**，因为每个节点需要存储额外的颜色属性。

（4）尽管红黑树有一些缺点，但在一些需要高效的插入、删除和查找操作的场景下，红黑树仍然被广泛应用，比如在许多编程语言和数据库的内部实现中。

> 与红黑树有关的具体知识可以参考[【数据结构】史上最好理解的红黑树讲解，让你彻底搞懂红黑树][Link 1]这篇文章。

## 3.常量定义 ##

### 3.1.默认初始化容量 ###

/**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

**（1）为什么不直接使用 16 代替 1 << 4？**

*  为了避免使用魔法数字，使得常量定义本身就具有自我解释的含义。
 *  强调这个数必须是 2 的幂。

> 在编程领域，魔法数字指的是**莫名其妙出现的数字**，数字的意义必须通过详细阅读才能推断出来。

（2）HashMap 中数组 table 长度为什么是 2 的 n 次方？源码中是如何保证的？  
① 为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。Hash 值的范围值 -2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以**这个散列值是不能直接拿来用的**。

② 我们首先可能会想到通过**取余操作**来实现。但是与 (&) 运算速度比取余 (%) 取模运算快，并且在取余 (%) 操作中如果除数是 2 的幂次，则等价于与其除数减一的与 (&) 操作，即 **hash % length == hash & (length - 1) 的前提是 length 是 2 的 n 次方**。

③ 此外，如果 HashMap 的长度为 2 的 n 次方，那么在扩容迁移时不需要再重新定位新的位置了，**因为扩容后元素新的位置，要么在原下标位置，要么在原下标 + 扩容前长度的位置**。

④ HashMap 源码中的 **tableSizeFor(int cap)** 可以保证其长度永远是是 2 的 n 次方。

/**
     * Returns a power of two size for the given target capacity.
     */
    //返回大于且最接近 cap 的 2^n，例如 cap = 17 时，返回 32
    static final int tableSizeFor(int cap) {
        
    	// n = cap - 1 使得 n 的二进制表示的最后一位和 cap 的最后一位一定不一样
        int n = cap - 1;
        //无符号右移，在移动期间，使用 | 运算保证低位全部是 1
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

> ① 无符号右移 >>>：**忽略符号位，空位均用 0 补齐**，最终结果必为非负数。  
> 具体分析可参考[HashMap 的长度为什么必须是 2 的 n 次方？][HashMap _ 2 _ n]这篇文章。

### 3.2.最大容量 ###

/**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

当然了 Interger 能表示的最大范围为 231 \- 1，除此之外，231 \- 1 是 20 亿，每个哈希条目需要一个对象作为条目本身，一个对象作为键，一个对象作为值。在为应用程序中的其他内容分配空间之前，最小对象大小通常为 24 字节左右，因此这将是 1440 亿字节。但可以肯定地说，最大容量限制只是理论上的，实际内存也没这么大！

### 3.3.负载因子 ###

（1）**当负载因子较大时**，给数组 table 扩容的可能性就会降低，所以相对占用内存较少（空间上较少），但是每条 entry 链上的元素会相对较多，查询的时间也会增长（时间上较多）。**当负载因子较少时**，给数组 table 扩容的可能性就会升高，那么内存空间占用就多，但是 entry 链上的元素就会相对较少，查出的时间也会减少。

（2）所以才有了负载因子是时间和空间上的一种折中的说法，那么设置负载因子的时候要考虑自己追求的是时间还是空间上的少。那么为什么默认负载因子 DEFAULT\_LOAD\_FACTOR 默认设置为 0.75？

/**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

其实 Hashmap 源码中给出了解释：

Because TreeNodes are about twice the size of regular nodes, we
    use them only when bins contain enough nodes to warrant use
    (see TREEIFY_THRESHOLD). And when they become too small (due to
    emoval or resizing) they are converted back to plain bins.  In
    usages with well-distributed user hashCodes, tree bins are
    rarely used.  Ideally, under random hashCodes, the frequency of
    nodes in bins follows a Poisson distribution
    (http://en.wikipedia.org/wiki/Poisson_distribution) with a
    parameter of about 0.5 on average for the default resizing
    threshold of 0.75, although with a large variance because of
    resizing granularity. Ignoring variance, the expected
    occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
    factorial(k)). The first values are:
    0:    0.60653066
    1:    0.30326533
    2:    0.07581633
    3:    0.01263606
    4:    0.00157952
    5:    0.00015795
    6:    0.00001316
    7:    0.00000094
    8:    0.00000006
    more: less than 1 in ten million

简单翻译一下就是：在理想情况下，使用随机哈希码时节点出现的频率在 hash 桶中遵循`泊松分布 (Poisson Distribution)`，上面的解释给出了桶中元素个数和概率的对照。从中可以看到**当桶中元素到达 8 个时，概率已经变得非常小，也就是说用 0.75 作为负载因子，每个碰撞位置的链表长度超过８是几乎不可能的**。

### 3.4.阈值 ###

/**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
    static final int TREEIFY_THRESHOLD = 8;
    
    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
    static final int UNTREEIFY_THRESHOLD = 6;
    
    /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    /**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;
    
    /**
     * The number of key-value mappings contained in this map.
     */
    transient int size;

*  **TREEIFY\_THRESHOLD**：使用红黑树而不是列表的 bin count 阈值。当向具有至少这么多节点的 bin 中添加元素时，bin 被转换为树。这个值必须大于 2，并且应该至少为 8，以便与树删除中关于收缩后转换回普通容器的假设相匹配。
 *  **UNTREEIFY\_THRESHOLD**：在调整大小操作期间取消（分割）存储库的存储计数阈值。应小于 TREEIFY\_THRESHOLD，并最多 6 个网格与收缩检测下去除。
 *  **MIN\_TREEIFY\_CAPACITY**：最小的表容量，可为容器进行树状排列（否则，如果在一个 bin 中有太多节点，表将被调整大小），至少为 `4 * TREEIFY_THRESHOLD`，以避免调整大小和树化阈值之间的冲突。
 *  **threshold**：当 `size` 大于该值时，则调用 `resize` 方法进行扩容，`threshold = capacity * loadFactor`，例如初始时的 `threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 16 * 0.75 = 12`

## 4.HashMap 源码分析 ##

### 4.1.构造函数 ###

`HashMap` 中提供了 4 种构造函数，具体含义源码中的注释已经解释地比较清楚，可以直接查看：

/**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        this.loadFactor = loadFactor;
        // tableSizeFor(cap) 返回大于且最接近 cap 的 2^n，例如 cap = 17 时，返回 32
        this.threshold = tableSizeFor(initialCapacity);
    }
    
    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public HashMap(int initialCapacity) {
        
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    
    /**
     * Constructs a new <tt>HashMap</tt> with the same mappings as the
     * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
     * default load factor (0.75) and an initial capacity sufficient to
     * hold the mappings in the specified <tt>Map</tt>.
     *
     * @param   m the map whose mappings are to be placed in this map
     * @throws  NullPointerException if the specified map is null
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

### 4.2.Node<K, V> ###

HashMap 中`数组 table` 的元素类型即为 `Node<K, V>`，具体分析见下面代码：

/**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K, V>[] table;
        
    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K, V> implements Map.Entry<K,V> {
        
        final int hash;
        final K key;
        V value;
        //指向下一个节点
        Node<K,V> next;
    
        Node(int hash, K key, V value, Node<K,V> next) {
        
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    
        public final K getKey()        {
         return key; }
        public final V getValue()      {
         return value; }
        public final String toString() {
         return key + "=" + value; }
    	
    	//重写 hashCode() 方法
        public final int hashCode() {
        
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
    
        public final V setValue(V newValue) {
        
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
    	
    	//重写 equals() 方法
        public final boolean equals(Object o) {
        
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
        
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

### 4.3.hash(Object key) ###

（1）hash 方法用于计算 key 的最终的哈希值，其源码如下所示：

/**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
    static final int hash(Object key) {
        
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

（2）`hashCode()`：Object 类中的方法，同时也是一个 `native` 方法，返回当前对象的哈希值。

public class Object {
        
    	//...
    	
    	public native int hashCode();
    }

（3）看了 hash 方法的源码之后，大家可能会有下面的几个问题？

*  **为什么要将 key 的哈希值 h 右移 16 位并且与原来的哈希值 h 进行异或运算？**
    
     *  右移 16 位是为了让 h 的高 16 位也参与运算，可以更好地均匀散列，减少碰撞，进一步降低 hash 冲突的几率；
     *  异或运算是为了更好保留两组 32 位二进制数中各自的特征；
 *  为什么不是与 (&) 运算或者或 (|) 运算呢？
    
     *  如果是与运算，那么可以发现**运算之后的结果向 0 靠拢**，其原因在于在二进制位运算中，只有 1 & 1 的结果为 1，而其余结果均为 0，那么使用与运算不仅不能够保留原两组数据中各自的特征，而且还会**提高哈希冲突的概率**；
     *  如果是或运算，那么可以发现**运算之后的结果向 1 靠拢**，其原因与上面的与运算类似；

### 4.4.put(K key, V value) ###

#### 4.4.1.流程 ####

![请添加图片描述][97ee871cb6b049f1b4d2675df043b193.png]

put 方法的执行流程如下：

*  判断数组 `table` 是否为空，如果为空则执行 `resize()` 方法进行扩容；
 *  然后通过 `hash` 方法计算出 key 的哈希值，然后通过哈希值计算出 key 在数组中的索引位置 `i`，具体计算方法为 hash % n == hash & (length - 1)（其中 n 为数组 table 的长度，通过位运算替代取余运算可以提高计算效率）；
 *  如果 table\[i\] 为 null，直接新建节点添加；
 *  如果 table\[i\] 不为空，则判断 table\[i\] 的首个元素的 key 是否和传入的 key 一样：
    
     *  如果相同直接覆盖 value，并直接返回`旧的 value`（**上图中没有体现出来！**）；
     *  如果不相同，则判断 table\[i\] 是否是树节点类型 (`TreeNode`)，即 table\[i\] 是否是红黑树：
        
         *  如果是红黑树，则直接在树中插入键值对；
         *  如果不是红黑树，则说明当前索引位置 `i` 上的是一条链表，那么遍历该链表，当链表长度大于阈值（默认为 8）时：
            
             *  如果数组 table 的长度小于 64，那么会选择进行数组扩容（**上图中没有体现出来！**），然后再进行链表的插入操作；
             *  如果数组 table 的长度大于等于 64，那么将链表转化为红黑树，在红黑树中执行插入操作。
 *  遍历过程中若发现 key 已经存在直接`覆盖 value` 并直接返回`旧的 value`（**上图中没有体现出来！**）；
 *  插入成功后，判断实际存在的键值对数量 `size` 是否超多了最大容量 `threshold`，如果超过，则调用 `resize` 方法进行扩容。

#### 4.4.2.源码 ####

/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        
        return putVal(hash(key), key, value, false, true);
    }
    
    /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // p 为树节点类型
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
        
                for (int binCount = 0; ; ++binCount) {
        
                    if ((e = p.next) == null) {
        
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        	//将链表转换为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) {
         // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();	//扩容
        afterNodeInsertion(evict);
        return null;
    }

/**
     * Replaces all linked nodes in bin at index for given hash unless
     * table is too small, in which case resizes instead.
     */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        
        int n, index; Node<K,V> e;
        //数组⻓度如果⼩于 MIN_TREEIFY_CAPACITY (默认为 64)，则选择进行数组扩容，而不是转换为红黑树
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
        
            TreeNode<K,V> hd = null, tl = null;
            do {
        
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
        
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

### 4.5.get(Object key) ###

#### 4.5.1.流程 ####

> 下图来自[HashMap详细介绍（源码解析）][HashMap 1]这篇文章。

![在这里插入图片描述][d0cb9f0cb01246fdb19cfe495ff4343e.png]

get 方法的执行流程如下：

*  如果 `table` 为空，或者其长度为 0，则说明 hashMap 中没有元素，此时直接返回 null 即可；否则进行下面的操作；
 *  通过 `hash` 方法计算出 key 的哈希值，然后通过哈希值计算出 key 在数组中的索引位置，具体计算方法为 `hash % n == hash & (length - 1)`（其中 n 为数组 table 的长度，通过位运算替代取余运算可以提高计算效率）；
 *  然后再进行如下判断：
    
     *  如果该索引位置上没有节点，则直接返回 `null`；
     *  如果该索引位置上有节点，则先判断该位置上元素是否与 key 相同（这里的相同指的是 hashCode 以及 equals）：
        
         *  如果相同，则直接返回该元素对应的 `Node` 中的 value；
         *  如果不相同，则对结点类型进行判断：
            
             *  如果该结点是红黑树结点 (`TreeNode`)，则调用 `getTreeNode` 方法从红黑树中来进行搜索；
             *  否则遍历链表来进行搜索；
 *  如果经过以上步骤仍然没有找到，那么说明 hashMap 中不存在该 key，最终返回 `null` 即可。

#### 4.5.2.源码 ####

/**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    /**
     * Implements Map.get and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        
        Node<K,V>[] tab; 
        Node<K,V> first, e; 
        int n;
        K k;
        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
        
            	//在红黑树中查找
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //在链表中查找
                do {
        
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

### 4.6.resize() ###

> 参考文章：  
> [HashMap resize() 方法源码详解][HashMap resize_]

#### 4.6.1.流程 ####

`resize` 方法实现了 HashMap 的扩容机制，其执行流程如下：

*  计算扩容后的容量 `newCap` ，它等于旧容量 `oldCap` 的 2 倍
 *  创建长度为 `newCap` 的 Node<K, V> 数组 `newTab`；
 *  遍历旧数组 `OldTab` 中的每一个节点 e，主要目的在于将旧数组中的节点复制到新数组中，具体操作如下：
    
     *  如果当前节点 e 为空，则说明旧数组的当前索引上没有元素，判断下一个节点；
     *  如果当前节点 e 不为空，则进行如下判断：
        
         *  当前节点 e 的下一个节点为空，则说明当前索引上只有 e 这一个节点，然后通过 `e.hash & oldCap` 的值来判断扩容后的 e 的索引是否变化的，**如果该值为 0，则说明新索引与旧索引相同**；如果该值为 1，那么将 e 调整到新数组中索引为 `旧索引 + OldTab (该值等于新索引)` 的位置上，接着判断下一个节点；
         *  当前节点 e 的下一个节点不为空，则说明当前索引上有可能存储的是链表或者红黑树，继续如下判断：
            
             *  如果节点 e 是**树节点类型**，调用 TreeNode 中的 `split` 方法来调整节点；
             *  否则当前索引上存储的是一条链表，那么依次遍历这条链条上的节点，并且将其复制到新数组中；

> 注意：  
> ① 由于 resize() 源码细节比较多，所以上述流程只抓住了重要部分进行说明；  
> ② 通过 `e.hash & oldCap` 的值来判断扩容后的 e 的索引是否变化的证明以及**旧索引 + OldTab = 新索引**的证明见源码分析部分；

#### 4.6.2.源码 ####

/**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
    final Node<K,V>[] resize() {
        
    	//1.计算出新的 newCap (扩容后的容量)和 newThr (扩容后阈值)
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
        
        	//如果 oldCap 大于等于最大值就不再扩容，直接返回 oldTab 即可
            if (oldCap >= MAXIMUM_CAPACITY) {
        
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //如果没有超过最大值，那么就扩充为原来的 2 倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {
                       // zero initial threshold signifies using defaults
            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);
        }
        //2.根据 newCap 和 newThr 构造出新的 newTab
        threshold = newThr;
        @SuppressWarnings({
        "rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
        
        	// j : 0 ~ oldCap - 1，遍历 table，将每个 bucket 都移动到新的 buckets 中
            for (int j = 0; j < oldCap; ++j) {
        
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
        
                    oldTab[j] = null;
                    //如果该索引位上只有一个结点，则将 e 调整到索引为 e.hash & (newCap - 1) 的位置
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果该索引位上的结点是树节点类型，调用 TreeNode 中的 split 方法来调整节点
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //该索引位上是一条链表    
                    else {
         // preserve order
                    	/*
    						loHead: 表示调整后仍会处于原索引位的节点之间重新链接后的链表的头节点
    						loTail: 表示调整后仍会处于原索引位的节点之间重新链接后的链表的尾节点
    						hiHead: 表示调整后应该处于新索引位的节点之间重新链接后的链表的头节点
    						hiTail: 表示调整后应该处于新索引位的节点之间重新链接后的链表的尾节点
    					*/
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
        
                            next = e.next;
                            /* 
    							(e.hash & oldCap) == 0 表示索引不变
    							(e.hash & oldCap) == 1 表示索引变为"原索引 + oldCap"
    						*/
                            if ((e.hash & oldCap) == 0) {
        
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            } else {
        
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //索引 j 不变
                        if (loTail != null) {
        
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //索引 j 变为"j + oldCap"
                        if (hiTail != null) {
        
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

下面主要解释一下 `resize` 方法源码中如何通过 `e.hash & oldCap` 的值来判断扩容后的索引是否变化的。

（1）设 `oldCap` 为数组 table 的长度（设为 `16`），当前 key 的哈希值为 `hash`，那么 `oldCap` 一定是 2 的 n 次幂（前面 3.1 节中有解释过），并且当前 key 在 table 中所对应的索引 `oldj = hash % oldCap = hash & (oldCap - 1)`。

（2）现在假设扩容后 table 的长度为 `newCap`，那么 `newCap = oldCap * 2 = 32`，当前 key 在扩容后的 table 中所对应的索引为 `newj = hash & (newCap - 1)`，扩容前后的索引的二进制表示如下所示：

hash		xxxx ... xxxy xxxx		
    &	oldCap - 1	0000 ... 0000 1111
    	oldj		0000 ... 0000 xxxx
    
    	hash		xxxx ... xxxy xxxx		
    &	newCap - 1	0000 ... 0001 1111
    	newj		0000 ... 000y xxxx

由上述二进制表示可知， `oldj` 与 `newj` 是否相等取决于 `y` 的值：

*  如果 `y == 0`，那么说明 `oldj == newj`，当前 key 不需要调整；
 *  如果 `y == 1`，那么说明 `oldj != newj`，当前 key 需要调整到 `oldj + oldCap` 的位置，因为根据它们的二进制表示可以推出 `newj = oldj + oldCap`；

（3）`resize()` 源码中通过 `hash & oldCap` 的值来判断扩容后的索引是否有变化，`hash` 和 `oldCap` 的二进制表示如下所示：

hash		xxxx ... xxxy xxxx		
    &	oldCap		0000 ... 0001 0000
    	res			0000 ... 000y 0000

*  如果 `y == 0`，那么说明 `hash & oldCap == 0`，即 `oldj == newj`，所以扩容后的索引不需要调整；
 *  如果 `y == 1`，那么说明 `hash & oldCap == 1`，即 `newj = oldj + oldCap`，所以扩容后的索引调整为 `oldj + oldCap`；

（4）这种判断方法设计的巧妙之处在于：

*  省去了重新计算 hash 值的时间，因为只需要通过原 key 的 hash（即代码中的 `e.hash`）与 `oldCap` 相与的结果即可判断新索引的值；
 *  由于 `y` 是 0 还是 1 可以认为是**随机的**，因此扩容时均匀地把之前冲突的节点分散到新的 bucket 中。

## 5.相关面试题 ##

### new Hashmap<1000> 和 new Hashmap<10000> 在数据都塞满的时候有什么区别？（提示：扩容相关） ###

（1）创建一个 HashMap 时，可以指定初始容量 (initial capacity) 参数来设置初始大小。对于 `new HashMap<>(1000)` 和 `new HashMap<>(10000)`，它们的初始容量分别是 1000 和 10000。当 HashMap 中的元素个数接近或达到容量阈值时，HashMap 会自动进行扩容操作。扩容的目的是为了保持 HashMap 的负载因子 (load factor) 在一个可接受的范围内，以减少哈希冲突，提高查询性能。

（2）在数据都塞满的情况下，`new HashMap<>(1000)` 和 `new HashMap<>(10000)` 会有以下区别：

*  **扩容触发点**：HashMap 的默认负载因子是 0.75，即当实际元素个数达到容量的 75% 时，就会自动触发扩容。对于 `new HashMap<>(1000)` 来说，当元素个数达到 750 个时，就会触发扩容操作；而对于 `new HashMap<>(10000)` 来说，当元素个数达到 7500 个时，扩容操作开始执行。
 *  **扩容速度**：在扩容时，HashMap 会重新计算哈希值和重新分配桶的索引位置。当元素个数增多，扩容操作对于容量较小的HashMap而言，可能会比较频繁，增加了重新计算和重新分配的开销，导致性能降低。而对于容量较大的HashMap，由于扩容操作相对较少，可能对性能的影响较小。

（3）因此，在数据都塞满的情况下，`new HashMap<>(10000)` 会相对于 `new HashMap<>(1000)` 具有更好的性能，因为它的扩容触发点更晚，扩容的频率更低。然而，需要根据具体场景和数据量来选择合适的初始容量，以平衡内存占用和查询性能。如果预计数据量较大，可以选择较大的初始容量，减少扩容的频率。

[HashMap]: https://mp.weixin.qq.com/s/SURVmTf6K_ou85fShFzrNA
[Java _HashMap]: https://xgqngu.blog.csdn.net/article/details/129851260
[8b4e181837eb487b8ec603c2804cb5ad.png]: https://img-blog.csdnimg.cn/8b4e181837eb487b8ec603c2804cb5ad.png
[04ad835272e24956bd2879fb33da492b.png]: https://img-blog.csdnimg.cn/04ad835272e24956bd2879fb33da492b.png
[e220d8a26c8a453a8485cea2125d6532.png]: https://img-blog.csdnimg.cn/e220d8a26c8a453a8485cea2125d6532.png
[Link 1]: https://blog.csdn.net/cy973071263/article/details/122543826
[HashMap _ 2 _ n]: https://blog.csdn.net/qq_26125865/article/details/118316632
[97ee871cb6b049f1b4d2675df043b193.png]: https://img-blog.csdnimg.cn/97ee871cb6b049f1b4d2675df043b193.png
[HashMap 1]: https://feige.blog.csdn.net/article/details/103645634
[d0cb9f0cb01246fdb19cfe495ff4343e.png]: https://img-blog.csdnimg.cn/d0cb9f0cb01246fdb19cfe495ff4343e.png
[HashMap resize_]: https://blog.csdn.net/qq_40979103/article/details/125124340