Java集合之轻松上手HashMap（2022珍藏版）

短命女 2024-04-29 02:47 7阅读 0赞

**目录**

1、什么是HashMap，什么时候选择HashMap

2、HashMap数据结构及其工作原理

2.1数据结构（JDK1.7）

2.2数据结构（JDK1.8之后）

3、源码分析

3.1 JDK1.7版本（1.8在后面）

3.1 JDK1.8版本

四、面试宝典

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

### 版本： ###

JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

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

#### Map（基础知识点） ####

（双列型集合，存放数据无序，key不可重复，value可以重复 ）

![d403ba273d014c34b8a22f13b0644fe5.png][]

#### HashMap ####

底层是哈希表，key不可重复，value可以重复。key对应的记录无序

*  **添加** put(K key , V value) 返回值为value的值，如果有覆盖则是此key上一个旧值
 *  **查询** get(object key)
 *  遍历Map集合

> BookMap.forEach((k,v)->\{  
> (k + "="+v).sout  
> \});

直接打印map集合（可以直接打印是因为HashMap源码中覆盖ltoString方法）

System.out.println(BookMap);

*  **修改** ==覆盖 直接put原来的key 更改value
 *  **删除**（底层是哈希表，没有下标，只能通过key删除value）
    
     *  根据key删除value
     *  clear

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

### 1、什么是HashMap，什么时候选择HashMap ###

说到容器，你肯定会想到 Java中[对象存储][Link 1]容器还有ArrayList，LinkedList，HashSet等，HashMap 相对这些容器来说，可以理解为多了一层指向关系，可以用指定Key找到指定Value。

比如：

现在有一个Java Bean 用于存储职员的信息，字段包括（职员姓名，职员年龄，职员身高，职员体重，职员教育程度 ... 等等），我是一名人力资源管理，我需要将员工信息整理好发给老板。

![146aed0cbf3f43ab8a4337baf484689c.png][]

★ **问题：**

这个时候你必须要想到，如果两个人名字一样可咋办，查到的到底是谁的信息呢？前者信息会被覆盖吗？带着问题来学习一下HashMap[数据结构][Link 2]及其工作原理

### 2、HashMap数据结构及其工作原理 ###

#### 2.1数据结构（**JDK1.7**） ####

**HashMap 数据结构为 数组+链表，其中：链表的节点存储的是一个 Entry 对象，每个Entry 对象存储四个属性（hash，key，value，next）JDK1.7**

![4243661d6bd04bdaa5766f4253ac5037.png][]

> 1.  整体是一个数组；
> 2.  数组每个位置是一个链表；
> 3.  链表每个节点中的Value即我们存储的Object；

#### 2.2数据结构（JDK1.8之后） ####

我们现在用的都是 JDK 1.8，底层是由“数组+链表+红黑树”组成，如下图

![ecc554ff1bfb4feb9b1a4a4444c7cf8c.png][]

**问题： 为什么jdk1.8要改成“数组+链表+红黑树”？**

> 主要是为了提升在 [hash][] 冲突严重时（链表过长）的查找性能，使用链表的查找性能是 O(n)，而使用红黑树是 O(logn)。

### 3、源码分析 ###

#### 3.1 JDK1.7版本（1.8在后面） ####

*  put()方法

> 解释写在代码注释里面了⭐😊

public V put(K key, V value) {
      //第一次的时候一定是成立
      //table默认就是EMPTY_TABLE，这是一个空的Entry数组
      if (table == EMPTY_TABLE) {
        //threshold = 16  ，如果传的值不是2^n,下面函数给他转成2^n
        inflateTable(threshold);
      }
      //如果key的值为空，直接put一个空的Key，只能是这一个，如果多个空key只能覆盖他
      if (key == null)
        return putForNullKey(value);
        //对key取hash，为了使hash码更加离散，也就是扰动
      int hash = hash(key);
      int i = indexFor(hash, table.length);
    //是空的直接放入，不是空的，遍历entry，先根据hash码，再根据equals
      for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
          V oldValue = e.value;
          e.value = value;
          e.recordAccess(this);
          return oldValue;
        }
      }
    
      modCount++;
      addEntry(hash, key, value, i);
      return null;
    }
    
    //初始化数组了
    private void inflateTable(int toSize) {
      //15->16 四舍五入容量成为2次方幂
      int capacity = roundUpToPowerOf2(toSize);
      
      //容量*0.75
      threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
      //创建指定容量的Entry(这儿的容量是四舍五入的2次方幂)
      table = new Entry[capacity];
        //初始化一个Hash种子，使得更加离散
      initHashSeedAsNeeded(capacity);
    }
    
    final boolean initHashSeedAsNeeded(int capacity) {
      //默认的情况下 currentAltHashing 是false
      boolean currentAltHashing = hashSeed != 0;
      //第一项判断jvm是否启动了 true
      //capacity=16第一次的情况下，
      //Holder.ALTERNATIVE_HASHING_THRESHOLD是Integer的最大值,如果传了值就是指定的值
      //第二项判断是false
      //useAltHashing就是false
      boolean useAltHashing = sun.misc.VM.isBooted() &&
        (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
      //异或成为false
      boolean switching = currentAltHashing ^ useAltHashing;
      //不进这个循环
      if (switching) {
        hashSeed = useAltHashing
          ? sun.misc.Hashing.randomHashSeed(this)
          : 0;
      }
      return switching;
    }

> 上面的代码先初始化Entry数组的类，然后设置threshold的值，是为初始化的值\*0.75，然后初始化指定容量的Entry，然后设置hashSeed的值，默认的情况的下0，一般的情况下是不会改变，可以具体看下我上面的注释。

![02cf6ccfac374a91beff4a58d0825071.png][]

如果key为空，这个时候会调用`putForNullKey(value);`方法，具体的代码如下：

//设置默认的空键的值
    private V putForNullKey(V value) {
      //遍历所有的Entry，设置好对应的Entry
      for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
          V oldValue = e.value;
          e.value = value;
          e.recordAccess(this);
          return oldValue;
        }
      }
      //记录修改的次数
      modCount++;
      //第一次为空的情况下，添加对应Entry
      addEntry(0, null, value, 0);
      return null;
    }

> 上面的代码就是遍历所有的table的数组，然后设置table的值，一般的情况下，第一次进来的时候是空的，然后就会调用`addEntry(0, null, value, 0);`具体的代码如下：

// 0 null value 0
    void addEntry(int hash, K key, V value, int bucketIndex) {
      //长度大于初始化长度*0.75，同时这项不等于null
      //会调用扩容 这个时候不会进入
      if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
      }
      //创建Entry的方法
      createEntry(hash, key, value, bucketIndex);
    }

> 上面的代码的是先判断是否需要扩容，扩容的条件：\*\*长度大于初始化长度\*0.75，同时插入的下标在数组不为null。\*\*然后创建Entry，具体的代码如下：

//创建Entry
    void createEntry(int hash, K key, V value, int bucketIndex) {
    //先找到表格中的Entry，直接通过table[当前位置]去new一个Entry
      Entry<K,V> e = table[bucketIndex];
      table[bucketIndex] = new Entry<>(hash, key, value, e);
      size++;
    }

进入Entry中，典型的头插法（新的节点的下一个节点，是原来的头节点）

![fde6758a21e545e888d6624fc12cf3dd.png][]

> 创建好的Entry，然后把size的值++，具体的我们来看下扩容的机制，具体的代码如下：

//扩容的长度是原来的长度*2
    void resize(int newCapacity) {
      //先将原来的值赋值给oldTable
      Entry[] oldTable = table;
      //老的长度
      int oldCapacity = oldTable.length;
      //如果的长度等于最大的长度，就直接用最新的（判断到没到Integer最大值）
      if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
      }
    
      //根据新的长度创建好的newTable
      Entry[] newTable = new Entry[newCapacity];
      
      //initHashSeedAsNeeded(newCapacity)这个返回值为false
      //转移
      transfer(newTable, initHashSeedAsNeeded(newCapacity));
      table = newTable;
      //计算容量*负载因子
      threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

> 上面的代码就是扩容的容量是原来的2倍，然后主要是调用转移的方法`transfer(newTable, initHashSeedAsNeeded(newCapacity));`，具体的代码如下：

//rehash = false
    void transfer(Entry[] newTable, boolean rehash) {
      int newCapacity = newTable.length;
      //遍历原来的数组table
      for (Entry<K,V> e : table) {
        //遍历数组下面的链表
        while(null != e) {
          Entry<K,V> next = e.next;
          //不需要重新rehash
          if (rehash) {
            e.hash = null == e.key ? 0 : hash(e.key);
          }
          //计算出新的位置
          int i = indexFor(e.hash, newCapacity);
          //放入到对应位置
          e.next = newTable[i];
          newTable[i] = e;
          e = next;
        }
      }
    }

*  HashMap（）

//initialCapacity = 16
    //loadFactor = 0.75
    //threshold = initialCapacity
    public HashMap(int initialCapacity, float loadFactor) {
        //容量小于0，就要抛异常
      if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
        //如果大于一个最大的容量（1<<30）,就让他是最大容量
      if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
        //如果负载因子小于0，或者他不是一个正常的传进来的负载因子，就抛异常
      if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
        //就把初始容量和负载因子设置进来了
      this.loadFactor = loadFactor;
      threshold = initialCapacity;
        //可以重写这个方法，所有在HashMap初始化之后~在元素插入之前被调用
      init();
    }

> 上面的代码主要赋值了三个值，一个initialCapacity初始化的值(16)，loadFactor负载因子(0.75)，threshold的值等于16。

> 讲到这个时候,put的方法差不多讲完了，差不多的逻辑，就是判断是否是空的，然后如果是空的，初始化这个table，如果这个键是null，然后就put空的null的键，这个时候也是插入数据，先判断需不需要扩容，如果需要扩容，就先扩容，然后再添加。再然后是计算hash的值，以及计算出来的位置，然后遍历这个数组的位置的链表，找到相同的替换，如果没有，直接添加这个Entry，这个时候也是判断是不是需要扩容，如果需要扩容，就先扩容，如果再添加。

流程图：

![142817d142c64243a01169f67eacc154.png][]

参考资料：[JDK1.7-HashMap的源码\_了不起的盖茨比。的博客-CSDN博客\_jdk1.7源码][JDK1.7-HashMap_-CSDN_jdk1.7]

#### 3.1 JDK1.8版本 ####

从非拷贝构造函数的实现来看，Hashmap的数据似乎并没有在最初就初始化好，仅仅设置了一些初始值而已。

//这两个是限定值 当节点数大于8时会转为红黑树存储
        static final int TREEIFY_THRESHOLD = 8;
        //当节点数小于6时会转为单向链表存储
        static final int UNTREEIFY_THRESHOLD = 6;
        //红黑树最小长度为 64
        static final int MIN_TREEIFY_CAPACITY = 64;
        //HashMap容量初始大小
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
        //HashMap容量极限
        static final int MAXIMUM_CAPACITY = 1 << 30;
        //负载因子默认大小
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
        //Node是Map.Entry接口的实现类
        //在此存储数据的Node数组容量是2次幂
        //每一个Node本质都是一个单向链表
        transient Node<K,V>[] table;
        //HashMap大小,它代表HashMap保存的键值对的多少
        transient int size;
        //HashMap被改变的次数
        transient int modCount;
        //下一次HashMap扩容的大小
        int threshold;
        //存储负载因子的常量
        final float loadFactor;
    
       //默认的构造函数
       public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }
        //指定容量大小
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
         //指定容量大小和负载因子大小
        public HashMap(int initialCapacity, float loadFactor) {
            //指定的容量大小不可以小于0,否则将抛出IllegalArgumentException异常
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
             //判定指定的容量大小是否大于HashMap的容量极限
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
             //指定的负载因子不可以小于0或为Null，若判定成立则抛出IllegalArgumentException异常
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
             
            this.loadFactor = loadFactor;
            // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
            //tableSizeFor用于查找到大于给定数值的最近2次幂值，比如给定18就是32。给定33就是64。
            this.threshold = tableSizeFor(initialCapacity);
        }
        //传入一个Map集合,将Map集合中元素Map.Entry全部添加进HashMap实例中
        public HashMap(Map<? extends K, ? extends V> m) {
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            //此构造方法主要实现了Map.putAll()
            putMapEntries(m, false);
        }

HashMap 是按照 lazy-load 原则，在首次使用时被初始化（拷贝构造函数除外）。我们去看看 put 方法实现，似乎只有一个 putVal 的调用：

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

进入putVal内部

public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
     //HashMap.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;
            //判定table不为空并且table长度不可为0,否则将从resize函数中获取
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
             //这样写法有点绕,其实这里就是通过索引获取table数组中的一个元素看是否为Null
            if ((p = tab[i = (n - 1) & hash]) == null)
                //若判断成立,则New一个Node出来赋给table中指定索引下的这个元素
                tab[i] = newNode(hash, key, value, null);
            else {  //若判断不成立
                Node<K,V> e; K k;
                 //对这个元素进行Hash和key值匹配
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode) //如果数组中德这个元素P是TreeNode类型
                    //判定成功则在红黑树中查找符合的条件的节点并返回此节点
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else { //若以上条件均判断失败，则执行以下代码
                    //向Node单向链表中添加数据
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                             //若节点数大于等于8
                            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; //p记录下一个节点
                    }
                }
                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;
        }

>  *  1.首先获取Node数组table对象和长度，若table为null或长度为0，则调用resize()扩容方法获取table最新对象，并通过此对象获取长度大小
>  *  2.判定数组中指定索引下的节点是否为Null，若为Null 则new出一个单向链表赋给table中索引下的这个节点
>  *  3.若判定不为Null,我们的判断再做分支
>     
>      *  3.1 首先对hash和key进行匹配,若判定成功直接赋予e
>      *  3.2 若匹配判定失败,则进行类型匹配是否为TreeNode 若判定成功则在红黑树中查找符合条件的节点并将其回传赋给e
>      *  3.3 若以上判定全部失败则进行最后操作,向单向链表中添加数据若单向链表的长度大于等于8,则将其转为红黑树保存，记录下一个节点,对e进行判定若成功则返回旧值
>  *  4.最后判定数组大小需不需要扩容

resize方法

//重新设置table大小/扩容 并返回扩容的Node数组即HashMap的最新数据
    final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table; //table赋予oldTab作为扩充前的table数据
            int oldCap = (oldTab == null) ? 0 : oldTab.length; 
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {
                 //判定数组是否已达到极限大小，若判定成功将不再扩容，直接将老表返回
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                 //若新表大小(oldCap*2)小于数组极限大小 并且 老表大于等于数组初始化大小
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    //旧数组大小oldThr 经二进制运算向左位移1个位置 即 oldThr*2当作新数组的大小
                    newThr = oldThr << 1; // double threshold
            }
             //若老表中下次扩容大小oldThr大于0
            else if (oldThr > 0)
                newCap = oldThr;  //将oldThr赋予控制新表大小的newCap
            else { //若其他情况则将获取初始默认大小
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            //若新表的下表下一次扩容大小为0
            if (newThr == 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; //将当前表赋予table
            if (oldTab != null) { //若oldTab中有值需要通过循环将oldTab中的值保存到新表中
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {//获取老表中第j个元素 赋予e
                        oldTab[j] = null; //并将老表中的元素数据置Null
                        if (e.next == null) //若此判定成立 则代表e的下面没有节点了
                            newTab[e.hash & (newCap - 1)] = e; //将e直接存于新表的指定位置
                        else if (e instanceof TreeNode)  //若e是TreeNode类型
                            //分割树，将新表和旧表分割成两个树，并判断索引处节点的长度是否需要转换成红黑树放入新表存储
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // preserve order
                            Node<K,V> loHead = null, loTail = null; //存储与旧索引的相同的节点
                            Node<K,V> hiHead = null, hiTail = null; //存储与新索引相同的节点
                            Node<K,V> next;
                            //通过Do循环 获取新旧索引的节点
                            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;
                            }
                        }
                    }
                }
            }
            //返回新表
            return newTab;
        }

>  *  1.判定数组是否已达到极限大小，若判定成功将不再扩容，直接将老表返回
>  *  2.若新表大小(oldCap2)小于数组极限大小&老表大于等于数组初始化大小 判定成功则 旧数组大小oldThr 经二进制运算向左位移1个位置 即 oldThr2当作新数组的大小
>     
>      *  2.1. 若\[2\]的判定不成功，则继续判定 oldThr （代表 老表的下一次扩容量）大于0，若判定成功 则将oldThr赋给newCap作为新表的容量
>      *  2.2 若 \[2\] 和\[2.1\]判定都失败,则走默认赋值 代表 表为初次创建
>  *  3.确定下一次表的扩容量, 将新表赋予当前表
>  *  4.通过for循环将老表中德值存入扩容后的新表中
>     
>      *  4.1 获取旧表中指定索引下的Node对象 赋予e 并将旧表中的索引位置数据置空
>      *  4.2 若e的下面没有其他节点则将e直接赋到新表中的索引位置
>      *  4.3 若e的类型为TreeNode红黑树类型
>         
>          *  4.3.1 分割树，将新表和旧表分割成两个树，并判断索引处节点的长度是否需要转换成红黑树放入新表存储
>          *  4.3.2 通过Do循环 不断获取新旧索引的节点
>          *  4.3.3 通过判定将旧数据和新数据存储到新表指定的位置

> 门限值等于（负载因子）x（容量），如果构建 HashMap 的时候没有指定它们，那么就是依据相应的默认常量值。
> 
> 门限通常是以倍数进行调整 （newThr = oldThr << 1），我前面提到，根据 putVal 中的逻辑，当元素个数超过门限大小时，则调整 Map 大小。
> 
> 扩容后，需要将老的数组中的元素重新放置到新的数组，这是扩容的一个主要开销来源。

资料参考：[通俗易懂Hashmap源码解析\_码农小白猿的博客-CSDN博客\_hashmap源码][Hashmap_-CSDN_hashmap]

### 四、面试宝典 ###

#### 1、HashMap 的底层数据结构 ####

JDK 1.8，底层是由“数组+链表+红黑树”组成，如下图，而在 JDK 1.8 之前是由“数组+链表”组成

![16e81fb5a8b94c979a21838bd02745ba.png][]

#### 2、为什么要改成“数组+链表+红黑树”？ ####

> 主要是为了提升在 [hash][] 冲突严重时（链表过长）的查找性能，使用链表的查找性能是 O(n)，而使用红黑树是 O(logn)。

#### 3、那在什么时候用链表？什么时候用红黑树？ ####

>  *  对于插入，默认情况下是使用链表节点。当同一个索引位置的节点在新增后达到9个（阈值8）：如果此时数组长度大于等于 64，则会触发链表节点转红黑树节点（treeifyBin）；而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容，因为此时的数据量还比较小。
>  *  对于移除，当同一个索引位置的节点在移除后达到 6 个，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点（untreeify）。

#### 4、为什么链表转红黑树的阈值是8？ ####

> 时间和空间
> 
>  *  红黑树节点大小约为链表节点的2倍，在节点太少时，红黑树的查找性能优势并不明显，付出2倍空间的代价作者觉得不值得
>  *  理想情况下，使用随机的哈希码，节点分布在 hash 桶中的频率遵循泊松分布，按照泊松分布的公式计算，链表中节点个数为8时的概率为 0.00000006，这个概率足够低了，并且到8个节点时，红黑树的性能优势也会开始展现出来，因此8是一个较合理的数字。

#### 5、那为什么转回链表节点是用的6而不是复用8？ ####

> 如果我们设置节点多于8个转红黑树，少于8个就马上转链表，当节点个数在8徘徊时，就会频繁进行红黑树和链表的转换，造成性能的损耗。

#### 6、HashMap 有哪些重要属性？分别用于做什么的？ ####

> 除了用来存储我们的节点 table 数组外，HashMap 还有以下几个重要属性：
> 
> 1）size：HashMap 已经存储的节点个数；
> 
> 2）threshold：扩容阈值，当 HashMap 的个数达到该值，触发扩容。
> 
> 3）loadFactor：负载因子，扩容阈值 = 容量 \* 负载因子。

#### 7、threshold 除了用于存放扩容阈值还有其他作用吗？ ####

> 在我们新建 HashMap 对象时， threshold 还会被用来存初始化时的容量。HashMap 直到我们第一次插入节点时，才会对 table 进行初始化，避免不必要的空间浪费。

#### 8、HashMap 的默认初始容量是多少？HashMap 的容量有什么限制吗？ ####

> 默认初始容量是16。HashMap 的容量必须是2的N次方，HashMap 会根据我们传入的容量计算一个大于等于该容量的最小的2的N次方，例如传 9，容量为16。

#### 9、为什么负载因子默认值是0.75。 ####

> 在时间和空间上权衡的结果。如果值较高，例如1，此时会减少空间开销，但是 hash 冲突的概率会增大，增加查找成本；而如果值较低，例如 0.5 ，此时 hash 冲突会降低，但是有一半的空间会被浪费，所以折衷考虑 0.75 似乎是一个合理的值。

#### 10、HashMap 的插入流程是怎么样的？ ####

![997601f9eea0409fac770af5a2863c57.png][]

#### 11、扩容的流程 ####

![f3a4278998f548ffa587e3c3b515c0dd.png][]

#### 12、死循环问题 ####

导致死循环的根本原因是 JDK 1.7 扩容采用的是“头插法”，会导致同一索引位置的节点在扩容后顺序反掉。而 JDK 1.8 之后采用的是“尾插法”，扩容后节点顺序不会反掉，不存在死循环问题。

> **hashmap1.7中的死循环是有多个线程并发扩容形成了环状链表，随后再进行扩容的线程会循环取这个环状链表的节点，造成死循环；其次，环状链表是几个节点相互指向，并不是某个节点自己指向自己。**

[d403ba273d014c34b8a22f13b0644fe5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/29/c60faee6c2994640a390639e65944882.png
[Link 1]: https://so.csdn.net/so/search?q=%E5%AF%B9%E8%B1%A1%E5%AD%98%E5%82%A8&spm=1001.2101.3001.7020
[146aed0cbf3f43ab8a4337baf484689c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/29/eab1ce24ef7e4870981c3125fabad463.png
[Link 2]: https://so.csdn.net/so/search?q=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84&spm=1001.2101.3001.7020
[4243661d6bd04bdaa5766f4253ac5037.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/29/e7f5053308b14b73a70a847c7f056aed.png
[ecc554ff1bfb4feb9b1a4a4444c7cf8c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/29/e618f6fbea8d4b7399306dc1e3405c7e.png
[hash]: https://so.csdn.net/so/search?q=hash&spm=1001.2101.3001.7020
[02cf6ccfac374a91beff4a58d0825071.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/29/8b2256c17bc244c0975bc42436f70014.png
[fde6758a21e545e888d6624fc12cf3dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/29/bc6b400d1324477dbf3019f2cd94d9c5.png
[142817d142c64243a01169f67eacc154.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/29/6484dcfe6f6f49cda59a64ced8d0535b.png
[JDK1.7-HashMap_-CSDN_jdk1.7]: https://blog.csdn.net/qq_36434742/article/details/119681178?ops_request_misc=&request_id=&biz_id=102&utm_term=jdk1.7hashmap%E6%BA%90%E7%A0%81&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-119681178.142%5Ev21%5Epc_rank_34,157%5Ev15%5Enew_3&spm=1018.2226.3001.4187
[Hashmap_-CSDN_hashmap]: https://blog.csdn.net/xadasss/article/details/116793267?ops_request_misc=&request_id=&biz_id=102&utm_term=hashMap%E6%BA%90%E7%A0%81&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-2-116793267.142%5Ev24%5Ehuaweicloudv2,157%5Ev15%5Enew_3&spm=1018.2226.3001.4187
[16e81fb5a8b94c979a21838bd02745ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/29/215d8b20e4ec4a88ab00e0e282aa44ac.png
[997601f9eea0409fac770af5a2863c57.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/29/1db17f2272d8462fb4810e87dedd641e.png
[f3a4278998f548ffa587e3c3b515c0dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/29/9955403d9be74aeca26e957079637dc0.png