JDK1.7头插法导致的循环

当多线程去扩容HashMap时，因为头插法会产生链表成环的问题：
若当前线程此时获得entry节点，但是被挂起，而另外一个线程已经完成扩容操作，并且因扩容和头插法操作导致链表顺序颠倒。
而原来被挂起的线程继续执行，并且继续才用头插法扩容同一个链表，因为此时链表顺序因为另一个线程的头插法颠倒了，所以当前线程再次采用头插法会将下一个节点的next指向自己。
导致两个节点的next互相引用对方，因此产生环。

HashMap原理

JDK8之前HashMap有数组+链表组成，数组为HashMap主体，链表用来解决Hash冲突。

JDK8及之后在解决哈希冲突的时候发生了变化，在链表长度大于阈值（默认为8），会将链表转换为红黑树（链表转红黑树前会判断，如果当前数组长度小于64，会先进行数组的扩容，而不是转换为红黑树。（该特性参考treeifBin方法

拉链法

将数组和链表结合，数组中的一个元素就是一个链表，若遇到哈希冲突，将冲突的值添加到链表即可。

HashMap类的属性

  1. public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
  2.     // 序列号
  3.     private static final long serialVersionUID = 362498820763181265L;    
  4.     // 默认的初始容量是16
  5.     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
  6.     // 最大容量
  7.     static final int MAXIMUM_CAPACITY = 1 << 30; 
  8.     // 默认的填充因子
  9.     static final float DEFAULT_LOAD_FACTOR = 0.75f;
  10.     // 当桶(bucket)上的结点数大于这个值时会转成红黑树
  11.     static final int TREEIFY_THRESHOLD = 8; 
  12.     // 当桶(bucket)上的结点数小于这个值时树转链表
  13.     static final int UNTREEIFY_THRESHOLD = 6;
  14.     // 桶中结构转化为红黑树对应的table的最小大小
  15.     static final int MIN_TREEIFY_CAPACITY = 64;
  16.     // 存储元素的数组，总是2的幂次倍
  17.     transient Node<k,v>[] table; 
  18.     // 存放具体元素的集
  19.     transient Set<map.entry<k,v>> entrySet;
  20.     // 存放元素的个数，注意这个不等于数组的长度。
  21.     transient int size;
  22.     // 每次扩容和更改map结构的计数器
  23.     transient int modCount;   
  24.     // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
  25.     int threshold;
  26.     // 加载因子
  27.     final float loadFactor;
  28. }
  1. loadFactor
    用于动态计算阈值，也用于表示该map的数据疏密程度，loadFactor过大会导致元素密集，hash碰撞的可能性也就越大，查找的效率也就越低。而loadFactor过小会导致数组利用率低，存放的数据分散。官方建议默认值0.75是一个比较好的临界值。
  2. threshold
    临界值，threshold = capacity * loadFactor当size >= threshold时，就要考虑对数组进行扩容

Node节点

  1. // 继承自 Map.Entry<K,V>
  2. static class Node<K,V> implements Map.Entry<K,V> {
  3.        final int hash;// 哈希值，存放元素到hashmap中时用来与其他元素hash值比较
  4.        final K key;//键
  5.        V value;//值
  6.        // 指向下一个节点
  7.        Node<K,V> next;
  8.        Node(int hash, K key, V value, Node<K,V> next) {
  9.             this.hash = hash;
  10.             this.key = key;
  11.             this.value = value;
  12.             this.next = next;
  13.         }
  14.         public final K getKey()        { return key; }
  15.         public final V getValue()      { return value; }
  16.         public final String toString() { return key + "=" + value; }
  17.         // 重写hashCode()方法
  18.         public final int hashCode() {
  19.             return Objects.hashCode(key) ^ Objects.hashCode(value);
  20.         }
  22.         public final V setValue(V newValue) {
  23.             V oldValue = value;
  24.             value = newValue;
  25.             return oldValue;
  26.         }
  27.         // 重写 equals() 方法
  28.         public final boolean equals(Object o) {
  29.             if (o == this)
  30.                 return true;
  31.             if (o instanceof Map.Entry) {
  32.                 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
  33.                 if (Objects.equals(key, e.getKey()) &&
  34.                     Objects.equals(value, e.getValue()))
  35.                     return true;
  36.             }
  37.             return false;
  38.         }
  39. }

HashMap构造方法

  1.     // 默认构造函数。
  2.     public HashMap() {
  3.         this.loadFactor = DEFAULT_LOAD_FACTOR; // all   other fields defaulted
  4.      }
  6.      // 包含另一个“Map”的构造函数
  7.      public HashMap(Map<? extends K, ? extends V> m) {
  8.          this.loadFactor = DEFAULT_LOAD_FACTOR;
  9.          putMapEntries(m, false);//下面会分析到这个方法
  10.      }
  12.      // 指定“容量大小”的构造函数
  13.      public HashMap(int initialCapacity) {
  14.          this(initialCapacity, DEFAULT_LOAD_FACTOR);
  15.      }
  17.      // 指定“容量大小”和“加载因子”的构造函数
  18.      public HashMap(int initialCapacity, float loadFactor) {
  19.          if (initialCapacity < 0)
  20.              throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
  21.          if (initialCapacity > MAXIMUM_CAPACITY)
  22.              initialCapacity = MAXIMUM_CAPACITY;
  23.          if (loadFactor <= 0 || Float.isNaN(loadFactor))
  24.              throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
  25.          this.loadFactor = loadFactor;
  26.          this.threshold = tableSizeFor(initialCapacity);
  27.      }

putMapEntries方法

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

putMapEntries方法逻辑：

  1. 先判断加进去的map大小是否为0，大于0则继续执行操作
  2. 再通过table==null判断Hashmap类是否初始化
    • 若未进行初始化，将待加入的map的大小除以loadfactor作为参考大小，将参考大小与Map最大容量做比较，保证参考大小不超过MAXIMUM_CAPACITY作为实际加入map的size。若这个size大于了threshold，进行扩容处理。
    • 若进行了初始化，并且待加入的map大小大于阈值threshold，进行resize（）处理（一般情况下resize会将原map扩容至两倍）
  3. 最后遍历待加入的map的Entry，将Entry放入目的map。

Put方法逻辑(JDK1.8)

put方法.png

HashMap只提供了put方法给用户使用，而put方法调用putVal方法，这样对于用户隐藏了一些参数细节。

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  2.                boolean evict) {
  3.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  4.     if ((tab = table) == null || (n = tab.length) == 0)
  5.         //注意resize的作用为初始化map或double这个map的大小，这里为初始化操作
  6.         n = (tab = resize()).length;
  7.     //如果table上的位置为null则直接插入，(n-1)&hash为确定下标的操作
  8.     if ((p = tab[i = (n - 1) & hash]) == null)
  9.         tab[i] = newNode(hash, key, value, null);
  10.     //若桶中已经存在元素 
  11.     else {
  12.         Node<K,V> e; K k;
  13.         //比较桶中的第一个元素，若hash和key都相等，直接覆盖
  14.         if (p.hash == hash &&
  15.             ((k = p.key) == key || (key != null && key.equals(k))))
  16.             e = p;
  17.         //如果key不相等，且该节点是树节点则调用putTreeVal
  18.         else if (p instanceof TreeNode)
  19.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  20.         else {
  21.             //都不是则该节点为链表，这里用一个binCount来表示链表的长度
  22.             for (int binCount = 0; ; ++binCount) {
  23.                 //采用尾插法，配合下面的 p = e 遍历到尾节点
  24.                 if ((e = p.next) == null) {
  25.                     //插入链表
  26.                     p.next = newNode(hash, key, value, null);
  27.                     //插入后若链表长度为8，进行树化操作
  28.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  29.                         treeifyBin(tab, hash);
  30.                     break;
  31.                 }
  32.                 //若此节点的key与待插入节点的key相同则跳出，跳出后再进行覆盖
  33.                 if (e.hash == hash &&
  34.                     ((k = e.key) == key || (key != null && key.equals(k))))
  35.                     break;
  36.                 //与前面的e = p.next组合，遍历链表
  37.                 p = e;
  38.             }
  39.         }
  40.         //覆盖操作
  41.         if (e != null) {
  42.             //记录旧值
  43.             V oldValue = e.value;
  44.             if (!onlyIfAbsent || oldValue == null)
  45.                 e.value = value;
  46.             //访问后回调
  47.             afterNodeAccess(e);
  48.             return oldValue;
  49.         }
  50.     }
  51.     //结构性修改
  52.     ++modCount;
  53.     //实际大小大于阈值则扩容
  54.     if (++size > threshold)
  55.         resize();
  56.     //插入后回调
  57.     afterNodeInsertion(evict);
  58.     return null;
  59. }

jdk1.7的put

与JDK1.8不同的地方主要在于，链表树化以及头插法插入链表两点。

get方法

  1. public V get(Object key) {
  2.         Node<K,V> e;
  3.         return (e = getNode(hash(key), key)) == null ? null : e.value;
  4.     }
  6.     final Node<K,V> getNode(int hash, Object key) {
  7.         Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  8.         //一边赋值一边检查table不为null、长度大于0、第一个元素能取到
  9.         if ((tab = table) != null && (n = tab.length) > 0 &&
  10.             (first = tab[(n - 1) & hash]) != null) {
  11.             //通过对比key先看看第一个元素是不是要找的元素
  12.             if (first.hash == hash && 
  13.                 ((k = first.key) == key || (key != null && key.equals(k))))
  14.                 return first;
  15.             //再看看后面有没有节点
  16.             if ((e = first.next) != null) {
  17.                 //有节点的话，看看第一个节点是不是树节点
  18.                 if (first instanceof TreeNode)
  19.                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  20.                 //不是树节点，那就是链表了，开始遍历
  21.                 do {
  22.                     //遍历到了就返回
  23.                     if (e.hash == hash &&
  24.                         ((k = e.key) == key || (key != null && key.equals(k))))
  25.                         return e;
  26.                 } while ((e = e.next) != null);
  27.             }
  28.         }
  29.         return null;
  30.     }

resize方法

resize还是非常耗时的，知道未来需要多少容量的情况下建议先一次性给足空间

  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.             //超过最大值就不扩容了，随你去碰撞（让你存这么多值= =
  8.             if (oldCap >= MAXIMUM_CAPACITY) {
  9.                 threshold = Integer.MAX_VALUE;
  10.                 return oldTab;
  11.             }
  12.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  13.                      oldCap >= DEFAULT_INITIAL_CAPACITY)
  14.                 //如果新容量超过了最大的容量，就不计算threshold了，因为也用不到
  15.                 newThr = oldThr << 1; // double threshold
  16.         }
  17.         //capacity没初始化就初始化capacity
  18.         else if (oldThr > 0) // initial capacity was placed in threshold
  19.             newCap = oldThr;
  20.         //用默认大小（16）初始化capacity和threshold
  21.         else {               // zero initial threshold signifies using defaults
  22.             newCap = DEFAULT_INITIAL_CAPACITY;
  23.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  24.         }
  25.         if (newThr == 0) {
  26.             float ft = (float)newCap * loadFactor;
  27.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  28.                       (int)ft : Integer.MAX_VALUE);
  29.         }
  30.         threshold = newThr;
  31.         @SuppressWarnings({"rawtypes","unchecked"})
  32.         //根据容量创建新的table                    
  33.         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  34.         table = newTab;
  35.         if (oldTab != null) {
  36.             //开始遍历
  37.             for (int j = 0; j < oldCap; ++j) {
  38.                 Node<K,V> e;
  39.                 if ((e = oldTab[j]) != null) {
  40.                     //用e存储了oldTab[j]，所以这里能设置为null
  41.                     oldTab[j] = null;
  42.                     //单节点情况下
  43.                     if (e.next == null)
  44.                         //rehash操作
  45.                         newTab[e.hash & (newCap - 1)] = e;
  46.                     //树节点情况下
  47.                     else if (e instanceof TreeNode)
  48.                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  50.                     else { // preserve order
  51.                         //这里有两条链表，区分的标准见下面那个if语句
  52.                         Node<K,V> loHead = null, loTail = null;
  53.                         Node<K,V> hiHead = null, hiTail = null;
  54.                         Node<K,V> next;
  55.                         do {
  56.                             next = e.next;
  57.                             //注意这里不是掩码的作用，而是看oldcap那一位是否为零
  58.                             //为零表示新容量不影响原来的Index计算，可以用原来的索引下标
  59.                             //至于为啥只看一位：因为resize是按两倍来扩容的
  60.                             if ((e.hash & oldCap) == 0) {
  61.                                 //这里先把头存起来
  62.                                 if (loTail == null)
  63.                                     loHead = e;
  64.                                 //再往下链接
  65.                                 else
  66.                                     loTail.next = e;
  67.                                 loTail = e;
  68.                             }
  69.                             //为1表示要进行一次偏移，偏移量为oldcapacity
  70.                             else {
  71.                                 if (hiTail == null)
  72.                                     hiHead = e;
  73.                                 else
  74.                                     hiTail.next = e;
  75.                                 hiTail = e;
  76.                             }
  77.                         } while ((e = next) != null);
  78.                         //下面两个if把事先存好的链表头接到table
  79.                         if (loTail != null) {
  80.                             loTail.next = null;
  81.                             newTab[j] = loHead;
  82.                         }
  83.                         if (hiTail != null) {
  84.                             hiTail.next = null;
  85.                             newTab[j + oldCap] = hiHead;
  86.                         }
  87.                     }
  88.                 }
  89.             }
  90.         }
  91.         return newTab;
  92.     }