【JDK源码】HashMap源码分析（附常见面试题）

布满荆棘的人生 2023-10-01 11:38 9阅读 0赞

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

## HashMap源码分析（附面试题） ##

### 1.什么是哈希？ ###

> 在分析HashMap之前，我们先来了解什么是哈希？

概念：Hash也称散列、哈希，对应的英文都是Hash。基本原理就是把**任意长度**的输入，通过Hash算法变成**固定长度**的输出这个映射的规则就是对应的**Hash算法**，而原始数据映射后的**二进制串**就是哈希值。

Hash的特点:

1.  从hash值不可以**反向推导**出原始的数据
2.  输入数据的**微小变化**会得到完全不同的hash值，相同的数据会得到相同的
3.  哈希算法的执行效率要**高效**，长的文本也能快速地计算出哈希值
4.  hash算法的**冲突**概率要小

由于hash的原理是将**输入空间**的值映射成**hash空间**内，而hash值的空间远小于输入的空间。根据**抽屉原理**，一定会存在不同的输入被映射成相同输出的情况。

> 抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。  
> 这一现象就是我们所说的“抽屉原理”。

### 2.HashMap的继承体系 ###

HashMap采用`key/value`存储结构，每个key对应唯一的value，查询和修改的速度都很快，能达到`O(1)`的平均时间复杂度。它是**非线程安全的**，且**不保证元素存储的顺序**。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8rNFqNRP-1641090759949)(HashMap源码分析（附常见面试题）.assets/image-20211231093118109.png)\]][img-8rNFqNRP-1641090759949_HashMap_.assets_image-20211231093118109.png]

从继承体系可以看出：

*  HashMap 实现了`Cloneable`接口，可以被克隆。
 *  HashMap 实现了`Serializable`接口，属于标记性接口，HashMap 对象可以被序列化和反序列化。
 *  HashMap 继承了`AbstractMap`，父类提供了 Map 实现接口，具有Map的所有功能，以最大限度地减少实现此接口所需的工作。

### 3.底层存储结构 ###

*  1.7 数组 + 链表
 *  1.8 数组 + （链表 | 红黑树）

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TONIod9y-1641090759953)(HashMap源码分析（附常见面试题）.assets/image-20211128085755408.png)\]][img-TONIod9y-1641090759953_HashMap_.assets_image-20211128085755408.png]

在Java中，HashMap的实现采用了（**数组 + 链表 + 红黑树**）的复杂结构，数组的一个元素又称作**桶**。

在添加元素时，会根据hash值算出元素在数组中的位置，如果该位置没有元素，则直接把元素放置在此处，如果该位置有元素了，则把元素以链表的形式放置在链表的尾部。

当一个链表的元素个数达到一定的数量（且数组的长度达到一定的长度）后，则把链表转化为红黑树，从而提高效率。

数组的查询效率为`O(1)`，链表的查询效率是`O(k)`，红黑树的查询效率是`O(log k)`，k为桶中的元素个数，所以当元素数量非常多的时候，转化为红黑树能极大地提高效率。

**树化需要同时满足两个条件：**

1.  链表长度`大于8`，并不是大于等于8
2.  数组长度`达到64`。如果数组长度不够64，会优先进行`resize()`扩容。

### 4.内部类 ###

**Node内部类**

`Node`是HashMap的静态内部类，实现了`Map.Entry<K,V>`接口。我们存储的键值对都是以Node的形式存储在map中的。其重要属性如下：

static class Node<K,V> implements Map.Entry<K,V> {
        
        //基于key的hashValue经过hash扰动后得到的，是hash分布更均匀
        final int hash;
        //put进来的key
        final K key;
        //对应的value
        V value;
        //指向链表中的下一个Node
        Node<K,V> next;
        ...
    }

### 5.HashMap核心属性分析 ###

/**
         * HashMap的初始化容量（必须是 2 的 n 次幂）默认的初始容量为16
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /**
         * table最大长度
         */
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /**
         * 默认的负载因子
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
        /**
         * 树化阈值：当一个桶中的元素个数大于8时进行树化（同时需要数组长度达到64）
         */
        static final int TREEIFY_THRESHOLD = 8;
    
        /**
         * 树降级为链表的阈值：当一个桶中的元素个数小于等于6时把树转化为链表
         */
        static final int UNTREEIFY_THRESHOLD = 6;
        /**
         * Node数组，又叫作桶（bucket）
         */
        transient Node<K,V>[] table;
    
        /**
         * 作为entrySet()的缓存
         */
        transient Set<Map.Entry<K,V>> entrySet;
    
        /**
         * 当前哈希表中元素的个数
         */
        transient int size;
    
        /**
         * 当前哈希表结构修改次数
         */
        transient int modCount;
    
        /**
         * 扩容阈值，当你的哈希表中的元素超过阈值时，触发扩容（threshold = capacity * loadFactor）
         */
        int threshold;
    
        /**
         * 负载因子（默认0.75）
         */
        final float loadFactor;

从属性源码我们可以得到几个信息：

1.  **容量**：容量为数组的长度，亦即桶的个数，默认为`16`，最大为`2的30次方`，当容量达到64时才可以树化。
2.  **装载因子**：用来计算容量达到多少时才进行扩容，默认装载因子为`0.75`。
3.  **树化**：当容量达到`64`且链表的长度大于`8`时进行树化，当链表的长度小于`6`时反树化。

### 6.HashMap构造方法 ###

**HashMap()**

构造一个空的HashMap，默认初始容量（16）和默认负载因子（0.75）

public HashMap() {
        
       // 将默认的负载因子0.75赋值给loadFactor，并没有创建数组
       this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }

**HashMap(int initialCapacity)**

构造指定初始容量`initialCapacity`的HashMap，其实也是调用`HashMap(int initialCapacity，float loadFactor)`，默认的负载因子

/**
    * 指定初始容量大小的构造函数
    * @param initialCapacity
    */
    public HashMap(int initialCapacity) {
        
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

**HashMap(int initialCapacity，float loadFactor)**

构造一个具有指定的初始容量`initialCapacity`和负载因子`loadFactor`的 HashMap

/*
    指定“容量大小”和“负载因子”的构造函数
    initialCapacity：指定的容量
    loadFactor:指定的负载因子
    */
    public HashMap(int initialCapacity, float loadFactor) {
        
        //判断初始容量initialCapacity是否小于0
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        //判断初始容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //判断负载因子loadFactor是否<=0或者是否是一个非数值
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        //将指定的负载因子loadFactor赋值给HashMap成员变量的负载因子
        this.loadFactor = loadFactor;
        //给扩容阈值赋值（只能是2的次方）
        this.threshold = tableSizeFor(initialCapacity);
    }
    	 /**
         * 作用：返回比指定cap容量大的最小2的n次幂数
         * 栗子：cap=10
         * n=10-1=9
         * 0b1001 | 0b0100 = 0b1101
         * 0b1101 | 0b0011 = 0b1111
         * 0b1111 | 0b0000 = 0b1111
         * 0b1111 | 0b0000 = 0b1111
         * 0b1111 | 0b0000 = 0b1111
         * ob1111->15
         * 15>0 -> return 15+1(16)
         * 模式：0001 1101 1100 => 0001 1111 1111 +1 => 0010 0000 0000
         */
    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;
    }

### 7.put方法 ###

put方法的整体流程：

1.  计算key的hash值
2.  如果桶（数组）数量为0，则初始化桶
3.  如果key所在的桶没有元素，则直接插入
4.  如果key所在的桶中的第一个元素的key与待插入的key相同，说明找到了元素，转后续流程（9）处理
5.  如果第一个元素是树节点，则调用树节点的putTreeVal()寻找元素或插入树节点
6.  如果不是以上三种情况，则遍历桶对应的链表查找key是否存在于链表中
7.  如果找到了对应key的元素，则转后续流程（9）处理
8.  如果没找到对应key的元素，则在链表最后插入一个新节点并判断是否需要树化
9.  如果找到了对应key的元素，则判断是否需要替换旧值，并直接返回旧值
10. 如果插入了元素，则数量加1并判断是否需要扩容

public V put(K key, V value) {
        
    	 // 调用hash(key)计算出key的hash值
        return putVal(hash(key), key, value, false, true);
    }

/**
         * 作用：让key的hash值的高16位参与运算
         * @param key
         * @return
         */
    static final int hash(Object key) {
        
        int h;
        //key==null直接返回0
        //1、否则调用key的hashCode()方法计算出key的哈希值然后赋值给h,
        //2、后与h无符号右移16位后的二进制进行按位异或得到最后的hash值,
        //3、这样做是为了使计算出的hash更分散，让高16位可以参与（低16位具有高16位的特征）
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

/**
         *
         * @param hash  key的hash值
         * @param key   原始key
         * @param value 要存放的值
         * @param onlyIfAbsent  如果 true 代表不更改现有的值，也就是说如果存在key就不改变，一般传入false
         * @param evict  如果为false表示 table 为创建状态
         * @return
         */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        
        //tab：引用当前hashMap的散列表
        //p：表示当前散列表的元素
        //n：表示散列表数组的长度
        //i：表示路由寻址结果
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 如果桶的数量为0，则初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            // 调用resize()初始化
            n = (tab = resize()).length;
        //最简单的一种情况：寻址找到的桶位null，直接将创建一个新结点放入桶中
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        
            //e：不为null的话，找到一个与当前要插入的key-value一致的key元素
            //k：临时的一个key
            Node<K,V> e; K k;
            //表示桶位中的该元素，与你当前插入的元素key完全一致，表示后续要进行替换操作
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                // 如果第一个元素是树节点，则调用树节点的putTreeVal插入元素
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
        
    			// 遍历这个桶对应的链表，binCount用于存储链表中元素的个数
                for (int binCount = 0; ; ++binCount) {
        
                    //条件成立的话，说明迭代到最后一个元素了，也没找到一个与你插入的key一致的node
                    //说明需要加入到当前链表的尾部
                    if ((e = p.next) == null) {
        
                        p.next = newNode(hash, key, value, null);
                        //条件成立的话，说明当前链表的长度达到树化的标准了，需要进行树化
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            //树化操作
                            treeifyBin(tab, hash);
                        break;
                    }
                    //说明条件成立的化，找到了相同key的node元素，进行替换操作
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //e不等于null，说明找到了一个与你插入元素key完全一致的数据，需要进行替换
            if (e != null) {
         // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 在节点被访问后做点什么事，在LinkedHashMap中用到
                afterNodeAccess(e);
                // 返回旧值
                return oldValue;
            }
        }
        //散列表结果修改次数加一，替换Node元素的value不计数
        ++modCount;
        //插入新元素，size自增
        //如果大于扩容阈值，扩容
        if (++size > threshold)
            resize();
        // 在节点插入后做点什么事，在LinkedHashMap中用到
        afterNodeInsertion(evict);
        // 没找到元素返回null
        return null;
    }

### 8.resize扩容方法 ###

整个扩容流程：

1.  如果使用是默认构造方法，则第一次插入元素时初始化为默认值，容量为16，扩容门槛为12
2.  如果使用的是非默认构造方法，则第一次插入元素时初始化容量等于扩容门槛，扩容门槛在构造方法里等于传入容量向上最近的2的n次方
3.  **如果旧容量大于0，则新容量等于旧容量的2倍，但不超过最大容量2的30次方，新扩容门槛为旧扩容门槛的2倍**
4.  创建一个新容量的桶
5.  搬移元素，原链表分化成两个链表，低位链表存储在原来桶的位置，高位链表搬移到原来桶的位置加旧容量的位置

/**
         * 为什么需要扩容？
         * 为了解决hash冲突导致的链化影响查询效率的问题，扩容会缓解该问题
         *
         * @return
         */
    final Node<K, V>[] resize() {
        
        //引用扩容前的哈希表
        Node<K, V>[] oldTab = table;
        //表示扩容之前的table数组的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //扩容之前的扩容阈值
        int oldThr = threshold;
        //newCap：扩容之后table数组的大小
        //newThr：扩容之后，下次在触发扩容的条件
        int newCap, newThr = 0;
        //条件入如果成立：说明hashMap中的散列表已经初始化过了，是一次正常扩容
        if (oldCap > 0) {
        
            //如果旧容量达到最大容量，则不再进行扩容
            if (oldCap >= MAXIMUM_CAPACITY) {
        
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 如果旧容量的两倍小于最大容量并且旧容量大于默认初始容量（16），则容量扩大为两部，扩容门槛也扩大为两倍
            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
            //使用非默认构造方法创建的map，第一次插入元素会走到这里
            //1.new HashMap(initCap,loadFactor);
            //2.new HashMap(initCap);
            //3.new HashMap(map); map有数据
            // 如果旧容量为0且旧扩容门槛大于0，则把新容量赋值为旧门槛
            newCap = oldThr;
        else {
        
            //使用默认构造方法创建的map，第一次插入元素会走这里
            newCap = DEFAULT_INITIAL_CAPACITY;
            //如果旧容量旧扩容门槛都是0，说明还未初始化过，则初始化容量为默认容量，扩容门槛为默认容量*默认装载因子
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
    
        if (newThr == 0) {
        
            //如果旧容量旧扩容门槛都是0，说明还未初始化过，则初始化容量为默认容量，扩容门槛为默认容量*默认装载因子
            float ft = (float) newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                      (int) ft : Integer.MAX_VALUE);
        }
        //赋值扩容门槛为新门槛
        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节点
                Node<K, V> e;
                //如果当前桶中第一个元素不为空，说明当前桶位有数据，赋值给e
                if ((e = oldTab[j]) != null) {
        
                    //清空旧桶，方便JVM GC时回收内存
                    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 {
        
                        //第三种情况：链表情况
                        // 比如，假如原来容量为4，3、7、11、15这四个元素都在三号桶中
                        // 现在扩容到8，则3和11还是在三号桶，7和15要搬移到七号桶中去
                        // 也就是分化成了两个链表
                        //低位链表：存放在扩容之后下标位置与当前数组下标位置一致
                        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的元素放在低位链表中
                            //比如3&4==0
                            if ((e.hash & oldCap) == 0) {
        
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            } else {
        
                                // (e.hash & oldCap) != 0的元素放在高位链表中
                                //比如，7&4！=0
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 遍历完成分化成两个链表了
                        // 低位链表在新桶中的位置与旧桶一样（即3和11还在三号桶中）
                        if (loTail != null) {
        
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 高位链表在新桶中的位置正好是原来的位置加上旧容量（即7和15搬移到七号桶了）
                        if (hiTail != null) {
        
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

### 9.get方法 ###

public V get(Object key) {
        
        Node<K, V> e;
        //这里hash(key)是因为put的时候hash了，这里取自然也需要hash
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    final Node<K, V> getNode(int hash, Object key) {
        
        //引用当前hashMap的散列表
        Node<K, V>[] tab;
        //first:桶位中的头元素
        //e:临时node元素
        Node<K, V> first, e;
        //n:table数组长度
        int n;
        K k;
        // 如果桶的数量大于0并且待查找的key所在的桶的第一个元素不为空
        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;
    }

get方法具体分这几步：

1.  计算key的hash值
2.  找到key所在的桶及其第一个元素
3.  如果第一个元素的key等于待查找的key，直接返回
4.  如果第一个元素是树节点就按树的方式来查找
5.  否则就按链表方式查找

### 10.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) {
        
        //引用当前hashMap中的散列表
        Node<K, V>[] tab;
        //当前node元素
        Node<K, V> p;
        //n:表示散列表数组长度
        //index:表示寻址结果
        int n, index;
        // 如果桶的数量大于0且待删除的元素所在的桶的第一个元素不为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
        
            //node:表示查找到的结果
            //e:表示当前node的下一个元素
            Node<K, V> node = null, e;
            K k;
            V v;
            // 如果第一个元素正好就是要找的元素，赋值给node变量后续删除使用
            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);
                }
            }
            // 如果找到了元素，则看参数是否需要匹配value值，如果不需要匹配直接删除，如果需要匹配则看value值是否与传入的value相等
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
        
                if (node instanceof TreeNode)
                    // 如果是树节点，调用树的删除方法（以node调用的，是删除自己）
                    ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    // 如果待删除的元素是第一个元素，则把第二个元素移到第一的位置
                    tab[index] = node.next;
                else
                    // 否则删除node节点，将当前元素p的下一个元素设置为删除元素的下一个元素
                    p.next = node.next;
                ++modCount;
                --size;
                // 删除节点后置处理
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

整个remove流程分为这几步：

1.  先查找元素所在的节点
2.  如果找到的节点是树节点，则按树的移除节点处理
3.  如果找到的节点是桶中的第一个节点，则把第二个节点移到第一的位置
4.  否则按链表删除节点处理
5.  修改size，调用移除节点后置处理等

### 11.总结 ###

1.  HashMap是一种散列表，采用（**数组 + 链表 + 红黑树**）的存储结构
2.  HashMap的默认初始容量为`16`（1<<4），默认装载因子为`0.75f`，容量总是2的n次方
3.  HashMap扩容时**每次容量变为原来的两倍**
4.  当桶的数量小于64时不会进行树化，只会扩容
5.  **当桶的数量大于64且单个桶中元素的数量大于8时，进行树化**
6.  **当单个桶中元素数量小于6时，进行反树化**
7.  HashMap是**非线程安全的容器**
8.  HashMap查找添加元素的时间复杂度都为`O(1)`

> **HashMap在JDK1.7和1.8中不同**

*  1.7 数组 + 链表
 *  1.8 数组 + （链表 | 红黑树）

> **为啥要用红黑树？**

红黑树用来避免 `DoS` 攻击，防止链表超长时性能下降，树化应当是偶然情况，是保底策略

> **为何不一上来就树化？**

*  hash 表的查找，更新的时间复杂度是  O ( 1 ) O(1) O(1)，而红黑树的查找，更新的时间复杂度是  O ( l o g 2 ⁡ n ) O(log\_2⁡n ) O(log2⁡n)
 *  TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表

> **树化阈值为何是8？**

hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 `0.75` 的情况下，**长度超过 8 的链表出现概率是 0.00000006**，树化阈值选择 8 就是为了让树化几率足够小

> **树化规则**

*  当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度，如果数组容量已经 >=64，才会进行树化
 *  树化的两个条件：链表长度超过树化阈值`>8` && 数组容量`>=64`

> **退化规则**

*  情况1：在扩容时如果拆分树时，树元素个数 `<= 6` 则会退化链表
 *  情况2：移除之前，remove 树节点时，若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表

> **索引计算方法**

1.  首先，计算对象的 `hashCode()`
2.  再进行调用 HashMap 的 `hash()` 方法进行**二次哈希**。**二次 hash() 是为了综合高位数据，让哈希分布更为均匀**
3.  最后 `& (capacity – 1)` 得到索引

> **数组容量为何是 2 的 n 次幂**

*  **计算索引时效率更高**：如果是 2 的 n 次幂可以使用位与运算代替取模
 *  **扩容时重新计算索引效率更高**： hash & oldCap == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap

**注意**：

*  二次 hash 是为了配合 **容量是 2 的 n 次幂** 这一设计前提，如果 hash 表的容量不是 2 的 n 次幂，则不必二次 hash
 *  **容量是 2 的 n 次幂** 这一设计计算索引效率更好，但 hash 的分散性就不好，需要二次 hash 来作为补偿，没有采用这一设计的典型例子是 Hashtable

> **put 流程**

1.  HashMap 是**懒惰创建**数组的，首次使用才创建数组
2.  计算索引（桶下标）
3.  如果桶下标还没人占用，创建 Node 占位返回
4.  如果桶下标已经有人占用
    
     *  已经是 TreeNode 走红黑树的添加或更新逻辑
     *  是普通 Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑
5.  返回前检查容量是否超过阈值，一旦超过进行扩容

> **put流程1.7中和1.8的区别**

1.  链表插入节点时，`1.7 是头插法`，`1.8 是尾插法`
2.  1.7 是大于等于阈值且没有空位时才扩容，而 1.8 是大于阈值就扩容
3.  1.8 在扩容计算 Node 索引时，会优化

> **扩容（加载）因子为何默认是 0.75f**

1.  在空间占用与查询时间之间取得较好的权衡
2.  大于这个值，空间节省了，但链表就会比较长影响性能
3.  小于这个值，冲突减少了，但扩容就会更频繁，空间占用也更多

> **key 的设计要求**

1.  HashMap 的 key 可以为 null，但 Map 的其他实现则不然（Hashtable等）
2.  作为 key 的对象，必须实现 hashCode 和 equals，并且 key 的内容不能修改（不可变）
3.  key 的 hashCode 应该有良好的散列性
4.  如果 key 可变，例如修改了 age 会导致再次查询时查询不到

> **String 对象的 hashCode() 设计**

*  目标是达到较为均匀的散列效果，每个字符串的 hashCode 足够独特
 *  字符串中的每个字符都可以表现为一个数字，称为  S i S\_i Si，其中 i 的范围是 0 ~ n - 1
 *  散列公式为：  S 0 ∗ 3 1 ( n − 1 ) + S 1 ∗ 3 1 ( n − 2 ) + … S i ∗ 3 1 ( n − 1 − i ) + … S ( n − 1 ) ∗ 3 1 0 S\_0∗31^\{(n-1)\}+ S\_1∗31^\{(n-2)\}+ … S\_i ∗ 31^\{(n-1-i)\}+ …S\_\{(n-1)\}∗31^0 S0∗31(n−1)\+S1∗31(n−2)\+…Si∗31(n−1−i)\+…S(n−1)∗310
 *  31 代入公式有较好的散列特性，并且 31 \* h 可以被优化为
    
     *  即 $32 ∗h -h $
     *  即  2 5 ∗ h − h 2^5 ∗h -h 25∗h−h
     *  即  h ≪ 5 − h h≪5 -h h≪5−h

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

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/14c80a1cd29a4e5c87bd1f1dd34ec0fd.webp?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[img-8rNFqNRP-1641090759949_HashMap_.assets_image-20211231093118109.png]: https://img-blog.csdnimg.cn/c57ef0992e774d00ba03655f782c3efc.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16
[img-TONIod9y-1641090759953_HashMap_.assets_image-20211128085755408.png]: https://img-blog.csdnimg.cn/f7889cc734564f8296c3a905fad15b89.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/0e2740c92c7c46fc8ee5c0c400c1b980.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16