HashMap 深入学习

以你之姓@ 2022-05-06 13:46 293阅读 0赞

**目录**

# 什么是 HashMap，有什么特点？ #

**目录**

什么是 HashMap，有什么特点？

HashMap 的put、get 的工作原理是什么？

JDK1.8源码中的 put 方法

执行流程图

put流程源码

有几个关键点：

1. 如何确定存储位置 index?

2. 什么时候需要扩容？

3. 扩容具体流程（resize）（https://www.jianshu.com/p/9ea8dd8dd40c）

两个关键点

1. 扩容后的数组长度为原来的 2 倍

2. 扩容后链表在新数组中的索引如何确定？

JDK1.8源码中的 get 方法

源码

总结

常见的 hashMap 面试题（见文末）

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

官方文档：

![70][]

HashMap 这样的一个集合类：

支持 key-value 存储形式，

允许key 和 value 都为 null，

不支持同步，

不能保证数据有序（因为通过 hash 函数算得 hashAddress - 存储地址）、

也不能保证数据的顺序随着时间变换而保持不变（由于扩容时需要 reHash - 重新计算 hashAddress）。

底层采用的数据结构是哈希表，解决hash冲突的办法是拉链法（hash冲突、拉链法[了解一下][Link 1]）。如下图

![20161027004004320][]

拉链法将所有冲突的数据存储在同一个链表中，并且将这些链表的表头指针存放在链表数组（链表数组中的数据是链表，就跟 int 数组中的数据是 int 值类似）中。

# HashMap 的put、get 的工作原理是什么？ #

## JDK1.8源码中的 put 方法 ##

### 执行流程图 ###

![Image 1][]

## put流程源码 ##

public V put(K key, V value) {
        // hash(key)：对key的hashCode()做hash
        return putVal(hash(key), key, value, false, true);
    }
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // tab（链表数组）为空则创建
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 计算index，并对null做处理
        if ((p = tab[i = (n - 1) & hash]) == null)
            //当前 index 还没有数据，所以需要新建一个链，并把链头指针（引用）存放到index处
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // 节点已存在
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 该链为树
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 该链为链表
            else {
                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
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //指针后移
                    p = e;
                }
            }
            // 写入
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 超过load factor*current capacity，resize
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

### 有几个关键点： ###

### 1. 如何确定存储位置 index? ###

从源码可知，是通过 hash(key) & (n-1) 来确定索引位置的，其中 n 为链表数组的长度。

hash(key) 源码如下

static final int hash(Object key) {
            int h;
            //计算出 key 的 hashCode() 值 h, 再和 h 右移 16 位之后的值进行异或操作
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

hash(key) & (n-1)实例：

### ![70 1][] ###

在计算 hash 的时候，为什么要把 hash 与 hash 的右移 16 位的值进行异或操作？

由于链表数组的容量都是 2 的 n 次方，且元素的 hashCode() 在很多时候下低位是相同的，这样在计算 index 的时候很容易产生冲突。所以为了减少冲突，需要把元素 hashCode() 值的高 16 位 参与到 hash 值的计算中来，于是就有了 (h = key.hashCode()) ^ (h >>> 16) 的操作。

### 2. 什么时候需要扩容？ ###

当 键值对 的数据量超过 指定的 阀值=加载因子\*初始链表数组长度 是需要扩容

### 3. 扩容具体流程（resize）（[https://www.jianshu.com/p/9ea8dd8dd40c][https_www.jianshu.com_p_9ea8dd8dd40c]） ###

final Node<K,V>[] resize() {
       // oldTab 指向旧的 table 表
       Node<K,V>[] oldTab = table;
       // oldCap 代表扩容前 table 表的数组长度，oldTab 第一次添加元素的时候为 null 
       int oldCap = (oldTab == null) ? 0 : oldTab.length;
       // 旧的扩容阈值
       int oldThr = threshold;
       // 初始化新的阈值和容量
       int newCap, newThr = 0;
       // 如果 oldCap > 0 则会将新容量扩大到原来的2倍，扩容阈值也将扩大到原来阈值的两倍
       if (oldCap > 0) {
           // 如果旧的容量已经达到最大容量 2^30 那么就不在继续扩容直接返回，将扩容阈值设置到 Integer.MAX_VALUE，并不代表不能装新元素，只是数组长度将不会变化
           if (oldCap >= MAXIMUM_CAPACITY) {
               threshold = Integer.MAX_VALUE;
               return oldTab;
           }//新容量扩大到原来的2倍，扩容阈值也将扩大到原来阈值的两倍
           else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
               newThr = oldThr << 1; // double threshold
       }
       //oldThr 不为空，代表我们使用带参数的构造方法指定了加载因子并计算了
       //初始初始阈值 会将扩容阈值 赋值给初始容量这里不再是期望容量，
       //但是 >= 指定的期望容量
       else if (oldThr > 0) // initial capacity was placed in threshold
           newCap = oldThr;
       else {
            // 空参数构造会走这里初始化容量，和扩容阈值 分别是 16 和 12
           newCap = DEFAULT_INITIAL_CAPACITY;
           newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
       }
       //如果新的扩容阈值是0，对应的是当前 table 为空，但是有阈值的情况
       if (newThr == 0) {
            //计算新的扩容阈值
           float ft = (float)newCap * loadFactor;
           // 如果新的容量不大于 2^30 且 ft 不大于 2^30 的时候赋值给 newThr 
           //否则 使用 Integer.MAX_VALUE
           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<K,V> e;//用来存储对应数组位置链表头节点
               //如果当前数组位置存在元素
               if ((e = oldTab[j]) != null) {
                    // 释放原来数组中的对应的空间
                   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 { // preserve order
                       //因为扩容是容量翻倍，
                       //原链表上的每个节点 现在可能存放在原来的下标，即low位，
                       //或者扩容后的下标，即high位
                  //低位链表的头结点、尾节点
                  Node<K,V> loHead = null, loTail = null;
                  //高位链表的头节点、尾节点
                  Node<K,V> hiHead = null, hiTail = null;
                  Node<K,V> next;//用来存放原链表中的节点
                  do {
                      next = e.next;
                      // 利用哈希值 & 旧的容量，可以得到哈希值去模后，
                      //是大于等于 oldCap 还是小于 oldCap，
                      //等于 0 代表小于 oldCap，应该存放在低位，
                      //否则存放在高位（稍后有图片说明）
                      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);
                  //将低位链表存放在原index处，
                  if (loTail != null) {
                      loTail.next = null;
                      newTab[j] = loHead;
                  }
                  //将高位链表存放在新index处
                  if (hiTail != null) {
                      hiTail.next = null;
                      newTab[j + oldCap] = hiHead;
                  }
               }
           }
       }
       return newTab;
    }

### 两个关键点 ###

### 1. 扩容后的数组长度为原来的 2 倍 ###

### 2. 扩容后链表在新数组中的索引如何确定？ ###

扩容后链表在新的链表数组中的 index 为 “原位置 x” 或者 “x+old链表数组长度”。下面是详细解释

> 图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

![Image 2][]

image

> 元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

![Image 2][]

image

> 所以在 JDK1.8 中扩容后，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap

## JDK1.8源码中的 get 方法 ##

## 源码 ##

public V get(Object key) {
       Node<K,V> e;
       //通过 getNode寻找 key 对应的 Value 如果没找到，或者找到的结果为 null 就会返回null 否则会返回对应的 Value
       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;
       //现根据 key 的 hash 值去找到对应的链表或者红黑树
       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);
                //遍历单链表找到对应的 key 和 Value   
               do {
                   if (e.hash == hash &&
                       ((k = e.key) == key || (key != null && key.equals(k))))
                       return e;
               } while ((e = e.next) != null);
           }
       }
       return null;
    }
    
    作者：醒着的码者
    链接：https://www.jianshu.com/p/9ea8dd8dd40c
    來源：简书
    简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。

get方法整体流程相较于 put 简单了很多。主要的逻辑就是：

1. 确定 key 在链表数组的 index

2. 遍历链表，查找指定的 key 对应的 value 值

# 总结 #

## [常见的 hashMap 面试题（见文末）][hashMap] ##

Thanks:

[https://www.jianshu.com/p/9ea8dd8dd40c][https_www.jianshu.com_p_9ea8dd8dd40c]

[https://blog.csdn.net/u011240877/article/details/53358305][https_blog.csdn.net_u011240877_article_details_53358305]

[http://openjdk.java.net/jeps/180][http_openjdk.java.net_jeps_180]

[70]: /images/20220506/56d6077202a64eb3a2eda3c8628e3b83.png
[Link 1]: https://blog.csdn.net/u011240877/article/details/52940469
[20161027004004320]: /images/20220506/dfce700a86a74f878f66a90429b96896.png
[Image 1]: /images/20220506/8e42bfe5b02344cfa46be5471eaf52c9.png
[70 1]: /images/20220506/e147e12c7dbf40a8a6ad425ec04bc55c.png
[https_www.jianshu.com_p_9ea8dd8dd40c]: https://www.jianshu.com/p/9ea8dd8dd40c
[Image 2]: 
[hashMap]: https://www.zybuluo.com/kiraSally/note/819843
[https_blog.csdn.net_u011240877_article_details_53358305]: https://blog.csdn.net/u011240877/article/details/53358305
[http_openjdk.java.net_jeps_180]: http://openjdk.java.net/jeps/180