【源码解读系列六】深入剖析HashMap的底层源码

柔情只为你懂 2023-07-18 02:38 35阅读 0赞

> **写在前面**： 我是 *扬帆向海*，这个昵称来源于我的名字以及女朋友的名字。我热爱技术、热爱开源、热爱编程。`技术是开源的、知识是共享的`。  
>   
> 这博客是对自己学习的一点点总结及记录，如果您对 *Java*、*算法* 感兴趣，可以关注我的动态，我们一起学习。  
>   
> `用知识改变命运，让我们的家人过上更好的生活`。

### 文章目录 ###

*   *   *  一、HashMap介绍及其源码剖析
         *  二、构造方法及其源码分析
         *  二、常用方法及其源码解析
         *   *  1. hash
             *  2. get(Object key)
             *  3. put(K key, V value)
             *  扩容机制
             *  4. remove(Object key)

### 一、HashMap介绍及其源码剖析 ###

> 面试官：扬帆向海，你对HashMap了解多少？你首先说说它的继承结构吧！

*  `HashMap`继承于AbstractMap，实现了Cloneable、Map、Serializable这些接口。
 *  `HashMap` 继承了AbstractList，实现了Map。
 *  `HashMap` 实现了Cloneable接口，即覆盖了函数clone()，所以它能被克隆。
 *  `HashMap` 实现了Serializable接口，这意味着HashMap支持序列化。

***顺便画出了它的继承结构***：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw_size_16_color_FFFFFF_t_70]

> 面试官：既然你说HashMap继承了AbstractList，实现了Map。那你再说说Map吧！

我去，这是要闹呢？但是还是得说。。。

*  Map 接口主要是用于保存具有映射关系的数据：key 和 value
 *  Map中的 key用 Set来存储， set是无序不可重复。`因此同一个 Map 对象所对应的类，必须重写 hashCode 和 equals 方法`。
 *  Map接口中的key与value都可以是任何引用类型的数据，并且它们之间是一对一的关系，因此`通过指定的 key 一定能找到唯一的、确定的value`

> 面试官：可以！看来你还理解的不错。那么接下来重点聊一下HashMap吧！

HashMap 的大致结构如下图所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw_size_16_color_FFFFFF_t_70 1]

其中哈希表是一个数组，我们经常把数组中的每一个节点称为一个桶，哈希表中的每个节点都用来存储一个键值对。`在插入元素时，如果发生冲突（即多个键值对映射到同一个桶上）的话，就会通过链表的形式来解决冲突`。在一个桶上可能存在多个键值对，在查找的时候，会先通过key的哈希值先定位到桶，再遍历桶上的所有键值对，找出key相等的键值对，从而来获取value值。

> 面试官：接下来聊聊HashMap的属性吧！

原来面试官都是一样的套路。。。  
![在这里插入图片描述][20200331143747753.jpg_pic_center]

***`HashMap 属性源码剖析`***

/** * The default initial capacity - MUST be a power of two. */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /** * 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;
    
        /** * The load factor used when none specified in constructor. */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        /** * 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;

***`属性分析：`***

*  `DEFAULT_INITIAL_CAPACITY`：HashMap 的默认容量是16
 *  `MAXIMUM_CAPACITY`: HashMap 的最大容是 2^30
 *  `DEFAULT_LOAD_FACTOR`：HashMap默认的负载因子为 0.75
 *  `TREEIFY_THRESHOLD`：链表长度大于变成树型结构的临界值8的时候，转化为红黑树
 *  `UNTREEIFY_THRESHOLD`：链表中红黑树存储的 Node 小于临界值6的时候，转化为链表
 *  `MIN_TREEIFY_CAPACITY`：Node 被树化时最小的 hash 表容量。当哈希表的大小超过这个值的时候，会把链式结构转化成树型结构，否则则是采取扩容来减少冲突

> 面试官：你一直在说Node，那你说说Node类

***`HashMap 属性源码剖析`***

// Node是单向链表，它实现了Map.Entry接口
    static class Node<K,V> implements Map.Entry<K,V> { 
        final int hash; // key的哈希值
        final K key; // 保存key
        V value; // 保存value
        Node<K,V> next; // 单链表用来指向后继节点
    
    	// 构造函数Hash值、键、值、下一个节点 
        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; }
    
        public final int hashCode() { 
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
    
        public final V setValue(V newValue) { 
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
    
    	// 判断两个node是否相等,若key和value都相等，则返回true. 可以与自身比较为true 
        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;
        }
    }

从源码里面可以看出，Node是 HashMap 中的一个静态内部类，`Node是单向链表，它实现了Map.Entry接口`，哈希表中的每一个节点都是 Node 类型。我们可以看到，Node 类中有 4 个属性，其中除了 key 和 value 之外，还有 hash 和 next 两个属性。hash 是用来存储 key 的哈希值的，next 是单向链表用来指向下一个节点。

> 面试官：接下来你说说对红黑树的理解

红黑树是一种近似平衡的二叉查找树，其主要的优点就是“平衡“，即左右子树高度几乎一致，以此来防止树退化为链表，通过这种方式来保障查找的时间复杂度为 log(n)。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw_size_16_color_FFFFFF_t_70_pic_center]

① 每个节点要么是红色，要么是黑色，但根节点永远是黑色的；  
② 每个红色节点的两个子节点一定都是黑色；  
③ 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）；  
④ 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；  
⑤ 所有的叶节点都是是黑色的（注意这里说叶子节点其实是上图中的 NIL 节点）；

在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件 3 或条件 4，需要通过调整使得查找树重新满足红黑树的条件。

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 
         TreeNode<K,V> parent;  // 父节点
         TreeNode<K,V> left;  // 左子树
         TreeNode<K,V> right;  // 右子树
         TreeNode<K,V> prev;    // needed to unlink next upon deletion 
         boolean red; // 颜色
         TreeNode(int hash, K key, V val, Node<K,V> next) { 
             super(hash, key, val, next);
         }
    
         /** * Returns root of tree containing this node. */
    	 // 返回当前节点的根节点 
         final TreeNode<K,V> root() { 
             for (TreeNode<K,V> r = this, p;;) { 
                 if ((p = r.parent) == null)
                     return r;
                 r = p;
             }
         }

### 二、构造方法及其源码分析 ###

① ***`HashMap(int initialCapacity, float loadFactor)`***

public HashMap(int initialCapacity, float loadFactor) { 
     	// 如果初始容量小于0，将会抛出异常 
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
         // 初始容量不能小于0；如果初始容量大于最大容量,将最大容量赋值给初始容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // 校验加载因子是否合法，如果加载因子小于0或为空，则抛出异常 
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        // 新的扩容临界值
        this.threshold = tableSizeFor(initialCapacity);
    }

当map容量达到这个临界值的时候，需要进行resize

② 有一个初始容量参数的构造方法 ***`HashMap(int initialCapacity)`***

public HashMap(int initialCapacity) { 
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

参数中传入初始容量，通过默认负载因子构造一个空的HashMap，把初始容量和默认加载因子作为入参调用HashMap(int initialCapacity, float loadFactor)的构造方法。

③ 无参构造方法 ***`HashMap()`***

public HashMap() { 
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

使用默认的加载因子0.75和默认初始容量16，来构造一个空的HashMap。

④ 有Map类型的参数的构造方法 ***`HashMap(Map<? extends K, ? extends V> m)`***

public HashMap(Map<? extends K, ? extends V> m) { 
    	// 将默认的负载因子赋值给成员变量loadFactor
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        // 调用PutMapEntries(),进行HashMap的初始化赋值过程
        putMapEntries(m, false);
    }

根据Map接口初始化一个新的HashMap，该HashMap拥有着和原Map中相同的映射关系，使用默认的初始容量和默认的载因子。

### 二、常用方法及其源码解析 ###

> 面试官：HashMap中有哪些方法呢？你对它们了解多少？

HashMap中常用的方法有get()、put()、remove()、hash()

#### 1. hash ####

static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这个hash方法先通过key的hashCode方法获取一个哈希值，再拿这个哈希值与它的高16位的哈希值做一个异或操作来得到最后的哈希值，计算过程可以参考下图。为啥要这样做呢？注释中是这样解释的：如果当n很小，假设为64的话，那么n-1即为63（0x111111），这样的值跟hashCode()直接做与操作，实际上只使用了哈希值的后6位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成冲突了，所以这里把高低位都利用起来，从而解决了这个问题。

#### 2. get(Object key) ####

用键，提取对应的值

public V get(Object key) { 
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

get()方法调用了getNode方法，getNode方法实现了Map.get和相关的方法

final Node<K,V> getNode(int hash, Object key) { 
    	//Entry对象数组 
        Node<K,V>[] tab; 
        // 在tab数组中经过散列的第一个位置
        Node<K,V> first, e; 
        int n; K k;
        //如果哈希表不为空 && key对应的桶上不为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) { 
            // 检查第一个Node是不是要找的Node
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
                // 判断是否有后续节点
            if ((e = first.next) != null) { 
            	// 如果当前的桶是采用红黑树处理冲突，则调用红黑树的get方法去获取节点
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 如果不是红黑树，则是传统的链式结构。通过循环遍历链表，找到key值和hash值都相同的Node
                do { 
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

实现步骤大致如下：

> ① 通过hash值获取该key映射到的桶。
> 
> ② 桶上的key就是要查找的key，则直接命中。
> 
> ③ 桶上的key不是要查找的key，则查看后续节点：
> 
>  *  如果后续节点是树节点，通过调用树的方法查找该key。
>  *  如果后续节点是链式节点，则通过循环遍历链查找该key。

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

放入键值对数据

public V put(K key, V value) { 
       return putVal(hash(key), key, value, false, true);
    }

put()方法调用了putVal方法，putVal()方法实现了Map.put和相关的方法。

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;
         // 如果table的在（n-1）&hash的值是空，就新建一个节点插入在该位置 
         if ((p = tab[i = (n - 1) & hash]) == null)
             tab[i] = newNode(hash, key, value, null);
         // 表示有冲突,开始处理冲突 
         else { 
             Node<K,V> e; K k;
             // 如果桶上节点的key与当前key重复，则p是要找的值
             if (p.hash == hash &&
                 ((k = p.key) == key || (key != null && key.equals(k))))
                 e = p;
             // 如果是采用红黑树的方式处理冲突，则通过红黑树的putTreeVal()方法插入键值对 
             else if (p instanceof TreeNode)
                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
             // 否则就是传统的链式结构 
             else { 
             	 // 采用循环遍历的方式，判断链中是否有重复的key 
                 for (int binCount = 0; ; ++binCount) { 
                 	 // 如果到了链尾还没找到重复的key，则说明HashMap没有包含该键 
                     if ((e = p.next) == null) { 
                     	 // 创建一个新节点插入到尾部
                         p.next = newNode(hash, key, value, null);
                         // 如果链的长度大于TREEIFY_THRESHOLD这个临界值，则把链变为红黑树
                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                             treeifyBin(tab, hash);
                         break;
                     }
                     // 找到了重复的key
                     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);
                 // 存在的Value值 
                 return oldValue;
             }
         }
         ++modCount;
         // 判断是否需要进行扩容，当实际大小(容量*加载因子)超过临界值时，会进行扩容 
         if (++size > threshold)
         	 // 扩容
             resize();
         afterNodeInsertion(evict);
         return null;
     }

> ① 先通过hash值计算出key映射到哪个桶。
> 
> ② 如果桶上没有碰撞冲突，则直接插入。  
> ③ 如果出现碰撞冲突了，则需要处理冲突：
> 
> > 如果该桶使用红黑树处理冲突，则调用红黑树的方法插入。  
> > 否则采用传统的链式方法插入。如果链的长度到达临界值，则把链转变为红黑树。
> 
> ④ 如果桶中存在重复的键，则为该键替换新值。  
> ⑤ 如果size大于阈值，则进行扩容。

#### 扩容机制 ####

***`何时进行扩容？`***

HashMap使用的是懒加载，构造完HashMap对象后，只要不进行put 方法插入元素之前，HashMap并不会去初始化或者扩容table。

当首次调用put方法时，HashMap会发现table为空然后调用resize方法进行初始化，当添加完元素后，如果HashMap发现size（元素总数）大于threshold（阈值），则会调用resize方法进行扩容.是当哈希表中的键值对个数超过阈值时，才进行扩容的！

final Node<K,V>[] resize() { 
    	// 把当前的table存放到oldTab中
        Node<K,V>[] oldTab = table;
        // 首先判断table是否为空，然后使用三元表达式进行赋值
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 把table的阈值赋值给oldThr
        int oldThr = threshold;
        // 定义变量newCap和newThr, 用来存放新的table的容量和阈值(临界值)
        int newCap, newThr = 0;
        // 计算扩容后的大小，如果oldCap 大于0
        if (oldCap > 0) { 
            // 如果当前容量超过最大容量，则无法进行扩容
            if (oldCap >= MAXIMUM_CAPACITY) { 
            	// 以int的最大值作为原来HashMap的阈值
                threshold = Integer.MAX_VALUE;
                // 返回oldTab
                return oldTab;
            }
            // 没超过最大值则扩为原来的两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 将newThr的值赋值为原HashMap的阈值的2倍 
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
        	// 将原阈值赋值给newCap
            newCap = oldThr;
        else {                // zero initial threshold signifies using defaults
        	
            // 默认容量作为newCap的值
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 默认初始容量*默认加载因子的结果赋值给newThr
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 如果newThr值为0，给newThr进行赋值
        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"})
        	// 创建一个容量为newCap的table
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        // 给table进行重新赋值 
        table = newTab;
        // 如果原来的HashMap不为空，则进行遍历
        if (oldTab != null) { 
        	// 遍历旧哈希表的每个桶，重新计算桶里元素的新位置 
            for (int j = 0; j < oldCap; ++j) { 
                Node<K,V> e;
                if ((e = oldTab[j]) != null) { 
                    oldTab[j] = null;
                    // 如果桶上只有一个键值对，则直接插入
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                     // 如果是通过红黑树来处理冲突的，则调用相关方法把树分离开 
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 如果采用链式处理冲突 
                    else {  // preserve order
                    	// 用于存放put后不移位的链表
                        Node<K,V> loHead = null, loTail = null;
                        // 用于存放put后移位的链表
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do { 
                            next = e.next;
                            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);
                        if (loTail != null) { 
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) { 
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        // 返回newTab
        return newTab;
    }

#### 4. remove(Object key) ####

找到指定的键，删除键值对

public V remove(Object key) { 
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

removeNode实现了Map.remove和相关的方法

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;
        // 如果当前key映射到的桶不为空
        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;
            // 如果桶上的节点就是要找的key，则直接命中
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) { 
            	// 如果是以红黑树处理冲突，则构建一个树节点
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                // 如果是以链式的方式处理冲突，则通过遍历链表来寻找节点 
                else { 
                    do { 
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) { 
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            // 比对找到的key的value跟要删除的是否匹配
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) { 
                // 通过调用红黑树的方法来删除节点 
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                // 使用链表的操作来删除节点 
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

--------------------

***由于水平有限，本博客难免有不足，恳请各位大佬不吝赐教！***

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw_size_16_color_FFFFFF_t_70]: /images/20230528/4a18e5f01f3f4ff08845e47e7793b5c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw_size_16_color_FFFFFF_t_70 1]: /images/20230528/981fdb9cb7174b5e854ea954907267b9.png
[20200331143747753.jpg_pic_center]: /images/20230528/6468a8c2d7ca419c8b4ab9217aa88d29.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/1a029ad6b8f347f4b8428cb288734d43.png