• HashMap超详细源码分析

    目录

    HashMap的特点

    实现原理

    JDK1.8的HashMap源码分析

    与JDK1.7中的区别

    默认数据——静态常量

    可变数据——用于存放数据的变量

    构造方法

    无参构造

     有参构造

    供外部调用的方法

    0.基础方法：hash()

    通过位运算，获取哈希值 

    1.get(Object key)

              2.put(K key, V value) 

    3.resize()

    4.remove()

    关于在JDK1.8中引入红黑树

    HashMap的特点

    • HashMap以key-value的形势存储数据
    • 通过key可以查出value
    • key具有唯一性，重复时新数据会覆盖旧数据
    • 存入数据具有无序性（与存入顺序不同），存入时通过hash算法确定存放位置
    • key与value可以为空，但是空的key也视为一个有效的key，不能重复
    • HashMap底层实现
      • jdk1.7：数组+链表
      • jdk1.8：数组+链表+红黑树

    实现原理

    HashMap将一个key-value当做一个整体来处理，使用数组存储这些键值对，通过计算key的hash值来确定数组中的存放位置，当两个key计算出相同的位置的时候（哈希冲突），在数组相应位置创建链表，在jdk1.8及以上版本中，当链表满足一定需求时就会转换为红黑树

    JDK≤1.7

    • 数组+单链表

    JDK≥1.8

    • 数组+单链表
    • 当有链表长度>8且数组长度>64：该链表转换为数组+红黑树

    JDK1.8的HashMap源码分析

    与JDK1.7中的区别

     jdk1.7中HashMap源码约等于jdk1.8的阉割版，少了转换为树的逻辑，并且链表的插入方式为头插法，1.8为尾插法

    默认数据——静态常量

      1.默认桶容量，即数组的初始大小，1左移4位 -> 16

        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

      2.数组的最大容量，1左移30位，很大的数，够用，不用关注

        static final int MAXIMUM_CAPACITY = 1 << 30;

       3.数组的负载因子，当（数组占用量）超过（数组长度*负载因子）的时候，就会触发扩容

        static final float DEFAULT_LOAD_FACTOR = 0.75f;

       4.树化阈值，链表长度超过阈值会将单链表结构转化为红黑树

        static final int TREEIFY_THRESHOLD = 8;

       5.链表化阈值，当红黑树结点小于6的时候，树会转化回单链表

        static final int UNTREEIFY_THRESHOLD = 6;

      6.数组阈值，树化时需要数组长度需要>64，否则不发生树化

        static final int MIN_TREEIFY_CAPACITY = 64;

    可变数据——用于存放数据的变量

      1.table：Node类型数组，用于存放键值对

        transient Node[] table;

      2.entrySet：用来存储键值对的集合，Map.Entry是内部类，用于键与值的映射

        transient Set> entrySet;

      3. size：存储键值对的个数

        transient int size;

      4.modCount ：记录修改次数

        transient int modCount;

      5.threshold：扩容方法 ，扩容部分大小为负载因子*桶当前大小

        int threshold;

       6.loadFactor：记录哈希表的负载因子，上面有默认值

        final float loadFactor;

    构造方法

    无参构造

    最常用的构造方式，使用默认的负载因子0.75，除了赋值不做其他操作

    1.     public HashMap() {
    2.        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    3.     }

     有参构造

      1.指定桶大小

    1.     public HashMap(int initialCapacity) {
    2.         this(initialCapacity, DEFAULT_LOAD_FACTOR);
    3.     }

      2.指定桶大小与负载因子，需要做的判断较多，与源码结合使用注释说明方便理解

    1. //initialCapacity桶大小
    2. //loadFactor负载因子
    3. public HashMap(int initialCapacity, float loadFactor) {
    4.     	// 判断给定的桶大小
    5.         if (initialCapacity < 0)
    6.             //小于0抛出异常，非法参数
    7.             throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    8.     	//判断给定的桶大小和默认大小的关系
    9.         if (initialCapacity > MAXIMUM_CAPACITY)
    10.             //如果给定的桶更大，用默认桶的大小
    11.             initialCapacity = MAXIMUM_CAPACITY;
    12.     	//判断负载因子是否合法：是数且>0
    13.         if (loadFactor <= 0 || Float.isNaN(loadFactor))
    14.             //抛异常，非法参数
    15.             throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    16.      	//正常，使用给定的负载因子
    17.         this.loadFactor = loadFactor;
    18.         this.threshold = tableSizeFor(initialCapacity);
    19.     }
    20.     //桶大小需要是2的整数幂，使用移位找出小于给定桶大小的最大的数
    21.     static final int tableSizeFor(int cap) {
    22.         int n = cap - 1;
    23.         n |= n >>> 1;
    24.         n |= n >>> 2;
    25.         n |= n >>> 4;
    26.         n |= n >>> 8;
    27.         n |= n >>> 16;
    28.         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    29.     }

    供外部调用的方法

    0.基础方法：hash()

    通过位运算，获取哈希值 

    i = (n - 1) & hash

     hash值通过HashCode获得，在HashMap中，hash值通过桶大小或运算HashCode获得

    举个例子：

            桶大小 = 10，HashCode = 12

            hash值 = 00001010(2) | 00001100(2) = 00000110(2) = 6

    位运算的速度远大于加减乘除的操作，节省运算时间

    1.get(Object key)

     通过key-value键值对的key来获取对应的value值

    1.     public V get(Object key) {
    2.         Node e;
    3.         return (e = getNode(hash(key), key)) == null ? null : e.value;
    4.     }

     该方法会调用getNode内部方法，该内部方法被final修饰，无法对该方法进行重写

    1. final Node getNode(int hash, Object key) {
    2.         Node[] tab; Node first, e; int n; K k;
    3.         //进行判断，桶不为空、长度不为0且key的hash值对应的桶的位置上不为空
    4.         if ((tab = table) != null && (n = tab.length) > 0 &&
    5.             (first = tab[(n - 1) & hash]) != null) {
    6.             //判断数组对应位置上的第一个元素是否为要找的元素
    7.             if (first.hash == hash && // always check first node
    8.                 ((k = first.key) == key || (key != null && key.equals(k))))
    9.                 return first;
    10.             //不是第一个元素，判断后续有没有结点
    11.             if ((e = first.next) != null) {
    12.                 //判断是否是红黑树
    13.                 if (first instanceof TreeNode)
    14.                     //调用红黑树的查找结点的方法
    15.                     return ((TreeNode)first).getTreeNode(hash, key);
    16.                 do {//不是红黑树，使用do while循环判断key对应的元素
    17.                     if (e.hash == hash &&
    18.                         ((k = e.key) == key || (key != null && key.equals(k))))
    19.                         return e;
    20.                 } while ((e = e.next) != null);
    21.             }
    22.         }
    23.         return null;
    24.     }

    get的流程：

    1. 调用get(Object key)方法
    2. 该方法调用内部的final方法getNode(int hash, Object key)
    3. 在getNode方法中，先判断桶是否为空、桶长度是否大于0、桶上key对应的hash的位置是否为空，空就return null
    4. 判断桶上那个位置的第一个数据，是就return这个数据
    5. 如果在数组上的不是要找的数据，再判断桶上这个位置是否有链表或红黑树，如果是链表那就用dowhile循环通过key值找，如果是红黑树就通过内部方法getTreeNode去找。

    2.put(K key, V value) 

    向集合中添加键值对

    1. 	public V put(K key, V value) {
    2.         //调用内部方法
    3.     	return putVal(hash(key), key, value, false, true);
    4. 	}
    1.  	final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    2.                    boolean evict) {
    3.         Node[] tab; Node p; int n, i;
    4.         //桶空或者桶长度=0，就会调用内部扩容方法resize()
    5.         if ((tab = table) == null || (n = tab.length) == 0)
    6.             n = (tab = resize()).length;
    7.          //通过索引判断key的hash值对应的位置是否为空
    8.         if ((p = tab[i = (n - 1) & hash]) == null)
    9.             //整一个新的结点给这个键值对
    10.             tab[i] = newNode(hash, key, value, null);
    11.         else {//那个坑有萝卜占了
    12.             Node e; K k;
    13.              //判断key值或者hash值想不想等
    14.             if (p.hash == hash &&
    15.                 ((k = p.key) == key || (key != null && key.equals(k))))
    16.                 //相等了，覆盖
    17.                 e = p;
    18.             else if (p instanceof TreeNode) //判断已有元素是否是树结点类型
    19.                 //结点类型，去树里找key或hash相等的
    20.                 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
    21.             else { //坑里有萝卜、链表结构找不到key或hash相同的元素、不是树型结构，那就往下走
    22.                 //尾插法将新结点插入进链表
    23.                 for (int binCount = 0; ; ++binCount) {
    24.                     if ((e = p.next) == null) {
    25.                         p.next = newNode(hash, key, value, null);
    26.                          //插完了结点树到了8
    27.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    28.                             //结构转为红黑树，同样是内部方法
    29.                             treeifyBin(tab, hash);
    30.                         break;
    31.                     }
    32.                     if (e.hash == hash &&
    33.                         ((k = e.key) == key || (key != null && key.equals(k))))
    34.                         break;
    35.                     p = e; //p记录下一个节点
    36.                 }
    37.             }
    38.             if (e != null) { // existing mapping for key
    39.                 V oldValue = e.value;
    40.                 if (!onlyIfAbsent || oldValue == null)
    41.                     e.value = value;
    42.                 afterNodeAccess(e);
    43.                 return oldValue;
    44.             }
    45.         }
    46.         ++modCount;
    47.         //桶到没到负载因子规定的大小
    48.         if (++size > threshold)
    49.             //到了，那扩容呗
    50.             resize();
    51.         afterNodeInsertion(evict);
    52.         return null;
    53.     }
    54.

     put流程：

    1. 外部调用put方法，put再调用内部方法putVal。
    2. 在putVal方法中先判断桶大小0或桶长度0，只要有一个成立那就先调桶扩容方法resize()
    3. 桶内有数据且长不为0的时候，通过key和key的hash值判断桶上自己的位置有没有人占着，没人占着那就创建一个新的结点，把入参的键值对放进去，如果有人占着：
      1. 通过key和hash值找有没有相等的，有就覆盖，然后return，没有则：
      2. 桶上这个位置是不是存了个树，是的话那就调用树的putTreeNode方法往里放键值对，然后return，如果不是树的话：
      3. 尾插法直接在链表尾部插入新结点
    4. 插入新结点如果链表长度超过阈值了（默认8），那就用内部方法treeifyBin将链表转为红黑树
    5. 最后通过负载因子*桶大小，判断要不要给桶扩容，需要就调一遍resize()
    6. 结束 

    3.resize()

    扩容方法，每次调用就扩大负载因子*桶大小的空间 

    1. final Node[] resize() {
    2.         //先用oldTab存一下扩容之前的数据（桶，即数组）
    3.         Node[] oldTab = table; 
    4.         //扩容之前的桶空就是0，不空就返回桶的大小
    5.         int oldCap = (oldTab == null) ? 0 : oldTab.length; 
    6.         int oldThr = threshold;
    7.         int newCap, newThr = 0;
    8.         //老的桶不是空
    9.         if (oldCap > 0) {
    10.              //虽然桶上限很大，还是要判断下，桶满了就不扩容了，直接返回传进来的数据
    11.             if (oldCap >= MAXIMUM_CAPACITY) {
    12.                 threshold = Integer.MAX_VALUE;
    13.                 return oldTab;
    14.             }
    15.              //判断，如果桶大小那个数左移1位（就是*2）后，不超过桶上限而且还比默认初始化的大小大
    16.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
    17.                      oldCap >= DEFAULT_INITIAL_CAPACITY)
    18.                 //为下次扩容做准备，下次扩容后的大小 -> 本次扩容大小那个数左移1位（即*2，空间翻倍）
    19.                 newThr = oldThr << 1; // double threshold
    20.         }
    21.         //老的桶空，并且算出来的扩容空间大小>0
    22.         else if (oldThr > 0)
    23.             newCap = oldThr;  //直接把扩容的后的大小给新桶
    24.         else { //桶空，而且扩容大小有问题（负载因子或者记录当前桶大小的数据非法，又或者计算过程出问题等）
    25.             //直接使用默认数值进行扩容（HashMap内部设定的静态数值）
    26.             newCap = DEFAULT_INITIAL_CAPACITY;
    27.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    28.         }
    29.         //如果上面扩容完毕的桶，下一次扩容大小是0
    30.         if (newThr == 0) {  
    31.             //使用扩容因子*新的桶大小获取下次扩容的大小
    32.             float ft = (float)newCap * loadFactor;
    33.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
    34.                       (int)ft : Integer.MAX_VALUE);
    35.         }
    36.         threshold = newThr; //更新当前扩容大小 <= 下次扩容的大小
    37.         @SuppressWarnings({"rawtypes","unchecked"})
    38.             Node[] newTab = (Node[])new Node[newCap];
    39.         table = newTab; //将新桶数据放进table
    40.         if (oldTab != null) { //若旧的桶中有数据，需要将旧数据放进新桶
    41.             for (int j = 0; j < oldCap; ++j) {
    42.                 Node e;
    43.                 if ((e = oldTab[j]) != null) {//旧桶不为空的位置的数据，放进新桶
    44.                     oldTab[j] = null; //清除旧桶对应位置的数据
    45.                     if (e.next == null) //当前数据如果没有后续结点
    46.                         newTab[e.hash & (newCap - 1)] = e; //该节点存入新桶
    47.                     else if (e instanceof TreeNode)  //如果该结点是TreeNode类型
    48.                         //分割树，将新表和旧表分割成两个树，并判断索引处节点的长度是否需要转换成红黑树放入新表存储
    49.                         ((TreeNode)e).split(this, newTab, j, oldCap);
    50.                     else { // preserve order
    51.                         Node loHead = null, loTail = null; //存储与旧索引的相同的节点
    52.                         Node hiHead = null, hiTail = null; //存储与新索引相同的节点
    53.                         Node next;
    54.                         //通过do while循环 获取新旧索引的节点
    55.                         do {
    56.                             next = e.next;
    57.                             if ((e.hash & oldCap) == 0) {
    58.                                 if (loTail == null)
    59.                                     loHead = e;
    60.                                 else
    61.                                     loTail.next = e;
    62.                                 loTail = e;
    63.                             }
    64.                             else {
    65.                                 if (hiTail == null)
    66.                                     hiHead = e;
    67.                                 else
    68.                                     hiTail.next = e;
    69.                                 hiTail = e;
    70.                             }
    71.                         } while ((e = next) != null);
    72.                         //通过判定将旧数据和新数据存储到新桶指定的位置
    73.                         if (loTail != null) {
    74.                             loTail.next = null;
    75.                             newTab[j] = loHead;
    76.                         }
    77.                         if (hiTail != null) {
    78.                             hiTail.next = null;
    79.                             newTab[j + oldCap] = hiHead;
    80.                         }
    81.                     }
    82.                 }
    83.             }
    84.         }
    85.         //返回新的桶
    86.         return newTab;
    87.     }
    88.

     resize方法的流程较长且判断较多，逻辑也可能弄混：

    1. 先记录旧桶的数据、旧桶的大小、当前扩容大小、新桶大小、新桶扩容的大小。
      1. 如果旧桶不是空的：
        1. 如果旧桶的数据量到了桶的容量上限，直接return旧数据
        2. 如果旧桶的空间翻倍还是没到容量上限而且旧桶的数据量大于HashMap内部的默认桶大小，扩容，新桶大小 = 旧桶*2，并且下次扩容大小 = 当前扩容大小*2
      2. 如果旧桶是空的，且当前扩容大小大于0，那就新桶大小直接等于扩容大小
      3. 如果旧桶是空的，而且当前扩容大小不大于0（负载因子或旧桶大小的合法性有问题，又或者计算过程有问题），那就将新桶大小和下次扩容大小用HashMap内部静态常量计算
    2. 如果下次扩容大小是0，那就通过上面计算完的新桶大小*负载因子算出下次扩容的大小
    3. 经过上面的流程新桶已经扩容完成（数据还未复制），将下次扩容大小的值赋给当前扩容大小
    4. 将新桶赋给table
    5. 如果旧桶是有数据，记录不为空的位置的数据，并抹去旧桶中的数据
      1. 如果该数据后面没有结点了，那就直接放在新桶中该数据key的hash值的位置
      2. 如果该数据是个树结点，那就将新桶与旧桶分成两个树，并通过索引处结点的长度转换成红黑树放进新桶
      3. 不是上述两种情况，那就需要维护桶的秩序，通过do while循环，将当前数据，与他后边所有的结点全部重新计算位置并放到新桶对应的位置
    6. 扩容结束，返回新桶，这时旧桶也全部清空

    tips：

    • 从扩容流程中可以看出在扩容时会复制一次HashMap数据，并且重新遍历所有数据的hash值，既耗费资源又耗费时间，应当尽量避免扩容，当然，只是尽量，该扩容时还是要扩容
    • 扩容后结点在新桶中的位置 = 旧桶中的位置 + 旧桶的长度，不需要重新计算hash值，节省了资源和时间

    4.remove()

    删除方法，通过key删除键值对

    1. public V remove(Object key) {
    2.         Node e;
    3.         return (e = removeNode(hash(key), key, null, false, true)) == null ?
    4.             null : e.value;
    5. }
    1. final Node removeNode(int hash, Object key, Object value,
    2.                            boolean matchValue, boolean movable) {
    3.     Node[] tab; Node p; int n, index;
    4. 	// 桶不为空且桶长度>0且key的hash值对应位置不为空
    5.     if ((tab = table) != null && (n = tab.length) > 0 &&
    6.         (p = tab[index = (n - 1) & hash]) != null) {
    7.         Node node = null, e; K k; V v;
    8.         // 如果该位置就是目标结点
    9.         if (p.hash == hash &&
    10.             ((k = p.key) == key || (key != null && key.equals(k))))
    11.             //node结点指向p
    12.             node = p;
    13.         //桶上这个位置是链表或者树
    14.         else if ((e = p.next) != null) {
    15.             //该节点是树节点
    16.             if (p instanceof TreeNode)
    17.                 //通过红黑树的get方法获取结点
    18.                 node = ((TreeNode)p).getTreeNode(hash, key);
    19.             //不是普通键值对且不是树节点，那就是单链表了
    20.             else {
    21.                 // 通过do while循环遍历链表寻找目标结点
    22.                 do {
    23.                     if (e.hash == hash &&
    24.                         ((k = e.key) == key ||
    25.                          (key != null && key.equals(k)))) {
    26.                         node = e;
    27.                         break;
    28.                     }
    29.                     p = e;
    30.                 } while ((e = e.next) != null);
    31.             }
    32.         }
    33.         // 将找到的结点与传入的参数做对比
    34.         if (node != null && (!matchValue || (v = node.value) == value ||
    35.                              (value != null && value.equals(v)))) {
    36.             // 通过调用红黑树的方法来删除结点
    37.             if (node instanceof TreeNode)
    38.                 ((TreeNode)node).removeTreeNode(this, tab, movable);
    39.             // 删除链表结点
    40.             else if (node == p)
    41.                 tab[index] = node.next;
    42.             else
    43.                 p.next = node.next;
    44.             ++modCount;
    45.             --size;
    46.             afterNodeRemoval(node);
    47.             return node;
    48.         }
    49.     }
    50.     return null;
    51. }

     remove方法相比上面的方法，流程就简洁了不少：

    1. 经典判断桶不空 && 桶长>0 && 桶对应位置是否空
    2. 如果桶上key的hash值的位置就是目标结点，直接让node指向该处
    3. 如果该处不是：
      1. 该位置如果是树节点：通过红黑树的get方法获得目标结点
      2. 如果是链表：通过do while循环获得目标结点
    4. 判断入参和找到的结点信息是否一致
      1. 如果是红黑树结点：用红黑树的删除方法删除目标结点
      2. 普通链表结点，直接删除
      3. 其余节点依次链接

    关于在JDK1.8中引入红黑树

    使用红黑树解决了拉链法链表过深问题，为最优结构

    • 数组+链表的存储方式，视觉上就像一个被拉开的拉链，但是链表特别长的时候遍历会明显变慢
    • 在使用二叉排序树的时候，在某些情况下会变成一条线性结构，比如只往右走的树，那就和单链表一样了，遍历起来相比链表没有任何优化。
    • 可以通过旋转树将二叉排序树转换为平衡二叉树，但是平衡二叉树是严格平衡的，删除树结点的时候为了维护秩序可能会旋转非常多的次数，即耗费时间又浪费资源。
    • 红黑树是非严格平衡的不论是新增还是删除，只需要最多旋转三次即可达到平衡，这样不仅在遍历的时候深度会大大减少，查询更快，操作树的时候也效率更高开销更小
    • B+树的特点是“矮胖”，只有叶子结点存储数据，每个叶子结点能储存非常多的数据，所以B+树能应对大量数据的情况，经常被用在数据库中。但是数据量不是很多的时候可能这些数据都挤在一个结点里，那这样遍历效率又退化成了链表，不合适。
    • 跳表查询也很快，但是HashMap的各个键值对之间没有内在排序关系，没有排序关系也就没法跳跃查询，跳表也需要定义多级指针，空间换时间，而红黑树不需要额外空间

    总结：

            红黑树是个非严格平衡的树，在删除的时候只要最多求三次旋转打到局部平衡即可，遍历也许没有二叉排序树和平衡二叉树快，但是维护性远强于前者，有良好的稳定性，在几种数据结构中综合实力最强

  • 相关阅读:
    Qt在qml组件中传递自定义类对象或结构体到cpp对象
    重复乃技艺之母
    14、监测数据采集物联网应用开发步骤(10)
    计算机毕业设计JavaH5女娲宫旅游网站设计与实现(源码+系统+mysql数据库+lw文档）
    centos7安装ansible图形化管理界面AWX
    java版Spring Cloud之Spark 离线开发框架设计与实现
    在Python上用openSMILE提取IS09和eGeMAPS特征集
    GitHub 上有什么好玩又有挑战的前端项目？
    tcp网络编程——2
    2023年8月第4周大模型荟萃
  • 原文地址：https://blog.csdn.net/qq_57031340/article/details/126807443