JDK1.8 HashMap putVal 源码解析

在JDK1.8之前HashMap底层数据结构为数组加链表，table为其内部类Entry的数组，而Entry实现是一个链表的数据结构；JDK1.8 HashMap底层数据结构为数组加链表与红黑树，table为Entry的数组，但entry有 Node与TreeNode两种实现，Node为链表实现，TreeNode红黑树实现，当结点个数没超过8个时，桶里面为Node结点构成的链表，如果超过桶里面为TreeNode结点构成的红黑树。JDK1.8 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是否被初始化没有时调用resize()方法初始化
        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<K,V> e; K k;
            //新放入桶中的元素原来已存在
            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);
           //新放入桶中的元素原来不存在，且桶里面原先结构为Node构成链表
            else {
                //遍历桶中的Node构成链表，从头向尾遍历
                for (int binCount = 0; ; ++binCount) {
                    //遍历到最后一下结点
                    if ((e = p.next) == null) {
                        //将新放入的结点加入链表尾部
                        p.next = newNode(hash, key, value, null);
                        //如果Node构成链表的长度超过8个，将桶中Node构成链表变为TreeNode构成的红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //放入的key在Node构成链表已存在
                    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;
    }

从putVal以下代码，可看出当桶中为Node结点构成的链表时，新放入的元素是加到链表的尾部的，这与JDK1.8之前的版本不太一样；JDK1.8之前的版本新放入的元素是加在链表的头部的。（前阵子去饿了么面试面试官问我新加入的元素是放在尾部还是头部，我回答尾部，面试官说不对，这个实际是要区分JDK版本的，很细节的一个问题，估计我以后当面试官会问这个问题^-^）

  //遍历桶中的Node构成链表，从头向尾遍历
  for (int binCount = 0; ; ++binCount) {
        //遍历到最后一下结点
        if ((e = p.next) == null) {
            //将新放入的结点加入链表尾部
            p.next = newNode(hash, key, value, null);
            //如果Node构成链表的长度超过8个，将桶中Node构成链表变为TreeNode构成的红黑树
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        //放入的key在Node构成链表已存在
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
   }
```

JDK1.7 实现put方法实现

```
  public V put(K paramK, V paramV)
  {
    //table为空根据阈值初始化table
    if (this.table == EMPTY_TABLE)
      inflateTable(this.threshold);
    //key为null时特殊处理
    if (paramK == null)
      return putForNullKey(paramV);
    int i = hash(paramK);
    int j = indexFor(i, this.table.length);
    //遍历具体桶中的链表
    for (Entry localEntry = this.table[j]; localEntry != null; localEntry = localEntry.next)
    {
      Object localObject1;
      //如果新要放入的key在原链接中已存在
      if ((localEntry.hash == i) && (((localObject1 = localEntry.key) == paramK) || 
        (paramK.equals(localObject1))))
      {
        Object localObject2 = localEntry.value;
        localEntry.value = paramV;
        localEntry.recordAccess(this);
        return localObject2;
      }
    }
    this.modCount += 1;
    //加入新key到桶中
    addEntry(i, paramK, paramV, j);
    return null;
  }
```

再来看看addEnty方法与createEntry方法实现

```
void addEntry(int paramInt1, K paramK, V paramV, int paramInt2)
  {
    //扩容处理
    if ((this.size >= this.threshold) && (null != this.table[paramInt2]))
    {
      resize(2 * this.table.length);
      paramInt1 = null != paramK ? hash(paramK) : 0;
      paramInt2 = indexFor(paramInt1, this.table.length);
    }
    //加入新结点
    createEntry(paramInt1, paramK, paramV, paramInt2);
  }
 
  void createEntry(int paramInt1, K paramK, V paramV, int paramInt2)
  {
    //保存桶中第一个结点
    Entry localEntry = this.table[paramInt2];
    //原第一个结点对应链表接到新加入结点尾部同时更新桶中第一个结点
    this.table[paramInt2] = new Entry(paramInt1, paramK, paramV, localEntry);
    this.size += 1;
  }
```

另外还有一点JDK1.7 HashMap在并发时由于resize可能导致桶中的链表出现循环链的情况，具体分析可以参考[https://coolshell.cn/articles/9606.html](http://) 
JDK1.8 应该不会出现这个问题，只是本人猜想后面我会分析一下具体源码。先到这里下面分析在并发情况下JDK1.8版本的HashMap到底会不会出现循环链的情况。