当前位置: 首页>后端>正文

HashMap 源码理解与面试

时间长了总是会容易遗忘的知识点

原文:https://blog.csdn.net/CrazyApes/article/details/121909849

[Toc]

前言

几乎是每次面试必问的问题,虽然别人已经写的很好了,但是自己整理总结一下可以加深印象。以JDK1.8以上版本为主介绍。

简介

Java 为数据结构中的映射定义了一个接口 java.util.Map,此接口主要有四个常用的实现类。
咱们主要是看HashMap

  • HashMap
    它根据 Key的hashCode 值存储数据。
    无序存储,但访问速度极快。
    最多只允许一条Key为null,允许多条Value为null。
    非线程安全,如果需要满足线程安全,可以用 Collections 的 synchronizedMap 方法使 HashMap 具有线程安全的能力(通过互斥锁实现),或者使用 ConcurrentHashMap。

  • Hashtable
    与 HashMap 类似,但是它承自Dictionary类
    key、value值均不可为 null。
    线程安全,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁(JDK1.7),(JDK1.8 使用了volatile + CAS + synchronized)

  • LinkedHashMap
    是HashMap的一个子类。
    有序存储,保存了记录的插入顺序。
    非线程安全

  • TreeMap
    实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器。
    在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。
    因此key不可以为null,value则不受影响。
    非线程安全

对于上述四种Map类型的类,要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化,Map对象很可能就定位不到映射的位置了。

类继承关系如下图所示:


HashMap 源码理解与面试,第1张
Map Class.png

存储结构

使用 数组 + 链表 + 红黑树 的方式存储键值对。

JDK1.7 及之前,HashMap是 数组 + 链表 实现的存储结构。
JDK1.8 添加了红黑树部分。众所周知,当链表的长度特别长的时候,查询效率将直线下降,查询的时间复杂度为 O(n),因此,JDK1.8 把它设计为达到一个特定的阈值 (链表长度> 8 且 数组大小 >= 64) 之后,就将链表转化为红黑树。由于红黑树,是一个自平衡的二叉搜索树,因此可以使查询的时间复杂度降为 O(logn)。

HashMap 源码理解与面试,第2张
HashMap.png

HashMap 使用哈希表来存储,并且用链地址法解决冲突。

哈希表为解决冲突,可以采用开放地址法链地址法等来解决问题,HashMap采用了链地址法。
链地址法,简单来说,就是数组加链表的结合。在每个数组元素上都一个链表结构,当数据被Hash后,得到数组下标,把数据放在对应下标元素的链表上。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    // 哈希桶数组,放所有Node节点
    transient Node<K,V>[] table;

    // 普通单向链表节点类
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash; // key的hash值,用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next; // 链表的下一个node

        Node(int hash, K key, V value, Node<K,V> next) {... }
        public final K getKey(){ ... }
        public final V getValue() { ... }
        public final String toString() { ... }
        public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); }
        public final V setValue(V newValue) { ... }
        public final boolean equals(Object o) { ... }
    }

    // 红黑树节点
    static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        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) { ... }
        final TreeNode<K,V> root() { ... }
        static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { ... }
        final TreeNode<K,V> find(int h, Object k, Class<?> kc) { ... }
        final TreeNode<K,V> getTreeNode(int h, Object k) { ... }
        static int tieBreakOrder(Object a, Object b) { ... }
        final void treeify(Node<K,V>[] tab) { ... }
        final Node<K,V> untreeify(HashMap<K,V> map) { ... }
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { ... }
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) { ... }
        final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { ... }
        static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { ... }
        static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) { ... }
        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { ... }
        static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) { ... }
        static <K,V> boolean checkInvariants(TreeNode<K,V> t) { ... }
    }
}

HashMap的容量是多少

  • 默认容量是 16 ( 1 << 4 )
  • 最大容量是 2^30 ( 1 << 30 )
  • 可通过构造方法传入初始化容量,HashMap会通过计算完成最终容量的计算,HashMap的容量一定是n次幂
  • HashMap会在容量不足的时候自行 resize 进行扩容,每次扩容2倍。
    // 默认的初始化容量为16,必须是2的n次幂
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    // 最大容量为 2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;

    // 默认的加载因子0.75,乘以数组容量得到的值,用来表示元素个数达到多少时,需要扩容。
    // 为什么设置 0.75 这个值呢,简单来说就是时间和空间的权衡。
    // 若小于0.75如0.5,则数组长度达到一半大小就需要扩容,空间使用率大大降低,
    // 若大于0.75如0.8,则会增大hash冲突的概率,影响查询效率。
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // map中的实际键值对个数,即数组中元素个数
    transient int size;

    // 每次结构改变时,都会自增,fail-fast机制,这是一种错误检测机制。
    // 当迭代集合的时候,如果结构发生改变,则会发生 fail-fast,抛出异常。
    transient int modCount;

    // 数组扩容阈值
    // 要调整大小的下一个大小值(容量*加载因子)。
    int threshold;

    // 加载因子
    final float loadFactor;

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

    public HashMap(Map<extends K, extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

    // 可指定期望的初始容量。
    // 为什么是期望
    // 因为容量要求一定是2的n次幂,如果传入的不符合,后面会计算使容量确定为仅大于该值的最小2次幂数
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    // 可指定期望容量和加载因子,不建议自己手动指定非0.75的加载因子
    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 方法保证容量总是2的n次幂。
        // 这里没有将值直接赋值给 capacity,而是赋值给扩容阈值threshold 
        // threshold 是要调整大小的下一个容量阈值
        // 因为扩容的存在,capacity是会变化的,
        // 所以,容器扩展到指定大小的任务交给resize方法即可。
        // 这里只要指定下一次所需要扩容的容量大小,
        // 在put第一次初始化哈希桶的时候,直接通过resize方法扩展至指定容量大小。
        this.threshold = tableSizeFor(initialCapacity);

        // 思考 ? 
        // 这里的 threshold 为什么没有考虑加载因子。 详见resize
    }

HashMap的容量如何保证一定是2的n次幂

  • 在构造方法中通过 tableSizeFor 方法进行运算。
    tableSizeFor 方法中采用了将原始数值进行无符号右移(>>>),再进行2进制按位或运算,这样等价于高位1不断右移,补充至末尾后,最后进行+1的操作,完成比原始数值大的最接近的2的次幂数计算。
  • 扩容时,每次扩容都是扩容 2倍
  • 这里选择了无符号右移(>>>)的操作,想想为什么不用有符号右移(>>)
    从源码可见,虽然调用 tableSizeFor 方法之前都有控制传入的参数cap要求大于0,
    但是从源码return来看,是有考虑cap出现小于等于0的情况。如果n出现负数,则有符号和无符号的右移操作将出现极大的差别。有符号计算高位补1,无符号补0。
    // 最大容量为 2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 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;
    }

我们以随意选一个数值运算来看下具体变化。

// 初始数值  37  ,仅以后八位示例
0010 0101   cap = 37
-----------
0010 0100   n = cap - 1 = 36
0001 0010   n >>> 1
-----------
0011 0110   按位或 |= 
0000 1001   n >>> 2
-----------
0011 1111   按位或 |= 

0011 1111   之后 n >>> 4, n >>> 8, n >>> 16 按位或的结果都是0011 1111

判断是否超过最大值,是则返回最大值 2^30。不是则返回n+1
0100 0000    未超过 , n + 1 = 2^6 = 64

  • 之前有人问
    这里return的时候判断了n < 0 则返回1,因为默认容量为 16。所以此处是否可以直接返回默认值
    DEFAULT_INITIAL_CAPACITY 。
return (n < 0) DEFAULT_INITIAL_CAPACITY  : (n >= MAXIMUM_CAPACITY) MAXIMUM_CAPACITY : n + 1;

不行。因为是可以设置容量小于16的,比如1,2,4,8。默认容量为16并不代表最小容量为16。不要把默认值和最小值搞混了。虽然,不建议设置这么小的值,会导致频繁扩容。

关于扩容 resize

刚才说容量的时候有提到扩容,扩容就是重新计算哈希桶的容量。
当然,Java中数组是无法自动扩容的。
HashMap 使用了一个新的哈希桶数组代替已有的容量小的数组,并将已存储的值重新计算位置放入新的哈希桶中。

  • 扩容时首先会判断旧哈希桶的容量
    1.如果旧容量 大于0,说明可以直接扩容,这里先判断是否超过最大值,没有的话直接进行2倍扩容,扩容阈值也直接扩大2倍。
    2.如果旧容量 不大于0 ,会先判断扩容阈值 threshold ,如果 threshold > 0 ,表示构造函数进行了容量设置,这里会将 threshold 直接给赋值给哈希容量。
    这里的 threshold 比较特殊,在构造函数中,是直接将期望容量赋值给 threshold 的,所以这里的 threshold 并未与加载因子挂钩,仅作为期望容量的一个初始载体,赋值给容量之后,就会进行加载因子的计算,得到准确的 threshold 进行扩容的阈值控制。
    3.如果 旧容量不大于0,扩容阈值也不大于0。完全未初始化,也没有期望容量的设置,这里直接取了默认容量16和默认阈值 16*0.72 = 12。

  • 确认好初始化容量和扩容阈值之后,就会生成新的哈希桶了

  • 然后判断旧的哈希桶是否有值,没有值的话直接扩容完毕。有值的话需要将值迁移至新的哈希桶中。
    遍历哈希桶,取出桶中的Node,顺手将旧桶指引置空,判断是链表还是红黑树,然后做不同操作。
    1.单个数据
    直接计算 index = h.hash & (newCap - 1),然后放入新的哈希桶中。
    2.红黑树结构
    拆解红黑树,通过 e.hash & oldCap 是否为0 来判断其中数据是否需要移位。需要位移则移入高位树中,必要时(数据量 <= 6)进行反树化,退化为链表结构。
    3.链表结构
    遍历链表,通过 e.hash & oldCap 是否为0 来判断其中数据是否需要移位。需要位移则通过尾插法插入高位链表中。JDK1.8 使用的尾插法可以避免 JDK1.7 中链表头插法形成环状结构导致死循环

  • 不论链表还是红黑树,均使用 index + oldCap 的方式确认高位index
    为什么这么用。我们看完源码稍后举例细说。

    // 默认的加载因子0.75,乘以数组容量得到的值,用来表示元素个数达到多少时,需要扩容。
    // 为什么设置 0.75 这个值呢,简单来说就是时间和空间的权衡。
    // 若小于0.75如0.5,则数组长度达到一半大小就需要扩容,空间使用率大大降低,
    // 若大于0.75如0.8,则会增大hash冲突的概率,影响查询效率。
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 数组扩容阈值
    // 要调整大小的下一个大小值(容量*加载因子)。
    int threshold;

    // 加载因子
    final float loadFactor;

    final Node<K,V>[] resize() {
        // 旧数组
        Node<K,V>[] oldTab = table;
        // 旧数组的容量
        int oldCap = (oldTab == null) 0 : oldTab.length;
        // 旧的扩容阈值
        int oldThr = threshold;
        // 新的容量及扩容阈值
        int newCap, newThr = 0;

        // 1.当旧数组的容量大于0时,直接扩容。
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 新容量为旧容量的2倍   newCap = oldCap << 1
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 扩容阈值也扩大两倍
                newThr = oldThr << 1; // double threshold 
        }

        // 2. 反之小于0 说明还未进行过初始化 。
        // 但是oldThr > 0 说明设置了期望的初始容量  =>  public HashMap(int initialCapacity)
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults

            // 3. 均小于0,说明均未初始化,设置默认值即可。
            newCap = DEFAULT_INITIAL_CAPACITY;  // 1 << 4  aka 16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 16 * 0.75
        }

        // 来自于上面的第2中情景,需要重新计算正确的扩容阈值 
        // 结合上方的情况2 和 public HashMap(int initialCapacity, float loadFactor)方法理解
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }

        // 赋予 threshold 正确的值,表示数组下次需要扩容的阈值
        threshold = newThr;

        // 创建扩容后的哈希桶数组
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;

        // 如果原来的数组不为空,那么我们就需要把原来哈希桶数组中的元素重新分配到新的数组中
        // 如果是空,则是第一次调用resize初始化数组,因此也就不需要重新分配元素
        if (oldTab != null) {
            // 遍历旧数组
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;

                // 取得桶中的链表 Node e;
                if ((e = oldTab[j]) != null) {
                    // 将旧数组中的引用置空,释放引用。 
                    oldTab[j] = null;

                    // 1. 如果当前元素的下一个元素为空,则说明此处只有一个元素
                    // 则直接用它的hash()值和新数组的容量取模就可以了,得到新的下标位置。
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        // 2. 如果是红黑树结构,则拆分红黑树,必要情况下可能退化为链表 
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        // 3. 当前是链表结构,判断是否需要移动链表元素的位置

                        // 区别于JDK1.7,这里使用尾插法

                        // loHead loTail  下标位置不变(低位)的链表头尾节点
                        Node<K,V> loHead = null, loTail = null;

                        // hiHead hiTail  需要移动位置(高位)的链表头尾节点
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;

                            // 这里不需要重新在计算hash值,
                            // 将原有 hash 和 oldCap 与运算为 0 ,表示位置不变。
                            // 详见 hash() 方法分析 结合 resize ,put的下标计算
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                // 需要移动到新位置的Node
                                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;

                            // 新位置下标为 旧位置索引 + oldCap 
                            // 详见 hash() 方法 结合 resize 和 put 方法。
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

为什么可以通过 e.hash & oldCap 是否为0 判断是否移位

首先,我们从 putVal() 方法中可以看到,哈希桶计算 index 的时候使用的
tab[i = (n - 1) & hash],而 n = tab.length
所以
i = (tab.length - 1) & hash
其实相当于对哈希桶长度取模操作,但是二进制算法效率更高。

例:

// 假设 n = 16 , hash 为 14

14 % 16 = 14

14  & (16 - 1)= 14

0000 1110   14
0000 1111   &  15
------------------
0000 1110   14

===================
// 假设 n = 16 , hash 为 18

18 % 16 = 2

18  & (16 - 1)= 2

0001 0010   18
0000 1111   &  15
------------------
0000 0010   2

确认完这个逻辑后,我们从 resize 方法了解到,HashMap 每次扩容都是2倍扩容。从二进制考虑,就是tabLength多了1位。在 hash 不变的情况下,低位计算不会变化,那么只要考虑只计算这多出来的1位高位就行。

  • 如果计算结果等于0,代表与之前的取模运算结果一致。
  • 如果等于1,则表示取模结果比之前低位的基础上,多了高位的1,而这一位高位的数值大小,正好是oldCap。
// 假设 n = 16 , hash 为 18

18 % 16 = 2

18  & (16 - 1)= 2

0001 0010   18
0000 1111   &  15
------------------
0000 0010   2

扩容后。 hash不变,n = 16 * 2 = 32
18 % 32 = 18

18  & (32 - 1)= 18

0001 | 0010   18
0001 | 1111   &  31 
------------------
0001 | 0010   18 = 2 + 16 = index + oldCap

计算结果低位未变,新增高位计算结果不为 0
需要移位,且移位大小为 index + oldCap

HashMap 是如何计算 hash 值的

  • 如果key == null,直接返回 0
    由此可见,HashMap 是支持 key == null,这种情况的。
    并且由于hash为0,所以一定存在于哈希桶的第 0 位的桶内 (index = hash & ( tab.length - 1))

  • 取得key的hashCode,并进行无符号右移16位,再进行异或操作。
    hashCode是一个32位的数值,右移16可以让高位影响低位,以减少哈希碰撞。

这个方法又被称作:扰动函数

    static final int hash(Object key) {
        int h;
        // h = key.hashCode()  取hashCode值
        // h ^ (h >>> 16)  高位参与运算
        return (key == null) 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

为什么这样操作可以减少哈希碰撞?
我们之前的内容也了解到了,哈希桶的插入位置是类似取模的操作。其实就是只有hash值的后n位有效,n是由哈希桶长度决定的。大部分时候,哈希桶的长度都是比较小的,可能只有涉及到4到6位左右的计算。
那么,如果两个hash值只要低位相同就会发生碰撞,哪怕高位不同也不行。而扰动函数进行高位右移与低位异或,等于将高位特征参与到低位中去,就能避免部分hash值低位相同,高位不同的碰撞问题。
在JDK1.7中,扰动函数是经过多次右移操作的,但是JDK1.8考虑到效率问题,多次右移并未有较为显著的提升效果,故一次右移已满足需求,更多考虑到效率及性能的一个交换。

如果我讲的不够明白,大家可以参考文章尾部的几篇链接,有大佬进行图文并茂的讲解。

简述数据插入 hashMap.put(K,V);

说了这么多,终于来到了这个环节,很多人在博客中可能喜欢先讲这部分,再补充其它点。但就我个人而言,可能上面的内容更加吸引我吧~ 哈哈。

  • 先通过扰动函数处理和计算key的hash值,并作为最终hash值使用。
  • 判断当前哈希桶是否初始化,没有的话,就通过调用 resize() 方法进行初始化。我们刚才讲 resize() 的时候有说过。
  • 通过 (n - 1) & hash 确认所在的哈希桶位置
  • 如果当前位置节点为空,则直接存入。
  • 不为空的话,判断首节点的key和hash是否相同
    相同则替换
    不同就向下找。
  • 确认向下是链表结构还是红黑树结构
    红黑树就插入红黑树
    链表就插入
  • 链表使用尾插法插入
    插入过程中
    如果有同值的key,就替换
    没有,则会遍历至链表尾部,在尾部插入新值,然后检查当前链表是否达到树化阈值 (8),达到则转化为红黑树结构。
    但是最终是否转化为红黑树,还要看当前容量是否达到最小树化容量阈值 (64),只有达到了才会真正转为红黑树,否则只会进行 resize() 扩容。
  • 最后,如果是插入新值,则需判断当前容量是否需要再次扩容。
  • 完毕。

下面请结合源码再过一遍。

    // 当链表长度超过阈值8 就会尝试转化为红黑树
    static final int TREEIFY_THRESHOLD = 8;

    // 链表转化为红黑树,除了有上面阈值的限制
    // 还需要数组容量至少达到64,才会真正树化,否则只会扩容
    static final int MIN_TREEIFY_CAPACITY = 64;

    // 通过扰动函数计算key的 hash 值,然后进行putVal
    // 如果当前 key 已经有 value ,则替换并返回被替换的value ,如果没有,则返回 null。
    public V put(K key, V value) {
        // 先调用了 hash(key)
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key   经过扰动函数处理过的hash值
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value  如果是true,则不替换value
     * @param evict if false, the table is in creation mode. 如果是false,则表示处于创建模式。
     * @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;

        // 判断哈希桶是否为空,如果是空,通过resize()方法进行初次初始化。
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

        // 通过 (n - 1) & hash 确认哈希桶中的位置
        // 如果当前位置节点为空,则直接存入K,V创建Node存入。
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            // 当前节点有值,分成三种情况分析
            Node<K,V> e; K k;

            // 1. 比较首节点的hash值,key值,如果相同,则替换
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                // 2. 当前节点为红黑树,将值加入红黑树中
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 3. 当前结构为链表,使用尾插法将值添加至链表尾部
                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 减一是因此处从首节点之后开始便利
                            // 插入之后,链表长度达到树化阈值 8,尝试转化为红黑树结构
                            // treeifyBin() 中会判断容量是否达到 MIN_TREEIFY_CAPACITY (64)
                            // 达到了才会真正树化,否则只会扩容
                            treeifyBin(tab, hash);
                        break;
                    }

                    // 遍历中,找到了相同的Key,跳出循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }

            // e 不为空,表示当前HashMap已经存在这个key,判断是否需要替换
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                     // onlyIfAbsent 为 false,替换旧值,并返回被替换的旧值
                    e.value = value;

                // 空实现,在LinkedHashMap中有实现,用于LinkedHashMap的排序问题
                afterNodeAccess(e);
                return oldValue;
            }
        }

        // fail - fast 机制
        ++modCount;

        // 插入完毕,size + 1
        // 判断插入后的大小是否达到扩容阈值,达到则进行扩容
        if (++size > threshold)
            resize();

        // 空实现
        afterNodeInsertion(evict);
        return null;
    }

树化和反树化

  • 树化
    只有在插入的时候会触发,即插入数据后,链表达到树化阈值 (8) 之后尝试进行树化操作。
    但是在 treeifyBin() 方法中还会判断当前容量是否达到 64,只有达到才会真正进行树化,否则只会进行 resize() 扩容。
    // 当链表长度超过阈值8 就会尝试转化为红黑树
    static final int TREEIFY_THRESHOLD = 8;

    // 链表转化为红黑树,除了有上面阈值的限制
    // 还需要数组容量至少达到64,才会真正树化,否则只会扩容
    static final int MIN_TREEIFY_CAPACITY = 64;

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        ...
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 减一是因此处从首节点之后开始遍历
            // 插入之后,链表长度达到树化阈值 8,尝试转化为红黑树结构
            // treeifyBin() 中会判断容量是否达到 MIN_TREEIFY_CAPACITY (64)
            // 达到了才会真正树化,否则只会扩容
            treeifyBin(tab, hash);
        ...
    }

    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() 初始化扩容
            resize();

        // 确认需要转化的节点不为 null
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            // 开始转化为红黑树结构
            TreeNode<K,V> hd = null, tl = null;
            do {
                // 链表节点Node 转化为 红黑树节点TreeNode
                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);
        }
    }

  • 反树化
    有树化就有反树化。

反树化主要发生在两个过程中

  1. resize() 扩容时
    我们之前在说 resize() 扩容的时候,如果遇到需要移动位置的元素,并且是红黑树结构的话。
    就会拆分红黑树 split() ;
    当红黑树的拆分的过程中,容量退化到 UNTREEIFY_THRESHOLD ( 6 ) 之后,红黑树就会退化为链表。
  2. remove操作
    当从 HashMap 中移除数据时也会触发。
    但是这里有点小特殊,我们从源码中可以看到,这里并没有对 UNTREEIFY_THRESHOLD 的判断,
    只在红黑树 root == null || root.right == null || (rl = root.left) == null || rl.left == null) 的时候触发退化。
    大概就是深度小于2的时候。
    根据红黑树的结构特性,大概发生于 元素 2 到 6 个之间。
    源码中也有对应的注释说明。

If the current tree appears to have too few nodes, the bin is converted back to a plain bin. (The test triggers somewhere between 2 and 6 nodes, depending on tree structure).

    // 如果红黑树种的元素减少至 6 个时,退化为链表
    static final int UNTREEIFY_THRESHOLD = 6;

    final Node<K,V>[] resize() {
        ...
                    else if (e instanceof TreeNode)
                        // 2. 如果是红黑树结构,则拆分红黑树,必要情况下可能退化为链表 
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        ...
    }

    static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> {

        ...
       final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
        ...
                if (hc <= UNTREEIFY_THRESHOLD)
                    // 拆分过程中元素减少到6个,触发反树化,退化为链表
                    tab[index + bit] = hiHead.untreeify(map);
        ...
        }

        /**
         * Removes the given node, that must be present before this call.
         * This is messier than typical red-black deletion code because we
         * cannot swap the contents of an interior node with a leaf
         * successor that is pinned by "next" pointers that are accessible
         * independently during traversal. So instead we swap the tree
         * linkages. If the current tree appears to have too few nodes,
         * the bin is converted back to a plain bin. (The test triggers
         * somewhere between 2 and 6 nodes, depending on tree structure).
         */
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) {
        ...
            if (root == null || root.right == null ||
                (rl = root.left) == null || rl.left == null) {
                // 红黑树太小了,退化为链表,大概发生于 2 到 6 nodes
                tab[index] = first.untreeify(map);  // too small
                return;
            }
        ...
        }

        final Node<K,V> untreeify(HashMap<K,V> map) {
            Node<K,V> hd = null, tl = null;
            for (Node<K,V> q = this; q != null; q = q.next) {
                Node<K,V> p = map.replacementNode(q, null);
                if (tl == null)
                    hd = p;
                else
                    tl.next = p;
                tl = p;
            }
            return hd;
        }

        ...

数据的查询获取 hashMap.get(K)

其实前面说了那么多,所有的设计都是为最终 get 服务的。

然而到 get(K) 方法反而简单了很多。
内心:废话,不简单,怎么做到快狠准!

哈哈哈,咱们接着聊

  • 还是通过扰动函数 hash(key) 拿到那个要找的hash
  • 如果桶是空的,或者通过((tab.length - 1) & hash)确认要找的位置上是空的,别说了,没找到,就是空!
  • 如果不是空,老规矩,先瞅瞅这个首节点的hash和key对的上么,对上了就返回。
  • 首节点不是,就需要确认下有没有下个节点了。
  • 如果有下个节点,看看是红黑树还是链表。
  • 然后完了。链表就找链表,红黑树就找红黑树。各回各家,各找各妈。
  • 哦,都没找到。那就是没有呗。null!

咱们在跟着源码简单过一遍


    public V get(Object key) {
        Node<K,V> e;
        // 通过扰动函数 hash(key) 拿到那个要找的hash
        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;

        // 哈希桶有值,并且 (n - 1) & hash 位置上也有值,就进去
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {

            // 先瞅瞅首节点呗。你看,注释都说always了。
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                // 就是它!返回
                return first;

            // 首节点不是,接着往下找
            if ((e = first.next) != null) {
                // next节点存在,分两种情况

                // 1. 当前桶里是红黑树
                if (first instanceof TreeNode)
                    // 从红黑树里取
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);

                // 2. 当前桶里是个链表
                do {
                    // 遍历链表
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }

        // 啥都没找着,返回 null
        return null;
    }

参考文献

文中有大量的参考内容,大佬写的是真的好,有部分是我结合自己的理解,做了不少改动之处。
大家可以尝试阅读以下原创,加深理解,或者指正我理解错误的地方。
欢迎指导和交流。

https://docs.oracle.com/javase/8/docs/api/
Java 8系列之重新认识HashMap <美团技术团队>
面试官再问你 HashMap 底层原理,就把这篇文章甩给他看
一个HashMap跟面试官扯了半个小时
知乎 - 解读HashMap中hash算法的巧妙设计
知乎 - 胖君 - HashMap 的 hash 方法原理是什么
An introduction to optimising a hashing strategy


https://www.xamrdz.com/backend/35a1925169.html

相关文章: