• HashMap源码解析

    前置知识：

    关于hashCode方法

    哈希：可以将任意长度的输入，通过散列算法，转化成固定长度的输出，这个输出称为哈希值。

    哈希表：固定长度的数组。

    散列算法（哈希）：建立 数据的关键字 （key）和 数据在数组中的存放位置（即index）的关系的方法。

    在HashMap中，对应的散列算法为：

    index = hash(key) & (arr.length - 1)

    哈希冲突：当不同key通过哈希函数，得到的index是一样的，称为哈希冲突。

    解决哈希冲突的方法：

    • 线形探查法：从index顺序往下查找，直到找到一个null的位置。
    • 二次探查法
    • 链地址法：在index位置，顺序建立hash冲突的链表。
    • 再哈希法：建立多个hash函数。

    其中HashMap使用解决hash冲突的方法是链地址法。

    HashMap基本结构

    HashMap的本质是一个Node数组和链表及红黑树的组合。Node 实现了Map.Entry接口，每次调用hashMap.put方法时，就是 创建一个Node，放在根据key的hashCode计算出来的index上。如果存在hash冲突，就会在index的位置创建一个链表。而当链表的长度>8时，会将链表转成红黑树以提高查找效率。所以HashMap的查询，插入的时间复杂度都是o(1)。

    transient Node<K,V>[] table;

    Node的基本结构：存储hash，key和value。

    1. static class Node<K,V> implements Map.Entry<K,V> {
    2.     final int hash;
    3.     final K key;
    4.     V value;
    5.     Node<K,V> next;
    6. }

    一些常见的常量：

    1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;// 数组默认初始容量16
    2. static final int MAXIMUM_CAPACITY = 1 << 30;// 数组最大容量2^30
    3. static final float DEFAULT_LOAD_FACTOR = 0.75f;// 默认的负载因子，即当size > CAPACITY *DEFAULT_LOAD_FACTOR时，进行扩容
    4. static final int TREEIFY_THRESHOLD = 8;// 解决hash冲突时，当链表长度> TREEIFY_THRESHOLD，就将链表转化成红黑树

    再看HashMap中两个重要的属性：

    1. // The next size value at which to resize (capacity * load factor).
    2. int threshold;
    3. // The load factor for the hash table.
    4. final float loadFactor;

    根据注释可以看出 threshold = capacity * loadFactor

    capacity 是数组的容量。

    loadFactor 又叫负载因子，默认是DEFAULT_LOAD_FACTOR（0.75）。当创建Node的个数大于容量 * loadFactor时，就会进行扩容。

    可能有人会问，既然都可以使用链表或红黑树去解决哈希冲突了，那就代表无论往数组里放多少个元素，都可以放得下。那为什么还需要扩容呢？

    因为HashMap的生命力在于查询速度，虽然可以解决哈希冲突，但也代表查找元素的速度变慢了。所以需要进行数组扩容，减少哈希冲突，提高查询速度。

    下面再看下在代码中，是怎么初始化这两个变量（threshold和loadFactor）的？它是不是按它说的做了（--> _-->）？

    当调用put方法的时候，会调用putVal方法。

    当tab == null，会调用resize方法。可以从resize方法看到对loadFactor，threshold等全局变量的初始化。

    1. final Node<K,V>[] resize() {// 扩容的方法，这里只用来解释loadFactor和threshold的意思，详细的后面再讲。
    2.     Node<K,V>[] oldTab = table;
    3.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
    4.     int oldThr = threshold;
    5.     int newCap, newThr = 0;
    6.     if (oldCap > 0) {/****/}
    7.     else if (oldThr > 0) // initial capacity was placed in threshold
    8.         newCap = oldThr;
    9.     else { 
    10. // 默认的初始化，会将数组长度newCap置为DEFAULT_INITIAL_CAPACITY:16，将newThr置为0.75*16=12,
    11.     // newThr即threshold
    12.         newCap = DEFAULT_INITIAL_CAPACITY;
    13.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    14.     }
    15.     if (newThr == 0) {
    16.         float ft = (float)newCap * loadFactor;
    17.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
    18.                   (int)ft : Integer.MAX_VALUE);
    19.     }
    20.     threshold = newThr;
    21.     /****/
    22.     return newTab;
    23. }

    好的，从上面代码可以看出，确实是这么个关系，过。

    HashMap的散列算法

    散列算法的定义在第一段的时候已经说过了。就是根据hashcode计算index的方法。其实就是hashcode到index的映射。

    一般映射方法也可以选用取余，即

    index = hash % array.length

    但是使用位运算会相对更迅速。因为数组长度会选择为2^n。所以当2^n-1以后，相当于一个n-1位的二进制全为1。这也是为什么数组长度需要是2^n的原因。

    那么hash & (array.length - 1)就相当于取hash值二进制的后n-1位。

    index = hash & (array.length - 1)

    举个栗子：

    假如数组长度为2^4 = 16，计算出来的hash值是01XXXXXXX1110，这时候通过2^4-1=15，转化为二进制为1111

    hash & (array.length-1) 就可以只取hash值的后四位，并且index一定是< array.length的。

    这种方法，既保证了速率，又保证了数组不越界，简直完美。

    下面这个图是这个散列算法对应的代码。

    HashMap重要方法讲解

    HashMap.put

    put方法，前面说过，实际就是新建一个node放到key对应的index位置上去。如果存在哈希冲突（即index上已经有node了），就创建链表，必要时，将链表转成红黑树。

    看下实际的代码

    1. // HashMap.java
    2. public V put(K key, V value) {
    3.     return putVal(hash(key), key, value, false, true);// 对key求hash
    4. }
    5.  
    6. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    7.                boolean evict) {
    8.     Node<K,V>[] tab; Node<K,V> p; int n, i;
    9.     if ((tab = table) == null || (n = tab.length) == 0)// table为空，则新建一个table
    10.         n = (tab = resize()).length;
    11.     if ((p = tab[i = (n - 1) & hash]) == null)// 如果table[i] == null，直接新建一个节点
    12.         tab[i] = newNode(hash, key, value, null);// 这个情况下e == null，后面mod++,resize
    13.     else {
    14.         Node<K,V> e; K k;
    15.         if (p.hash == hash &&
    16.             ((k = p.key) == key || (key != null && key.equals(k))))// 如果key相同，替换
    17.             e = p;
    18.         else if (p instanceof TreeNode) // 如果是树节点，putTree
    19.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    20.         else {// 否则，是一个链表
    21.             for (int binCount = 0; ; ++binCount) {
    22.                 if ((e = p.next) == null) {// 如果找到链表的最后都还没有找到这个key，这里也会导致e==null
    23.                     p.next = newNode(hash, key, value, null);// 就新建一个节点
    24.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st，
    25.                     // 建完节点后，看链表的节点有没有超过阈值，默认TREEIFY_THRESHOLD=8
    26.                         treeifyBin(tab, hash);
    27.                     break;
    28.                 }
    29.                 if (e.hash == hash &&
    30.                     ((k = e.key) == key || (key != null && key.equals(k))))
    31.                     // 找到之后，找到的节点e 
    32.                     break;
    33.                 p = e;
    34.             }
    35.         }
    36.         if (e != null) { // existing mapping for key-->这里意味着map当中存在这个key，只要map存在这个key，size就不会++
    37.             V oldValue = e.value;
    38.             if (!onlyIfAbsent || oldValue == null)
    39.                 e.value = value;// 链表中找到的节点，在这里替换成新的值，直接替换，所以不
    40.                 // 会走resize
    41.             afterNodeAccess(e);// 这个是给LinkedHashMap用的，存在这个key，调用afterNodeAccess，不存在，就调用下面的afterNodeInsertion
    42.             return oldValue;
    43.         }
    44.     }
    45.     ++modCount;
    46.     if (++size > threshold)
    47.         resize();
    48.     afterNodeInsertion(evict);
    49.     return null;
    50. }

    所以对上面的代码做一个总结就是：

    • put值的时候，如果发现table == null，就调用resize方法创建table（所以HashMap是实现了延迟初始化的）
    • 对key进行hash ，
      • i = (n-1)&hash（hash->index的映射）
      • if (table[i] == null) newNode ; ++modCount;++Size; // 该索引为空，不需要处理hash冲突，直接创建一个新节点
      • if (table[i] != null && table[i].key == key) {table[i].value = value} // 该索引不为空，但是key刚好相同，直接替换
      • else if (table[i] != null && table[i].key != key)
        • 则if (table[i] instanceOf TreeNode) sourceTree() // 如果node.next指向的是一颗红黑树，直接遍历树，如果新创建了节点++size,++modCount
        • 否则table[i]指向的是一个链表，进行链表的遍历
        • 如果链表循环到尾节点，也找不到，则newNode
          • if (list.length > TREEIFY_THRESHOLD) {treeify(); }// treeify_threshold=8
          • ++modCount;++size;
        • 找到，则直接替换
    • if(size > threshold) resize(); // 总的来说就是，只要新建节点，且size > 阈值，就会触发扩容。

    再次总结一下put方法

    1. HashMap会在put的时候才创建table，即延迟初始化。
    2. 在遍历key的过程中，如果有相同的key，就直接替换value。如果没有，就新创建一个Node，并且modCount++，size++
    3. 如果最后检验到size > threshold，则进行数组的扩容。

    (这个图画得太好了，引用一下)

    图来源：Java 8系列之重新认识HashMap - 美团技术团队

    从上面的总结可以看出，HashMap另一个重要的方法，就是扩容。所以...

    HashMap.resize

    对于扩容，前面说过，扩容是为了减少哈希冲突，提升查询效率。

    那么扩容的过程应该是怎样的？很容易想到，扩容就是扩大数组的大小。扩大大小的话，又不能在原来数组上追加，那就只好新建一个更大的数组了。那建更大的数组，原来数组的元素怎么办呢？它们应该移到新数组的哪个位置上去？

     扩容之后，计算原数组中的元素（包括链表及树）在新数组中的位置的过程称为rehash。

    原数组的index计算过程为

    index = hash(key) & (arr.length - 1)

    那么新数组扩容2倍之后，按道理hash的过程是不应该变的。确实，rehash的方法没变，但是速度上可以做提升吗？

    我们知道，原数组长度为16，对应二进制10000，取的index为hash值的后4位。扩容两倍后，原数组长度变成32，对应二进制100000，arr.length - 1为11111。即取hash值后5位。

    比如hash值计算出来为000..11011。那原数组计算出来的index为1011。新的数组index为11011。

    11011 = 1011+10000

    这里的10000就是原数组的长度。即newIndex = oldIndex + oldArr.length

    但如果hash计算出来为000...01011。这时候newIndex = oldIndex + 0

    从上面的推导过程可以推出一个结论：

    newIndex = oldIndex + (hash & oldArr.length == 0? 0 : oldArr.length)

    明白这一点，就很容易看懂源码了。

    1. final Node<K,V>[] resize() {
    2.     Node<K,V>[] oldTab = table;
    3.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
    4.     int oldThr = threshold;
    5.     int newCap, newThr = 0;
    6.     if (oldCap > 0) {
    7.         if (oldCap >= MAXIMUM_CAPACITY) {// 如果扩容前table长度已经大于MAX_VALUE,不创建
    8.             threshold = Integer.MAX_VALUE;
    9.             return oldTab;
    10.         }
    11.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
    12.                  oldCap >= DEFAULT_INITIAL_CAPACITY)// DEFAULT_INICIAL_CAPACITY = 16
    13.                  // 初始table的容量
    14.             newThr = oldThr << 1; // double threshold
    15.     }// threshold*2,capacity * 2
    16.     else if (oldThr > 0) // initial capacity was placed in threshold
    17.         newCap = oldThr;
    18.     else {               // zero initial threshold signifies using defaults
    19.         newCap = DEFAULT_INITIAL_CAPACITY;
    20.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    21.     }
    22.     if (newThr == 0) {
    23.         float ft = (float)newCap * loadFactor;
    24.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
    25.                   (int)ft : Integer.MAX_VALUE);
    26.     }
    27.     /**这里往前都是值的初始化，即所有的值放大成原来的两倍，往下才是数组的迁移过程**/
    28.     threshold = newThr;
    29.     @SuppressWarnings({"rawtypes","unchecked"})
    30.     // 创建一个新的数组了
    31.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    32.     table = newTab;
    33.     if (oldTab != null) {
    34.         for (int j = 0; j < oldCap; ++j) {// 遍历旧数组，开始进行元素迁移
    35.             Node<K,V> e;
    36.             if ((e = oldTab[j]) != null) {
    37.                 oldTab[j] = null;
    38.                 if (e.next == null)// 如果链表只有一个值，直接新建一个node
    39.                     newTab[e.hash & (newCap - 1)] = e;
    40.                 else if (e instanceof TreeNode)// 树节点
    41.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
    42.                 else { // preserve order 链表，保持链表的顺序
    43.                     // loHead,loTail可以理解为在j位置链表的head和tail(lo代指low)
    44.                     Node<K,V> loHead = null, loTail = null;
    45.                     // hiHead,hiTail可以理解为在j+oldLength位置链表的head和tail(hi代指high)
    46.                     Node<K,V> hiHead = null, hiTail = null;
    47.                     Node<K,V> next;
    48.                     do {
    49.                         next = e.next;
    50.                         // 以下这段if else即为rehash,重新计算Node在新table中的索引
    51.                         if ((e.hash & oldCap) == 0) {// 构建将在j位置的链表
    52.                             if (loTail == null)
    53.                                 loHead = e;
    54.                             else
    55.                                 loTail.next = e;
    56.                             loTail = e;
    57.                         }
    58.                         else {// 构建将在j+oldLength位置的链表
    59.                             if (hiTail == null)
    60.                                 hiHead = e;
    61.                             else
    62.                                 hiTail.next = e;
    63.                             hiTail = e;
    64.                         }
    65.                     } while ((e = next) != null);// 循环遍历原链表
    66.                     if (loTail != null) {// 将链表放进相应的位置
    67.                         loTail.next = null;
    68.                         newTab[j] = loHead;
    69.                     }
    70.                     if (hiTail != null) {
    71.                         hiTail.next = null;
    72.                         newTab[j + oldCap] = hiHead;
    73.                     }
    74.                 }
    75.             }
    76.         }
    77.     }
    78.     return newTab;
    79. }

    总结一下扩容的过程：

    • 如果table == null，创建初始长度为16，阈值为12的table
    • 如果table != null，则扩容为原来的2倍，threshold也扩充为原来的2倍。
    • 对table元素进行遍历
      • 如果table[i].next == null，直接获取newIndex ，newTab[e.hash & (newCap - 1)] = e;
      • 如果table[i] == 树结构，.....
      • 如果table[i] == 链表，遍历链表
        • 获取链表中的node在新table中的位置（通过e.hash & oldCap）
          • 如果e.hash & oldCap == 0，则在新table中的位置为i
            • 将node放入loHead链表中
          • 如果e.hash & oldCap == 1，则在新table中的位置为i+oldCap
            • 将node放入hiHead链表中
      • 将loHead放入table[i]
      • 将hiHead放入table[i+oldLength]中

    为什么hashMap不支持并发

    后端---java中hashmap多线程并发问题详解_lbxxzt的博客-CSDN博客_hashmap多线程读

    老生常谈，HashMap的死循环 - 简书

    1.7中HashMap死循环分析 - 知乎

    HashMap在jdk1.8以前会在get的时候触发死循环，原因是putVal的时候多线程resize的时候会导致循环链表

    在jdk1.8及之后，会在treeify方法的时候触发死循环。

    并发-HashMap在jdk1.8也会出现死循环 - xuwc - 博客园

    HashMap死循环分析

    关于HashMap的遍历顺序

    要看遍历顺序，重要的就是看构建的Iterator。

    1. abstract class HashIterator {
    2.     Node<K,V> next;        // next entry to return
    3.     Node<K,V> current;     // current entry
    4.     int expectedModCount;  // for fast-fail
    5.     int index;             // current slot
    6.  
    7.     HashIterator() {
    8.         expectedModCount = modCount;
    9.         Node<K,V>[] t = table;
    10.         current = next = null;
    11.         index = 0;
    12.         if (t != null && size > 0) { // advance to first entry
    13.         // 因为HashMap是hash->index映射，并不是按顺序存储Node的，
    14.         //所以，会出现，某些index没有Node的情况
    15.         // 所以初始化的时候,寻找table中第一个不为空的节点
    16.             do {} while (index < t.length && (next = t[index++]) == null);
    17.         }
    18.     }
    19.  
    20.     public final boolean hasNext() {
    21.         return next != null;
    22.     }
    23.  
    24.     final Node<K,V> nextNode() {
    25.         Node<K,V>[] t;
    26.         Node<K,V> e = next;
    27.         if (modCount != expectedModCount)
    28.             throw new ConcurrentModificationException();
    29.         if (e == null)
    30.             throw new NoSuchElementException();
    31.         // 获取e.next，如果e.next!= null，则设置next = e.next，返回e
    32.         // 如果e.next == null，证明这个index对应的链表或树已经遍历完毕，寻找下一个不为空的index节点
    33.         if ((next = (current = e).next) == null && (t = table) != null) {
    34.             do {} while (index < t.length && (next = t[index++]) == null);
    35.         }
    36.         return e;
    37.     }
    38.  
    39.     public final void remove() {
    40.         Node<K,V> p = current;
    41.         if (p == null)
    42.             throw new IllegalStateException();
    43.         if (modCount != expectedModCount)
    44.             throw new ConcurrentModificationException();
    45.         current = null;
    46.         K key = p.key;
    47.         removeNode(hash(key), key, null, false, false);
    48.         expectedModCount = modCount;
    49.     }
    50. }

    还是这张熟悉的图，如果按HashMap的遍历顺序，那遍历的顺序就应该是：

    1. 先找到第一个不为空的Node，即Node1。（即在HashIterator的构造函数中干的事。）
    2. 先遍历完Node1对应的树。如果遍历完Node1对应的树之后，开始寻找下一个table[index]!=null的节点。即Node6。这是HashIterator中的nextNode方法干的事。
    3. 接着开始遍历Node6对应的链表，即node7,node10。

    所以可以得出结论，因为HashMap的插入是没有顺序的，所以HashMap的遍历也是没有顺序的。

    最后的最后，可能会有人问，假如我想使用一个可以记录插入顺序的HashMap呢？

    答案就是LinkedHashMap。

    下一篇讲解为什么LinkedHashMap可以记录插入顺序。

  • 相关阅读:
    docker 部署多个前端vue项目
    还在手动发包？手把手教你 Jenkins 自动化部署SpringBoot
    Vue3 复制 copy 功能实现（vue-clipboard3）
    蓝桥杯成绩已出
    window下Vscode配置 git 为终端
    当下IT测试技术员的求职困境
    预告篇：利用现学知识实现一个shell
    桌面运维类面试非技术问题
    ESP32设备通信-Mesh网络通信
    记一次简单的网络通信遇到的问题点总结
  • 原文地址：https://blog.csdn.net/yolan6824/article/details/125456353