HashMap JDK8 源码分析

朱雀 2022-12-30 08:13 187阅读 0赞

### 概述 ###

HashMap是基于哈希表(散列表)，实现Map接口的双列集合，数据结构是“链表散列”，也就是数组+链表 ，key唯一的value可以重复，允许存储null 键null 值，元素无序。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证顺序。

值得注意的是HashMap不是线程安全的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。

### 数据结构 ###

在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，hashmap也不例外。Hashmap实际上是一个数组和链表的结合体（在数据结构中，一般称之为“链表散列“），如图（竖排表示数组，横排表示数组元素【实际上是一个链表】）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjcwMTA2_size_16_color_FFFFFF_t_70][]

图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中的第一个位置。  
在JDK8中 又有了新的优化。桶中的元素不再唯一按照链表组合，也可以使用红黑树进行存储

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjcwMTA2_size_16_color_FFFFFF_t_70 1][]

### 源码分析 ###

> public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

> public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable \{  
>     // 序列号  
>     private static final long serialVersionUID = 362498820763181265L;      
>     // 默认的初始容量是16  
>     static final int DEFAULT\_INITIAL\_CAPACITY = 1 << 4;     
>     // 最大容量  
>     static final int MAXIMUM\_CAPACITY = 1 << 30;   
>     // 默认的填充因子  
>     static final float DEFAULT\_LOAD\_FACTOR = 0.75f;  
>     // 当桶(bucket)上的结点数大于这个值时会转成红黑树  
>     static final int TREEIFY\_THRESHOLD = 8;   
>     // 当桶(bucket)上的结点数小于这个值时树转链表  
>     static final int UNTREEIFY\_THRESHOLD = 6;  
>     // 桶中结构转化为红黑树对应的table的最小大小  
>     static final int MIN\_TREEIFY\_CAPACITY = 64;  
>     // 存储元素的数组，总是2的幂次倍  
>     transient Node<k,v>\[\] table;   
>     // 存放具体元素的集  
>     transient Set<map.entry<k,v>> entrySet;  
>     // 存放元素的个数，注意这个不等于数组的长度。  
>     transient int size;  
>     // 每次扩容和更改map结构的计数器  
>     transient int modCount;     
>     // 临界值 当实际大小(容量\*填充因子)超过临界值时，会进行扩容  
>     int threshold;  
>     // 填充因子  
>     final float loadFactor;  
> \}

### HashMap结构 ###

JDK 7

>       /\*\* Entry是单向链表。      
>      \* 它是 “HashMap链式存储法”对应的链表。      
>      \*它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数    
>     \*\*/   
> 
>     transient Entry\[\] table;  
> 
>     static class Entry<K,V> implements Map.Entry<K,V> \{    
>         final K key;    
>         V value;    
>         // 指向下一个节点     
>         Entry<K,V> next;    
>         final int hash;    
>         // 构造函数。      
>         // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"      
>         Entry(int h, K k, V v, Entry<K,V> n) \{      
>             value = v;      
>             next = n;      
>             key = k;      
>             hash = h;      
>         \}     
>     \}

JDK 8

> /\*\* Node是单向链表。      
>      \* 它是 “HashMap链式存储法”对应的链表。      
>      \*它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数    
>     \*\*/    
>  static class Node<K,V> implements Map.Entry<K,V> \{  
>         final int hash;  
>         final K key;  
>         V value;  
>         Node<K,V> next;
> 
>         Node(int hash, K key, V value, Node<K,V> next) \{  
>             this.hash = hash;  
>             this.key = key;  
>             this.value = value;  
>             this.next = next;  
>         \}  
>         ．．．
> 
> //红黑树节点    
>     static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> \{  
>         TreeNode<K,V> parent;  // red-black tree links  
>         TreeNode<K,V> left;  
>         TreeNode<K,V> right;  
>         TreeNode<K,V> prev;    // needed to unlink next upon deletion  
>         boolean red;  
>         TreeNode(int hash, K key, V val, Node<K,V> next) \{  
>             super(hash, key, val, next);  
>         \}
> 
>         /\*\*  
>          \* Returns root of tree containing this node.  
>          \*/  
>         final TreeNode<K,V> root() \{  
>             for (TreeNode<K,V> r = this, p;;) \{  
>                 if ((p = r.parent) == null)  
>                     return r;  
>                 r = p;  
>             \}  
>         \}

### 构造函数 ###

public HashMap()

> public HashMap() \{  
>     // 初始化填充因子  
>     this.loadFactor = DEFAULT\_LOAD\_FACTOR;   
> \}

HashMap(int initialCapacity)

> public HashMap(int initialCapacity) \{  
>     // 调用HashMap(int, float)型构造函数  
>     this(initialCapacity, DEFAULT\_LOAD\_FACTOR);  
> \}

public HashMap(Map)

> public HashMap(Map<? extends K, ? extends V> m) \{  
>     // 初始化填充因子  
>     this.loadFactor = DEFAULT\_LOAD\_FACTOR;  
>     // 将m中的所有元素添加至HashMap中  
>     putMapEntries(m, false);  
> \}

注意：在hashMap中数组的大小都是默认指定为2的４次幂，以后容量也是２的ｎ次幂。具体原因，下面putVal方法介绍。

> 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为空就创建  
>         if ((tab = table) == null || (n = tab.length) == 0)  
>             n = (tab = resize()).length;  
>         //确定插入table的位置，算法是(n - 1) & hash  
>         if ((p = tab\[i = (n - 1) & hash\]) == null)  
>             tab\[i\] = newNode(hash, key, value, null);  
>         //在table的i位置发生碰撞，有两种情况，1、key值是一样的，替换value值，  
>         //2、key值不一样的有两种处理方式：2.1、存储在i位置的链表；2.2、存储在红黑树中  
>         else \{  
>             Node<K,V> e; K k;  
>             if (p.hash == hash &&  
>                 ((k = p.key) == key || (key != null && key.equals(k))))  
>                 e = p;  
>             //2.2  
>             else if (p instanceof TreeNode)  
>                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  
>             //2.1  
>             else \{  
>                 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;  
>                 \}  
>             \}  
>             //如果e不为空就替换旧的oldValue值  
>             if (e != null) \{ // existing mapping for key  
>                 V oldValue = e.value;  
>                 if (!onlyIfAbsent || oldValue == null)  
>                     e.value = value;  
>                 afterNodeAccess(e);  
>                 return oldValue;  
>             \}  
>         \}  
>         ++modCount;  
>         //threshold=newThr:(int)(DEFAULT\_LOAD\_FACTOR \* DEFAULT\_INITIAL\_CAPACITY);  
>         //默认0.75\*16，大于threshold值就扩容  
>         if (++size > threshold)  
>             resize();  
>         afterNodeInsertion(evict);  
>         return null;  
>     \}

### Hash算法： ###

得到hash值

> static final int hash(Object key) \{  
>         int h;  
>         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  
>     \}

解释：  
h>>16:  
得到通过h=key.hashCode()方法计算key的hashcode的值，通过计算出的hashcode的值向右移动16位，使原有的hashcode的值的高16位变低16位，高16位则统一都变为0。  
异或运算：(h = key.hashCode()) ^ (h >>> 16)

原 来 的 hashCode : 1111 1111 1111 1111 0100 1100 0000 1010  
移位后的hashCode: 0000 0000 0000 0000 1111 1111 1111 1111  
进行异或运算 结果：1111 1111 1111 1111 1011 0011 1111 0101

这样做的好处是，可以将hashcode高位和低位的值进行混合做异或运算，而且混合后，低位的信息中加入了高位的信息，这样高位的信息被变相的保留了下来。掺杂的元素多了，那么生成的hash值的随机性会增大。

获取位置：  
接着我们看该重新产生的hashcode应该对应的位置。

源码中模运算是在这个indexFor( )函数里完成的。

> bucketIndex = indexFor(hash, table.length);

indexFor的代码也很简单，就是把散列值和数组长度做一个”与”操作

> static int indexFor(int h, int length) \{  
>         return h & (length-1);  
> \}

顺便说一下，这也正好解释了为什么HashMap的数组长度要取2的整次幂。因为这样（数组长度-1）正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值“与”操作如下，结果就是截取了最低的四位值。

>         10100101 11000100 00100101  
>  &      00000000 00000000 00001111  
>  ----------------------------------  
>         00000000 00000000 00000101    //高位全部归零，只保留末四位

整个流程如下:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjcwMTA2_size_16_color_FFFFFF_t_70 2][]

这样我们已经得到了该元素的在数组中的位置。 在put时，由于根据的是hashcode来put元素的,假如当前数组位置已经存在元素，则会通过链表形式在该位置追加元素。（jdk7）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjcwMTA2_size_16_color_FFFFFF_t_70 3][]

在JDK8中，有所改进的是，当加入链表元素的数量达到某固定值时，则改为红黑树结构存储。

> //put(K key,V value)函数   
>   public V put(K key, V value) \{  
>           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;  
>        //如果table为空或者长度为0，则resize()  
>        if ((tab = table) == null || (n = tab.length) == 0)  
>            n = (tab = resize()).length;  
>        //找到key值对应的槽并且是第一个，直接加入  
>        if ((p = tab\[i = (n - 1) & hash\]) == null)  
>            tab\[i\] = newNode(hash, key, value, null);  
>        else \{  
>                Node<K,V> e;  
>                K k;  
>                //第一个node的hash值即为要加入元素的hash  
>                if (p.hash == hash &&  
>                    ((k = p.key) == key || (key != null && key.equals(k))))\{  
>                     e = p;  
>                \}else if (p instanceof TreeNode)//第一个节点是TreeNode，即tree-bin  
>                   /\*Tree version of putVal.  
>                    \*final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>\[\] tab,int h, K k, V v)  
>                  e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  
>                      else \{  
>                          //不是TreeNode,即为链表,遍历链表  
>                          for (int binCount = 0; ; ++binCount) \{  
>                              /\*到达链表的尾端也没有找到key值相同的节点，  
>                               \*则生成一个新的Node,并且判断链表的节点个数是不是到达转换成红黑树的上界  
>                                \*达到，则转换成红黑树  
>                                \*/  
>                               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);  
>                      //返回旧的value值  
>                      return oldValue;  
>                  \}  
>          \}  
>          ++modCount;  
>          if (++size > threshold)  
>              resize();  
>          afterNodeInsertion(evict);  
>          return null;  
> \}

## 扩容： ##

> final Node<K,V>\[\] resize() \{  
>     // 当前table保存  
>     Node<K,V>\[\] oldTab = table;  
>     // 保存table大小  
>     int oldCap = (oldTab == null) ? 0 : oldTab.length;  
>     // 保存当前阈值   
>     int oldThr = threshold;  
>     int newCap, newThr = 0;  
>     // 之前table大小大于0  
>     if (oldCap > 0) \{  
>         // 之前table大于最大容量  
>         if (oldCap >= MAXIMUM\_CAPACITY) \{  
>             // 阈值为最大整形  
>             threshold = Integer.MAX\_VALUE;  
>             return oldTab;  
>         \}  
>         // 容量翻倍，使用左移，效率更高  
>         else if ((newCap = oldCap << 1) < MAXIMUM\_CAPACITY &&  
>             oldCap >= DEFAULT\_INITIAL\_CAPACITY)  
>             // 阈值翻倍  
>             newThr = oldThr << 1; // double threshold  
>     \}  
>     // 之前阈值大于0  
>     else if (oldThr > 0)  
>         newCap = oldThr;  
>     // oldCap = 0并且oldThr = 0，使用缺省值（如使用HashMap()构造函数，之后再插入一个元素会调用resize函数，会进入这一步）  
>     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"\})  
>     // 初始化table  
>     Node<K,V>\[\] newTab = (Node<K,V>\[\])new Node\[newCap\];  
>     table = newTab;  
>     // 之前的table已经初始化过  
>     if (oldTab != null) \{  
>         // 复制元素，重新进行hash  
>         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  
>                     Node<K,V> loHead = null, loTail = null;  
>                     Node<K,V> hiHead = null, hiTail = null;  
>                     Node<K,V> next;  
>                     // 将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割，分成两个不同的链表，完成rehash  
>                     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;  
> \}

说明：进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。

在resize前和resize后的元素布局如下

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjcwMTA2_size_16_color_FFFFFF_t_70 4][]

说明：上图只是针对了数组下标为2的桶中的各个元素在扩容后的分配布局，其他各个桶中的元素布局可以以此类推。　从putVal源代码中我们可以知道，当插入一个元素的时候size就加1，若size大于threshold的时候，就会进行扩容。假设我们的capacity大小为32，loadFator为0.75,则threshold为24 = 32 \* 0.75，此时，插入了25个元素，并且插入的这25个元素都在同一个桶中，桶中的数据结构为红黑树，则还有31个桶是空的，也会进行扩容处理，其实，此时，还有31个桶是空的，好像似乎不需要进行扩容处理，但是是需要扩容处理的，因为此时我们的capacity大小可能不适当。我们前面知道，扩容处理会遍历所有的元素，时间复杂度很高；前面我们还知道，经过一次扩容处理后，元素会更加均匀的分布在各个桶中，会提升访问效率。所以，说尽量避免进行扩容处理，也就意味着，遍历元素所带来的坏处大于元素在桶中均匀分布所带来的好处。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjcwMTA2_size_16_color_FFFFFF_t_70]: /images/20221120/7862405d98084452979960dbbe732afa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjcwMTA2_size_16_color_FFFFFF_t_70 1]: /images/20221120/287d6f85adfb410e819e7735a737800f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjcwMTA2_size_16_color_FFFFFF_t_70 2]: /images/20221120/39d5bd67d96a4ee3833e0e57181e2063.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjcwMTA2_size_16_color_FFFFFF_t_70 3]: /images/20221120/941708cb2cd547719a16c2decfd33006.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjcwMTA2_size_16_color_FFFFFF_t_70 4]: /images/20221120/c1f7c72b12a749db8192206da41ce2f0.png