神刀安全网

Jdk1.8 HashMap源码分析


1. 概述

平常我们开发中,可能用的最多的容器就是HashMap。我们来看下HashMap的结构如下图。

Jdk1.8 HashMap源码分析

image.png

它是由一个Node数组,每个数组元素又是有一个链表构成。接下来我们结合源码来分析下put(),get(),resize()者三个常见的操作。

2. 类成员变量的认识
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // HashMap初始的bucket16.必须是2的n次幂,原因在后面会涉及到  static final int MAXIMUM_CAPACITY = 1 << 30;  //最大容量  static final float DEFAULT_LOAD_FACTOR = 0.75f; //负载因子,估计整个bucket冲突,当到达bucket*0.75容量时,会引起扩容  static final int TREEIFY_THRESHOLD = 8;  //当链表长度大于这个值时,会转变成红黑树  static final int UNTREEIFY_THRESHOLD = 6; //当树的节点低于这个值时会转变成链表  
3. put()函数的解析

put()添加操作的过程如下。

  • 对key的hashCode()做hash,然后再计算index(求余);
  • 如果没碰撞直接放到bucket里;
  • 如果碰撞了,以链表的形式存在buckets后;
  • 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD),就把链表转换成红黑树;
  • 如果节点已经存在就替换old value(保证key的唯一性)
  • 如果bucket满了(超过load factor*current capacity),就要resize。
    其他的解释都在源码中标注。
public V put(K key, V value) {         //对key的hashcode做hash         return putVal(hash(key), key, value, false, true);     } //onlyIfAbsent为true时,相同的key不会改变替换值。这里的为false,会替换 //evict表示模式,为fasle表示处于bucket处于创建阶段。这里用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;         if ((tab = table) == null || (n = tab.length) == 0)             //若为null,则创建bucket             n = (tab = resize()).length;         if ((p = tab[i = (n - 1) & hash]) == null)             //若bucket那个位置为null,则创建新的Node节点             tab[i] = newNode(hash, key, value, null);             //表示bucket不为null         else {             Node<K,V> e; K k;             //key存在             if (p.hash == hash &&                 ((k = p.key) == key || (key != null && key.equals(k))))                 e = p;                 //若原来为TreeNode,则插入到红黑树种中             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;         //若超过当前容量大小超过capacity*0.75,则会引起扩容         if (++size > threshold)             resize();         afterNodeInsertion(evict);         return null;     } 

注意这里采用的二次hash()操作,不是直接对hashcode再hash。

//hashcode的低16位和高16位做 异或操作 static final int hash(Object key) {         int h;         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);     } 
  • 之所以这样hash,是采用key的hashcode的低16位和高16位做异或操作。这样的好处在于避免hash冲突。否则,它只取低16位,与高位无关,那么它有可能会hash冲突严重。另外,如果还有更严重的冲突,那么可以采用红黑树来解决,事实上Jdk1.8 HashMap也是采用的这样的思想。

Improve the performance of java.util.HashMap under high hash-collision conditions by using balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class.

4. get()的解析

get()相对来说就非常简单了,过程如下。

  • bucket里的第一个节点,直接命中;
  • 如果有冲突,则通过key.equals(k)去查找对应的entry
  • 若为树,则在树中通过key.equals(k)查找,O(logn);
  • 若为链表,则在链表中通过key.equals(k)查找,O(n)。
public V get(Object key) {         Node<K,V> e;         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;         //这个if判断bucket是否存在         if ((tab = table) != null && (n = tab.length) > 0 &&             (first = tab[(n - 1) & hash]) != null) {             //检查第一个Node(bucket中第一个节点)是否是要查找的。             if (first.hash == hash && // always check first node                 ((k = first.key) == key || (key != null && key.equals(k))))                 return first;             if ((e = first.next) != null) {                 //红黑树的查找key                 if (first instanceof TreeNode)                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);                 do {                 //遍历链表,寻找key相同                     if (e.hash == hash &&                         ((k = e.key) == key || (key != null && key.equals(k))))                         return e;                 } while ((e = e.next) != null);             }         }         return null;     } 

(n - 1) & hash就是一个求索引,即求Node数组中的下标。这样的操作是,当我们的n(表示capacity时)取2的幂的时候,例如n取16,那么n-1=15(二进制表示1111)与hash做与操作的时候相当于取余,这样做比直接取余更高效。

5. reSize()的解析
  • 当put时,如果发现目前的bucket占用程度已经超过了Load Factor所希望的比例,那么就会发生resize。在resize的过程,简单的说就是把bucket扩充为2倍,之后重新计算index,把节点再放到新的bucket中。
  • 然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在(原位置+旧capacity)的位置。
    怎么理解呢?例如我们从16扩展为32时,具体的变化如下所示:

    Jdk1.8 HashMap源码分析

    rehash

  • 这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。因此元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:

    Jdk1.8 HashMap源码分析

    resize

因此,我们在扩充HashMap的时候,不需要重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图:

Jdk1.8 HashMap源码分析

resize16-32

final Node<K,V>[] resize() {         Node<K,V>[] oldTab = table;         int oldCap = (oldTab == null) ? 0 : oldTab.length;         int oldThr = threshold;         int newCap, newThr = 0;         if (oldCap > 0) {           //旧的hashMap容量已经达到最大值,那么最新的也只能是最大值             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         } //旧的容量oldThreshold已经存在,但是没分配容量。那么久新的容量=oldThreshold         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);         } //如果初始化的oldThreshold为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"})             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                   //尾插法把节点插入新分配的bucket中。不带头节点的                         Node<K,V> loHead = null, loTail = null;                         Node<K,V> hiHead = null, hiTail = null;                         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;     } 

参考文章:

  1. Java HashMap工作原理及实现
  2. HashMap1.8源码解读
  3. 深入浅出ConcurrentHashMap1.8

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Jdk1.8 HashMap源码分析

分享到:更多 ()

评论 抢沙发