HashMap是Java Collection Framework重要成员，也是基于哈希表使用最多的Collection，以key-value形式存储数据，但由于其线程不安全性不用于多线程编程，但用途依然广泛，在JDK1.8上，HashMap的源码又加入了新的内容，可见其重要。这次就是基于JDK1.8的源码来理解HashMap的运行原理。

继承

public class HashMap
    
      extends AbstractMap
     
      implements Map
      
       , Cloneable, Serializable {
      
     
    

这里可以看到HashMap是继承AbstractMap抽象类并且依赖Map接口的，而其中AbstractMap则是对Map接口进行了部分实现，主要基于迭代器。下面就是在AbstractMap中对get方法的实现。

public V get(Object key) {    Iterator
    
     
      > i = entrySet().iterator();    if (key==null) {        while (i.hasNext()) {            Entry
      
        e = i.next();            if (e.getKey()==null)                return e.getValue();        }    } else {        while (i.hasNext()) {            Entry
       
         e = i.next();            if (key.equals(e.getKey()))                return e.getValue();        }    }    return null;}
       
      
     
    

构造和初始化

在了解HashMap的构造函数之前首先需要知道HashMap的数据结构，也就是如何去存储。HashMap是基于哈希表的，因此底层肯定有一个作为哈希表的数组。而了解数据结构哈希表的都知道，哈希表在存储过程中存在冲突的问题，即存在多个key的哈希值相同，HashMap的做法是链表或者红黑树的方法，将相同哈希值的元素以链的形式连接在哈希表对应的位置。

这里需要注意的是关于红黑树的部分，在JDK1.7的部分是只有链表结构，但是由于链表过长的时候查找元素时间较长，在JDK1.8的时候加入了红黑树，当链表超过一定长度之后，链表就会转换成红黑树，便于查找和插入。

HashMap的构造函数有三种

• HashMap() 默认初始容量(16)和默认加载因子(0.75)的空HashMap
• HashMap(int initialCapacity) 指定初始容量和默认负载因子(0.75)的空HashMap
• HashMap(int initialCapacity, float loadFactor) 指定初始容量和负载因子的空 HashMap

这里需要了解两个参数，initialCapacity(初始容量)，指最开始创建哈希表数组的大小。loadFactor(负载因子)，指哈希表扩容的阈值，一般是当前表中存有元素与哈希表容量相除的商。

put和get

从JDK1.8开始，HashMap的元素是以Node形式存在，主要结构如下

static class Node
    
      implements Map.Entry
     
       {    final int hash;    final K key;    V value;    Node
      
        next;    //类方法，这里省略    .........}
      
     
    

包括元素的hash值，key，value以及指向下一个元素的引用。

put

put方法是HashMap的重点，包含了阈值校验，链表到红黑树的调整以及初始开辟哈希表，都是在put方法中完成的。这里是我注释的源码

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;//哈希表未创建或者长度为0时创建哈希表//resize()是重建哈希表的方法   if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length; //如果存入元素位置为空，创建一个node类，插入   if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);//存入元素位置有元素    else {        Node
      
        e; K k;    //存在相同的key，替换原先的值        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            e = p;    //存储的链表已经变为红黑树，调用putTreeVal()方法去存入        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) {                //没有相同key元素，就最后加上该元素                    p.next = newNode(hash, key, value, null);        //链表过长的时候，转变成红黑树                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        treeifyBin(tab, hash);                    break;                }                //找到相同key元素，替换value                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) //true || --                e.value = value;       //3.            afterNodeAccess(e);            return oldValue;        }    }    ++modCount;//判断阈值，决定是否扩容    if (++size > threshold)        resize();    afterNodeInsertion(evict);    return null;}
       
      
     
    

这里有简单的流程图表示这个过程

对于resize()的描述就不深入了，这里简单讲一下HashMap的扩容原则

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                 oldCap >= DEFAULT_INITIAL_CAPACITY)            newThr = oldThr << 1; // double threshold

这里可以看到，每次哈希表的扩容是在上一次的容量基础上乘以2。

get

get方法相对于put就简单很多，就是根据哈希值找到相应的元素链，然后遍历查找元素即可，源码如下

public V get(Object key) {    Node
    
      e;    return (e = getNode(hash(key), key)) == null ? null : e.value;}final Node
     
       getNode(int hash, Object key) {    Node
      
       [] tab; Node
       
         first, e; int n; K k;    if ((tab = table) != null && (n = tab.length) > 0 &&        (first = tab[(n - 1) & hash]) != null) {        //判断首元素是否为所找的        if (first.hash == hash && // always check first node            ((k = first.key) == key || (key != null && key.equals(k))))            return first;         //非首元素，需要遍历元素链        if ((e = first.next) != null) {        //判断是否为红黑树            if (first instanceof TreeNode)                return ((TreeNode
        
         )first).getTreeNode(hash, key);            do {                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    return e;            } while ((e = e.next) != null);        }    }    return null;}
        
       
      
     
    

HashMap死循环

在JDK1.7多线程情况下HashMap存在死循环的情况，主要是由于扩容的过程是非线程安全的，并且在元素存入新表的过程中会出现元素倒置，由于插入过程，新插入元素总是插入到头部，源码如下

void transfer(Entry[] newTable)  {      Entry[] src = table;      int newCapacity = newTable.length;       for (int j = 0; j < src.length; j++) {          Entry
    
      e = src[j];          if (e != null) {              src[j] = null;             //这里在做插入的过程中，总是将新插入元素放在链表头             do {                  Entry
     
       next = e.next;                  int i = indexFor(e.hash, newCapacity);                  e.next = newTable[i];                  newTable[i] = e;                  e = next;              } while (e != null);          }      }  }
     
    

具体的过程用图来表示，假设有两个线程，同时到了扩容的阶段，线程一在while循环开始就挂起了，线程二执行结束

之后线程一开始执行，从e节点开始，但是注意由于线程二扩容的影响，此时next节点的下一个节点是e

之后再往下遍历的时候，发现又回到了key=3，出现了环

这个问题在JDK1.8中解决了，它用了新的插入方式

Node
    
      loHead = null, loTail = null;Node
     
       hiHead = null, hiTail = null;Node
      
        next;do {    next = e.next;    //还是原索引位置    if ((e.hash & oldCap) == 0) {        if (loTail == null)            loHead = e;        else            loTail.next = e;        loTail = e;    }    //原索引+ oldCap位置    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;}
      
     
    

由于扩容是在原容量基础上乘以2，那么hash码校验的时候会比原来的多一位，那么只需要比较这个位置是0还是1即可，是1那么就在原索引位置向后位移原容量大小即可，是0就不动。