HashMap底层源码与数据结构分析(JDK1.8)

一、简介

JDK1.8中HashMap采用的是数组+链表结构+红黑树保存所有数据

HashMap主要用于存放键值对，它基于哈希表的Map接口实现，是常用的 Java 集合之一，是非线程安全的。

HashMap可以存储null的key和value，但是null作为键只能有一个，null作为值可以有很多个。

JDK1.8之前HashMap由数组 + 链表构成，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（"拉链法"解决冲突）。JDK1.8以后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）（将链表转换为红黑树前会判断，如果当前数组的长度小于64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

HashMap默认的初始化大小为16，之后每次扩充，容量变为原来的2倍。并且，HashMap总是使用2的幂作为哈希表的大小。

二、底层数据结构分析

JDK1.8之后

相比于之前的版本，JDK1.8 以后在解决哈希冲突时有了较大的变化。

当链表长度大于阈值（默认为 8）时，会首先调用 treeifyBin()方法。这个方法会根据 HashMap 数组来决定是否转换为红黑树。只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是执行 resize() 方法对数组扩容。相关源码这里就不贴了，重点关注 treeifyBin()方法即可！

类的属性：

 /**
      * 默认初始化容量为16
      */
     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 ​
     /**
      * 默认最大的容量, 2^30
      */
     static final int MAXIMUM_CAPACITY = 1 << 30;
 ​
     /**
      * 负载因子，默认为0.75
      */
     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 java.util.HashMap.Node<K,V>[] table;
 ​
     /**
      * 存放具体元素的集
      */
     transient Set<Map.Entry<K,V>> entrySet;
 ​
     /**
      * 存放元素的个数，注意这个不等于数组的长度
      */
     transient int size;
 ​
     /**
      * 每次扩容和更改map结构的计数器
      */
     transient int modCount;

 

  • loadFactor 加载因子

    loadFactor 加载因子是控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0，数组中存放的数据(entry)也就越少，也就越稀疏。

    loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。

    给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

  • threshold

    threshold = capacity * loadFactor，当 Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。

Node节点

 static class Node<K,V> implements Map.Entry<K,V> {
         final int hash;
         final K key;
         V value;
         java.util.HashMap.Node<K,V> next;
 ​
         Node(int hash, K key, V value, java.util.HashMap.Node<K,V> next) {
             this.hash = hash;
             this.key = key;
             this.value = value;
             this.next = next;
         }
 ​
         public final K getKey()        { return key; }
         public final V getValue()      { return value; }
         public final String toString() { return key + "=" + value; }
 ​
         public final int hashCode() {
             return Objects.hashCode(key) ^ Objects.hashCode(value);
         }
 ​
         public final V setValue(V newValue) {
             V oldValue = value;
             value = newValue;
             return oldValue;
         }
 ​
         public final boolean equals(Object o) {
             if (o == this)
                 return true;
             if (o instanceof Map.Entry) {
                 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                 if (Objects.equals(key, e.getKey()) &&
                         Objects.equals(value, e.getValue()))
                     return true;
             }
             return false;
         }
     }

树节点类源码

 java.util.HashMap.TreeNode<K,V> parent;  // red-black tree links
         java.util.HashMap.TreeNode<K,V> left;
         java.util.HashMap.TreeNode<K,V> right;
         java.util.HashMap.TreeNode<K,V> prev;    // needed to unlink next upon deletion
         boolean red; // 判断颜色
         TreeNode(int hash, K key, V val, java.util.HashMap.Node<K,V> next) {
             super(hash, key, val, next);
         }
 ​
         /**
          * 返回根节点
          */
         final java.util.HashMap.TreeNode<K,V> root() {
             for (java.util.HashMap.TreeNode<K,V> r = this, p;;) {
                 if ((p = r.parent) == null)
                     return r;
                 r = p;
             }
         }

三、源码分析

构造方法

 /**
      * 指定 “容量大小” 和 “加载因子” 的构造函数
      */
     public HashMap(int initialCapacity, float loadFactor) {
         // 容量小于0，抛出异常
         if (initialCapacity < 0)
             throw new IllegalArgumentException("Illegal initial capacity: " +
                     initialCapacity);
         // 容量大于MAXIMUM_CAPACITY即 2^30
         if (initialCapacity > MAXIMUM_CAPACITY)
             initialCapacity = MAXIMUM_CAPACITY;
         // 判断加载因子
         if (loadFactor <= 0 || Float.isNaN(loadFactor))
             throw new IllegalArgumentException("Illegal load factor: " +
                     loadFactor);
         this.loadFactor = loadFactor;
         this.threshold = tableSizeFor(initialCapacity);
     }
 ​

 /**
      * 指定 “容量大小” 的构造函数
      */
     public HashMap(int initialCapacity) {
         this(initialCapacity, DEFAULT_LOAD_FACTOR);
     }
 /**
      * 无参构造函数
      */
     public HashMap() {
         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
     }

putMapEntries 方法:

 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
         int s = m.size();
         if (s > 0) {
             // 判断table是否已经初始化
             if (table == null) { // pre-size
                 // 未初始化，s为m实际元素的个数
                 float ft = ((float)s / loadFactor) + 1.0F;
                 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                 // 计算得到的t大于阈值，则初始化阈值
                 if (t > threshold)
                     threshold = tableSizeFor(t);
             }
             // 已初始化，并且m元素个数大于阈值，进行扩容处理
             else if (s > threshold)
                 resize();
             // 将m中的所有元素添加至HashMap中
             for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                 K key = e.getKey();
                 V value = e.getValue();
                 putVal(hash(key), key, value, false, evict);
             }
         }
     }

hash方法

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

put方法

对 putVal 方法添加元素的分析如下：

  1. 如果定位到的数组位置没有元素 就直接插入。

  2. 如果定位到的数组位置有元素就和要插入的 key 比较，如果 key 相同就直接覆盖，如果 key 不相同，就判断 p 是否是一个树节点，如果是就调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)将元素添加进入。如果不是就遍历链表插入(插入的是链表尾部)。

     

 /**
      * 向表中添加K,V键值对
      */
     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) {
         java.util.HashMap.Node<K,V>[] tab; java.util.HashMap.Node<K,V> p; int n, i;
         // table未初始化或者长度为0，进行扩让
         if ((tab = table) == null || (n = tab.length) == 0)
             n = (tab = resize()).length;
         // (n - 1) & hash 确定元素放在哪个桶中，桶为空，新生成节点放入桶中（此时，这个节点是放在数组中）
         if ((p = tab[i = (n - 1) & hash]) == null)
             tab[i] = newNode(hash, key, value, null);
         // 桶中已经存在元素
         else {
             java.util.HashMap.Node<K,V> e; K k;
             // 比较桶中第一个元素（数组中的节点）的hash值相等，key相等
             if (p.hash == hash &&
                     ((k = p.key) == key || (key != null && key.equals(k))))
                 // 将第一个元素赋值给e，用e来记录
                 e = p;
             // 如果冲突位置已经是红黑树作为存储结构，则放入红黑树中
             else if (p instanceof java.util.HashMap.TreeNode)
                 e = ((java.util.HashMap.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);
                         // 如果此时链表内长度 >= 7，将链表转化为红黑树，并将节点插入
                         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;
                     // 用于遍历桶中的链表，与前面的 e = p.next 组合可以遍历链表
                     p = e;
                 }
             }
             // 表示在桶中找到key值，hash值与插入元素相等的节点
             if (e != null) { // existing mapping for key
                 // 记录e的value值
                 V oldValue = e.value;
                 if (!onlyIfAbsent || oldValue == null)
                     // 新值替换旧值
                     e.value = value;
                 afterNodeAccess(e);
                 // 返回旧值
                 return oldValue;
             }
         }
         // 结构性修改
         ++modCount;
         // 实际大小大于阈值则扩容
         if (++size > threshold)
             resize();
         afterNodeInsertion(evict);
         return null;
     }

get方法

 /**
      * 传入key值，返回value值，
      * 若不存在则返回null
      */
     public V get(Object key) {
         java.util.HashMap.Node<K,V> e;
         return (e = getNode(hash(key), key)) == null ? null : e.value;
     }
 ​
     final java.util.HashMap.Node<K,V> getNode(int hash, Object key) {
         java.util.HashMap.Node<K,V>[] tab; java.util.HashMap.Node<K,V> first, e; int            n; K k;
         // 表不为空且长度不为0，指定位置hash表内有元素
         if ((tab = table) != null && (n = tab.length) > 0 &&
                 (first = tab[(n - 1) & hash]) != null) {
         // 若key值相同，返回该节点
             if (first.hash == hash && // always check first node
                     ((k = first.key) == key || (key != null && key.equals(k))))
                 return first;
             // 若该节点有下一个节点
             if ((e = first.next) != null) {
                 // 若该节点属于红黑树节点，在红黑树中get
                 if (first instanceof java.util.HashMap.TreeNode)
                     return ((java.util.HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
                 // 在链表中get
                 do {
                     if (e.hash == hash &&
                             ((k = e.key) == key || (key != null && key.equals(k))))
                         return e;
                 } while ((e = e.next) != null);
             }
         }
         return null;
     }

resize()方法

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

 /**
      * 调整底层用于存储数据的hashmap底层数组长度
      * 优化操作效率 -> 每次扩容 扩大为原来的2倍
      */
     final java.util.HashMap.Node<K,V>[] resize() {
         java.util.HashMap.Node<K,V>[] 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;
             }
             // 如果小于最大值，容量翻倍
             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                 newThr = oldThr << 1; // double threshold
         }
         // 如果旧容量为0，并且旧阈值>0，就说明之前创建了哈希表但是没有添加元素，初始化容量等于阈值
         else if (oldThr > 0) // initial capacity was placed in threshold
             newCap = oldThr;
         else {               // zero initial threshold signifies using defaults
             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"})
         java.util.HashMap.Node<K,V>[] newTab = (java.util.HashMap.Node<K,V>[])new java.util.HashMap.Node[newCap];
         table = newTab;
         if (oldTab != null) {
             for (int j = 0; j < oldCap; ++j) {
                 java.util.HashMap.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 java.util.HashMap.TreeNode)
                         ((java.util.HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                     else { // preserve order
                         java.util.HashMap.Node<K,V> loHead = null, loTail = null;
                         java.util.HashMap.Node<K,V> hiHead = null, hiTail = null;
                         java.util.HashMap.Node<K,V> next;
                         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;
     }

JDK 1.7与1.8相同与不同

首先是相同点：

  1. 默认初始容量都是16，默认加载因子都是0.75。容量必须是2的指数倍数

  2. 扩容时都将容量增加1倍

  3. 根据hash值得到桶的索引方法一样，都是i=hash&(cap-1)

  4. 初始时表为空，都是懒加载，在插入第一个键值对时初始化

  5. 键为null的hash值为0，都会放在哈希表的第一个桶中

接下来是不同点,主要是思想上的不同，不再纠结与实现的不同：

  1. 最为重要的一点是，底层结构不一样，1.7是数组+链表，1.8则是数组+链表+红黑树结构

  2. 主要区别是插入键值对的put方法的区别。1.8中会将节点插入到链表尾部，而1.7中会将节点作为链表的新的头节点

  3. JDk1.8中一个键的hash是保持不变的，JDK1.7时resize()时有可能改变键的hash值

  4. rehash时1.8会保持原链表的顺序，而1.7会颠倒链表的顺序

  5. JDK1.8是通过hash&cap==0将链表分散，而JDK1.7是通过更新hashSeed来修改hash值达到分散的目的

  6. 初始化方法：