HashMap

简单HashMap的实现：https://juejin.cn/post/6844903920947429390#comment

线程不安全

Java7

  1. void transfer(Entry[] newTable, boolean rehash) {  
  2.         int newCapacity = newTable.length;  
  3.         for (Entry<K,V> e : table) {  
  5.             while(null != e) {  
  6.                 Entry<K,V> next = e.next;           
  7.                 if (rehash) {  
  8.                     e.hash = null == e.key ? 0 : hash(e.key);  
  9.                 }  
  10.                 int i = indexFor(e.hash, newCapacity);   
  11.                 e.next = newTable[i];  
  12.                 newTable[i] = e;  
  13.                 e = next;  
  14.             } 
  15.         }  
  16.     }

HashMap - 图1
我们假设有两个线程同时需要执行resize操作，我们原来的桶数量为2，记录数为3，需要resize桶到4，原来的记录分别为：[3,A],[7,B],[5,C]，在原来的map里面，我们发现这三个entry都落到了第二个桶里面。
假设线程thread1执行到了transfer方法的Entry next = e.next这一句，然后时间片用完了，此时的e = [3,A], next = [7,B]。线程thread2被调度执行并且顺利完成了resize操作，需要注意的是，此时的[7,B]的next为[3,A]。此时线程thread1重新被调度运行，此时的thread1持有的引用是已经被thread2 resize之后的结果。线程thread1首先将[3,A]迁移到新的数组上，然后再处理[7,B]，而[7,B]被链接到了[3,A]的后面，处理完[7,B]之后，就需要处理[7,B]的next了啊，而通过thread2的resize之后，[7,B]的next变为了[3,A]，此时，[3,A]和[7,B]形成了环形链表，在get的时候，如果get的key的桶索引和[3,A]和[7,B]一样，那么就会陷入死循环。
如果在取链表的时候从头开始取（现在是从尾部开始取）的话，则可以保证节点之间的顺序，那样就不存在这样的问题了。

作者：一字马胡
链接：https://www.jianshu.com/p/e2f75c8cce01
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Java8

  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.             n = (tab = resize()).length;
  6.         if ((p = tab[i = (n - 1) & hash]) == null) // 如果没有hash碰撞则直接插入元素
  7.             tab[i] = newNode(hash, key, value, null);
  8.         else {
  9.             Node<K,V> e; K k;
  10.             if (p.hash == hash &&
  11.                 ((k = p.key) == key || (key != null && key.equals(k))))  // 第一个节点就是
  12.                 e = p;
  13.             else if (p instanceof TreeNode)
  14.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  15.             else { // 链表
  16.                 for (int binCount = 0; ; ++binCount) {
  17.                     if ((e = p.next) == null) {
  18.                         p.next = newNode(hash, key, value, null);
  19.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  20.                             treeifyBin(tab, hash);
  21.                         break;
  22.                     }
  23.                     if (e.hash == hash &&
  24.                         ((k = e.key) == key || (key != null && key.equals(k))))
  25.                         break;
  26.                     p = e;
  27.                 }
  28.             }
  29.             if (e != null) { // existing mapping for key
  30.                 V oldValue = e.value;
  31.                 if (!onlyIfAbsent || oldValue == null)
  32.                     e.value = value;
  33.                 afterNodeAccess(e);
  34.                 return oldValue;
  35.             }
  36.         }
  37.         ++modCount;
  38.         if (++size > threshold)
  39.             resize();
  40.         afterNodeInsertion(evict);
  41.         return null;
  42.     }

这是jdk1.8中HashMap中put操作的主函数， 注意第6行代码，如果没有hash碰撞则会直接插入元素。如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，所以这线程A、B都会进入第6行代码中。假设一种情况，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，问题出现：线程A会把线程B插入的数据给覆盖，发生线程不安全。

Java8源码分析

初始化

  1. 设置的容量不能小于0
  2. 不能大于最大值
  3. 负载因子不能小于等于0
  4. 设置负载因子
  5. 设置门槛作为下次初始化的长度,在构造方法中不初始化数组
    1.  public HashMap(int initialCapacity, float loadFactor) {
    2.      if (initialCapacity < 0)
    3.          throw new IllegalArgumentException("Illegal initial capacity: " +
    4.                                             initialCapacity);
    5.      if (initialCapacity > MAXIMUM_CAPACITY)
    6.          initialCapacity = MAXIMUM_CAPACITY;
    7.      if (loadFactor <= 0 || Float.isNaN(loadFactor))
    8.          throw new IllegalArgumentException("Illegal load factor: " +
    9.                                             loadFactor);
    10.      this.loadFactor = loadFactor;
    11.      this.threshold = tableSizeFor(initialCapacity);
    12.  }

    Put

    ```java 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[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node 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)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; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

  2. 1. 数组如果为空,resize初始化数组
  3. 1. 如果对应的数组位置上是空,则在这个地方添加节点
  4. 1. 如果这个位置的头结点就是参数中的key,记录这个节点为e
  5. 1. 否则如果这个节点是树节点,进行树节点的遍历
  6. 1. 否则遍历这个列表
  7.    1. 如果已经查找到列表末尾都没有这个key,在列表后面添加节点,并判断是否到达树化的临界点
  8.    1. 如果有这个节点了,记录这个节点为e
  9. 6. 如果e!=null(说明节点已经存在),进行覆盖,返回旧值
  10. 6. 此时说明是添加节点,size++,判断是不是需要扩容
  11. 6. 返回null
  13. <a name="EEN1c"></a>
  14. ## resize
  15. ```java
  16. final Node<K,V>[] resize() {
  17.     Node<K,V>[] oldTab = table;
  18.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  19.     int oldThr = threshold;
  20.     int newCap, newThr = 0;
  21.     if (oldCap > 0) {
  22.         if (oldCap >= MAXIMUM_CAPACITY) {
  23.             threshold = Integer.MAX_VALUE;
  24.             return oldTab;
  25.         }
  26.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  27.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  28.             newThr = oldThr << 1; // double threshold
  29.     }
  30.     else if (oldThr > 0) // initial capacity was placed in threshold
  31.         newCap = oldThr;
  32.     else {               // zero initial threshold signifies using defaults
  33.         newCap = DEFAULT_INITIAL_CAPACITY;
  34.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  35.     }
  36.     if (newThr == 0) {
  37.         float ft = (float)newCap * loadFactor;
  38.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  39.                   (int)ft : Integer.MAX_VALUE);
  40.     }
  41.     threshold = newThr;
  42.     @SuppressWarnings({"rawtypes","unchecked"})
  43.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  44.     table = newTab;
  45.     if (oldTab != null) {
  46.         for (int j = 0; j < oldCap; ++j) {
  47.             Node<K,V> e;
  48.             if ((e = oldTab[j]) != null) {
  49.                 oldTab[j] = null;
  50.                 if (e.next == null)
  51.                     newTab[e.hash & (newCap - 1)] = e;
  52.                 else if (e instanceof TreeNode)
  53.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  54.                 else { // preserve order
  55.                     Node<K,V> loHead = null, loTail = null;
  56.                     Node<K,V> hiHead = null, hiTail = null;
  57.                     Node<K,V> next;
  58.                     do {
  59.                         next = e.next;
  60.                         if ((e.hash & oldCap) == 0) {
  61.                             if (loTail == null)
  62.                                 loHead = e;
  63.                             else
  64.                                 loTail.next = e;
  65.                             loTail = e;
  66.                         }
  67.                         else {
  68.                             if (hiTail == null)
  69.                                 hiHead = e;
  70.                             else
  71.                                 hiTail.next = e;
  72.                             hiTail = e;
  73.                         }
  74.                     } while ((e = next) != null);
  75.                     if (loTail != null) {
  76.                         loTail.next = null;
  77.                         newTab[j] = loHead;
  78.                     }
  79.                     if (hiTail != null) {
  80.                         hiTail.next = null;
  81.                         newTab[j + oldCap] = hiHead;
  82.                     }
  83.                 }
  84.             }
  85.         }
  86.     }
  87.     return newTab;
  88. }

分成两部分
第一部分:扩容操作

  1. 如果旧的容量>0
    1. 判断旧容量是不是大于最大容量,如果大于,返回
    2. 如果不大于,容量加倍
  2. 如果旧的容量=0
    1. 如果threshold>0,那么在构造函数里面设置了初试容量(最近的2^n)
    2. 否则就按默认值16进行初始化
  3. 按新的容量申请新数组

第二部分:更新位置

  1. 从0开始遍历旧的数组
  2. 如果这个位置不为空
    1. 并且只有一个节点,那么直接放入新数组的hash&(newCap-1)
    2. 如果是树节点
    3. 遍历链表
      1. 如果hash&oldCapacity=0,放入一个链表
      2. 如果hash&oldCapacity=1,放入一个链表
      3. 遍历完链表,将两个链表分别放入新链表的当前位置和当前位置+oldCapacity
    4. 返回新链表

get

  1. public V get(Object key) {
  2.     Node<K,V> e;
  3.     return (e = getNode(hash(key), key)) == null ? null : e.value;
  4. }
  8. final Node<K,V> getNode(int hash, Object key) {
  9.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  10.     if ((tab = table) != null && (n = tab.length) > 0 &&
  11.         (first = tab[(n - 1) & hash]) != null) {
  12.         if (first.hash == hash && // always check first node
  13.             ((k = first.key) == key || (key != null && key.equals(k))))
  14.             return first;
  15.         if ((e = first.next) != null) {
  16.             if (first instanceof TreeNode)
  17.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  18.             do {
  19.                 if (e.hash == hash &&
  20.                     ((k = e.key) == key || (key != null && key.equals(k))))
  21.                     return e;
  22.             } while ((e = e.next) != null);
  23.         }
  24.     }
  25.     return null;
  26. }
  1. 如果链表为空,返回null
  2. 根据hash & (capacity-1)得到所属的数组位置
  3. 如果该位置的第一个节点就是要查找的key,返回
  4. 如果头结点的下一个不是空
    1. 是树结点,树结点的查找
    2. 链表的遍历,遍历到就返回
  5. 返回空