HashMap 源码解析(jdk 1.8)

　　 在程序员的日常工作中，面试中常常涉及。对于大部分程序猿来说可能还仅仅停留于会用的一个层面，很少会去摸索它底层是如何实现的，实现的原理是什么，面对这些的时候都是满头雾水。工作中的一次偶然让作者本人也逐步跨进了源码的大门，逐渐发现其中趣味，一点点摸索源码创作者的奇思妙想，在不知觉中提升了自己的思维韧性。 ———— 在此与大家一起分享所得，一起讨论一起提升自我，这也是本人开始写博客的初衷。所以以下有阐述的不对的地方请指出，谢谢

　概要

　　本章我们重新从整体上认识HashMap，先从数据结构开始然后再到源代码的实现。

1. 常见的数据结构
2. HashMap的数据结构
3. HashMap 源码解析（基于JDK1.8）
   • 重要字段
   • 基本单元
   • HashMap的构造方法
   • put()方法实现
     1. index 算法解析
     2. resize() 方法
   • get()方法实现
4. 总结

　　常见的数据结构

　　 那么常见的数据结构无非就是 数组 链表 二叉树 哈希表 ,我们大概了解下它们的新增，查找基础操作执行性能：

• 数组：采用一段连续的存储单元来存储数据，将所有元素按次序一次存储。查找操作需要遍历数组，逐一对比给定关键字和数组元素
• 链表：一条相互相连的数据节点表，每个节点由数据和指向下一个节点的指针组成。查找操作需要遍历链表逐一进行比对。根据指针域的不同可分为单向链表，双向链表，循环链表，多向表(网状表)
• 二叉树：二叉树是非线性结构，即每个数据节点至多只有一个前驱节点，但可以有多个后继节点，它可以采用顺序存储结构和链式储存结构
• 哈希表：以键 - 值(key - index)存储数据，相比于上面所说的数据结构，哈希表的性能相当高，在不考虑哈希冲突的情况下，查找操作仅需一次定位即可获得相应数据

　   HashMap数据结构

　　这里我们先来通过图来更形象具体的展现HashMap数据结构的组成，如图：

图1

　　 从上面图中所得 HashMap 是由数组+单向链表+红黑树组成，其主干是以Node为基本单元的一个Node数组，每个Node中包含一个key - value 键值对。通过散列映射来存储键值对数据，在查询上使用散列码的方式，提升了查询效率。最多允许一对键值对的key为null,允许多对键值对的value为null。

　　 HashMap 源码解析（基于JDK1.8）

　　 1.重要字段

    //默认初始容量是16，必须是2的幂
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    //最大容量（必须是2的幂并且小于2的30次幂，若过大将被这个值替换）
    static final int MAXIMUM_CAPACITY = 1 << 30;

    //默认加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //默认链表转红黑树的阈值
    static final int TREEIFY_THRESHOLD = 8;

    //从红黑树转成链表的阈值
    static final int UNTREEIFY_THRESHOLD = 6;

    transient Node[] table; //hash数组

    transient Set> entrySet;  //entry 缓存set

    transient int size;  //元素个数

    transient int modCount;  // 修改次数

    int threshold; //阈值，等于加载因子*容量，当实际大小超过阈值则进行扩容

    final float loadFactor;  //加载因子，默认值为0.75

 　　 2. 基本单元（Entry），亦叫Node节点，是HashMap的静态内部类，实现了Entry 。多个Node节点成链表，当链表的长度大于8时转为红黑树结构。

    static class Node implements Map.Entry {
        final int hash; //hash值，根据key值通过hash算法所得
        final K key;
        V value;
        Node next; //指向当前Node节点的下一个节点对象

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

　　 3. HashMap的构造方法

 1 //构造一个指定容量和负载因子的空HashMap
 2     public HashMap(int initialCapacity, float loadFactor) {
 3         if (initialCapacity < 0)
 4             throw new IllegalArgumentException("Illegal initial capacity: " +
 5                     initialCapacity);
 6         if (initialCapacity > MAXIMUM_CAPACITY)
 7             initialCapacity = MAXIMUM_CAPACITY;
 8         if (loadFactor <= 0 || Float.isNaN(loadFactor))
 9             throw new IllegalArgumentException("Illegal load factor: " +
10                     loadFactor);
11         this.loadFactor = loadFactor;
12         this.threshold = tableSizeFor(initialCapacity);//确定扩容阈值
13     }
14     //构造一个指定容量的空HashMap,默认负载因子（0.75）
15     public HashMap(int initialCapacity) {
16         this(initialCapacity, DEFAULT_LOAD_FACTOR);
17     }
18 
19     //构造一个空的HashMap,默认初始容量（16）和默认负载因子（0.75）
20     public HashMap() {
21         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
22     }
23 
24     //构造一个与指定映射Map相同的新HashMap
25     public HashMap(Map<? extends K, ? extends V> m) {
26         this.loadFactor = DEFAULT_LOAD_FACTOR;
27         putMapEntries(m, false);
28     } 

/**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

  这有一点要注意的是，上面代码中第一个构造器和第二个器都会通过tableSizeFor()方法来确认threshold值(判断是否需要扩容临界值，阈值)，如上面代码12行所示。而第三个默认的构造器则没有指定threshold的值， 最后构造器则是将一个Map映射到当前新的Map中。

　　 4. put()方法的实现

 1      public V put(K key, V value) {
 2           return putVal(hash(key), key, value, false, true); //hash(key)通过hash算法计算对应key的hash值
 3     }
 4 
 5     /**
 6      * Implements Map.put and related methods
 7      *
 8      * @param hash         hash for key
 9      * @param key          the key
10      * @param value        the value to put
11      * @param onlyIfAbsent if true, don't change existing value
12      * @param evict        if false, the table is in creation mode.
13      * @return previous value, or null if none
14      */
15     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
16                    boolean evict) {
17         Node[] tab;
18         Node p;
19         int n, i;
20         if ((tab = table) == null || (n = tab.length) == 0)
21             n = (tab = resize()).length;  //resize()方法 负责初始化和扩容
22         if ((p = tab[i = (n - 1) & hash]) == null) //计算下标  这里直接采用了计算机基本运算的二进制&运算代替取模运算  ('n-1 & hash' 与 'hash%n' 一样效果）   
23             tab[i] = newNode(hash, key, value, null);
24         else {
25             Node e ;
26             K k;
27             if (p.hash == hash &&
28                     ((k = p.key) == key || (key != null && key.equals(k)))) //hashCode相同key相同，直接覆盖
29                 e = p;
30             else if (p instanceof TreeNode) //若为红黑树结构时
31                 e = ((TreeNode) p).putTreeVal(this, tab, hash, key, value);
32             else { //链表
33                 for (int binCount = 0; ; ++binCount) {
34                     if ((e = p.next) == null) {
35                         //链表尾插，jdk1.7是头插
36                         p.next = newNode(hash, key, value, null);
37                         if (binCount >= TREEIFY_THRESHOLD - 1) // 当链表长度大于8是转为红黑树结构
38                             //链表转红黑树
39                             treeifyBin(tab, hash);
40                         break;
41                     }
42                     if (e.hash == hash &&
43                             ((k = e.key) == key || (key != null && key.equals(k))))
44                         break;
45                     p = e;
46                 }
47             }
48             if (e != null) { // existing mapping for key
49                 V oldValue = e.value;
50                 if (!onlyIfAbsent || oldValue == null)
51                     e.value = value;
52                 afterNodeAccess(e);
53                 return oldValue;
54             }
55         }
56         ++modCount;
57         if (++size > threshold)
58             resize();
59         afterNodeInsertion(evict);
60         return null;
61     }

 1）index 算法：解读上面第22行代码

  p = tab[i = (n - 1) & hash] 根据代码不难猜到（n-1）& hash 就是数组元素的下标值index，如何去理解为什么 （n-1）& hash 就是index值呢？
　　
　首先，我们以默认数组初始容量大小(16)考虑，假如我们通过put("xxx","world")往Map中放键值对，那么根据图1的结构所示，首先要根据key值"xxx"得到一个 0-15 的整型数才能确定
该Node对象在数组哪个桶位(也就是下标index)，那么就必须要整型数，正好每个对象都有hashCode,得到一个整型数，因为最终要得到一个0-15的整型数，那么就可以将得到的hashCode整型
数取模16（hashCode % 16 = result），那么这样得到的result的结果就是0-15之间的一个数。我们再对比下源码（n-1）& hash 看起来好像不一样( n=16 )，但是事实告诉我的是一样
的，这就是源码设计者的精妙之处所在。
那来解释一下到底精妙在哪里：
　　　首先，计算机的底层基本运算是二进制运算的，而这里 hashCode % 16 相比于 二进制 与（&） 运算更为复杂，因为取模（%）运算最终都将会转化为二进制的'&','|','^'等运算，
一定程度上提高了效率，知道了这一点后我们。
　　　再来分析下为什么 （n-1）& hash  == hashCode%16  ?
　　　　   16  的   二进制    10000
　　n-1　　15  的   二进制    01111
　　假如 hash  的   二进制    1001 0010 0001 0100 0100 0010 0010 1010       hash              ---- int 类型，一定是32位
　　　　　　　　　　　　　　  0000 0000 0000 0000 0000 0000 0000 1111   &    15
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　----------
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　result       index
　　　正如上面所举的例子，可变的只有hash值，n是不变，n-1=15 ，15的二进制是 01111 ，高位不足全部补0，即下滑线的0为补上的0，&运算遇0得0，那么自然而然 result 的结果则取决
于hash值的末4位数（红色字位），hash的后4位的范围是 0000-1111 之间，参与&运算，那么result的最大值只有可能是1111，最小就是0000，同样达到了我们前面所要求的获取 0-15的一
个整型数值。说了这么多也不知道大家能不能看懂。(不懂欢迎随时找我)
    我们不如再来看看 hash(key)函数，代码如下

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //key.hashCode()得到一个整型数，
        // 高16位和低16位进行异或运算，使每位都参与运算，增大可能性
    }

　　正如上面我们解释过 result 的结果最终演变成了hash值的末4位数。我们倒回去看上面putVal()方法的源码中，我们可以看到22行 if 的判断，假设 result =1,也就是数组index=1的桶
位不为null，那么则代码走else语句，若key相同则直接替代，若不相同，则意味着 hash冲突 的产生，put入的Node节点对象必然要么存在链表结构中，要么就存在红黑树结构中，不管是链表或
是红黑树的查询效率都远远比不上散列码（哈希表）的查询高效。冲突不可避免，只能尽可能的降低冲突发生的可能性，结合上面分析得到，要尽量增大result的可能性，那自然成了要增大hash值的
可能性，这样则可以实现result尽可能的不一样，然而起决定性作用的是hash值末4位，为了增大其可能性源码设计者采用异或运算，将高位的16位和低16位进行异或,如此一来影响结果的位数就不
止仅后四位决定，通过更多位的参与运算得到一个更加均匀分布的entry数组，有效提高了hashMap的性能。运算流程如下图：

图2

为什么用 ‘异或’运算而 ‘与’ ‘或’ 运算不行能呢？相信大家同样会有这样的疑惑，我们结合下图来一起理解下

图3

  图3中的概率比较明显的是'&'和'|'运算，有0则0或有1则1 每种可能都是75%，而'^'运算则可以均衡1和0的分布，那么自然出现相同的概率相比于前两者要更低。　
　
　

2）resize()方法，负责初始化和扩容工作

 1 　　final Node[] resize() {
 2         Node[] oldTab = table;
 3         int oldCap = (oldTab == null) ? 0 : oldTab.length;
 4         int oldThr = threshold;
 5         int newCap, newThr = 0;
 6         if (oldCap > 0) {
 7             if (oldCap >= MAXIMUM_CAPACITY) { //当数组超过最大容量处理
 8                 threshold = Integer.MAX_VALUE;
 9                 return oldTab;
10             } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)//newCap = oldCap << 1 扩大为原来的两倍
11                 newThr = oldThr << 1; // double threshold
12         } else if (oldThr > 0) // 初始容量设置为阈值
13             newCap = oldThr;
14         else {               // 初始阈值为零时使用默认值
15             newCap = DEFAULT_INITIAL_CAPACITY;
16             newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
17         }
18         if (newThr == 0) {
19             float ft = (float) newCap * loadFactor;
20             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
21         }
22         threshold = newThr;
23         @SuppressWarnings({"rawtypes", "unchecked"})
24         Node[] newTab = (Node[]) new Node[newCap];
25         //扩容时，数据迁移处理
26         if (oldTab != null) {
27             for (int j = 0; j < oldCap; ++j) {
28                 Node e;
29                 if ((e = oldTab[j]) != null) {
30                     oldTab[j] = null;
31                     if (e.next == null) // 判断当前节点下有无链表结构
32                         newTab[e.hash & (newCap - 1)] = e;
33                     else if (e instanceof TreeNode) //判断当前节点是否为红黑树结构
34                         ((TreeNode) e).split(this, newTab, j, oldCap);
35                     else { // preserve order  // 链表迁移处理
36                         Node loHead = null, loTail = null;//存与老表索引位置相同的节点
37                         Node hiHead = null, hiTail = null;//存老表索引+oldCap的节点
38                         Node next;
39                         do {table = newTab;
40                             next = e.next;
41                             if ((e.hash & oldCap) == 0) { //如果e.hash值与老表的容量进行‘&’运算，则扩容后的索引位置跟老表的索引位置一样
42                                 if (loTail == null)
43                                     loHead = e;
44                                 else
45                                     loTail.next = e;
46                                 loTail = e;
47                             } else {//如果e.hash值与原表的容量进行‘&’运算结果为1，则扩容的后的索引位置为 老表索引+oldCap
48                                 if (hiTail == null)
49                                     hiHead = e;
50                                 else
51                                     hiTail.next = e;
52                                 hiTail = e;
53                             }
54                         } while ((e = next) != null);
55                         if (loTail != null) {
56                             loTail.next = null;
57                             newTab[j] = loHead;
58                         }
59                         if (hiTail != null) {
60                             hiTail.next = null;
61                             newTab[j + oldCap] = hiHead;
62                         }
63                     }
64                 }
65             }
66         }
67         return newTab;
68     }

我们从上面源码第6行开始看，
if(oldCap>0){} 
　　　　　　　　　如果老表的容量大于0,判断老表的是否超过最大容量，若超过将threshold阈值设置为Integer.MAX_VALUE，返回出老表。若新表的容量设为2被的老表容量（oldCap<<1,
　　　　　　　　　左位移运算相当与乘2）小于MAXIMUM_CAPACITY(最大容量)，并且老表容量oldCap大于等于DEFAULUT_INITIAL_CAPACITY(默认初始容量 16)，则新表的阈值设置位2倍
　　　　　　　　　老表的阈值。
else if(oldThr > 0){}   
　　　　　　　　　只有当老表的容量oldCap = 0 ，并且传入了自定义容量值初始化出来的空表(老表的创建)，也就是HashMap(int initialCapacity,float loadFactor)的构造方法
　　　　　　　　　初始化创建的空HashMap，从构造器中可以看出并没有属性去接收该initialCapacity值，而是将该值通过tableSizeFor()方法计算出阈值，那么老表的阈值(oldThr)则
　　　　　　　　　为我们要新创建的HashMap的capacity，所以代码中将新表的容量设置为老表的阈值。
else{}
　　　　　　　　　如果老表的容量oldCap = 0 ，并且 阈值threshold = 0，那么就是没有自定义参数new出来空的新HashMap，那么阈值和容量则设置为默认值。
if(newThr == 0){}
　　　　　　　　　当出现newThr == 0 的时，跟上面else if(oldThr > 0)的情况相同，即只有传入自定义容量初始化出来的老表才能满足 newThr == 0，亦可理解为代码执行了else if
　　　　　　　　　(oldThr > 0 ) 就能满足 newThr == 0 的条件，从源码中执行流程亦可看出此点。

重点来了，大家看到上面源码第41行，
e.hash&oldCap == 0
　　　上面源码注解中提到，若此条件成立，一个节点从老表中迁移到新表中的下标值(index)不变，反之则下标值为老表下标值+老表容量。
　　　为什么呢？
　　　　　我们从上面提到 put()方法内的 p = tab[i = (n-1) & hash] 代码来展开，假设老表的容量oldCap = 16,则扩容后的新表的容量newCap = 32 ，在老表中有index = 1 上的
　　　Node节点要从老表迁移到新表上，按正常p = tab[i = (n-1) & hash]的方法来计算index，即 i = 31 & hash ,对于同一个key值算出来的 hash值是一样的，那么新表与老表决定i
　　　值区别在于一个 31 ，一个 15 ，我们将其转为二进制表示：31为 11111 ，15为 1111 ，二进制的31和15的后4位都是1，那么对于同一个Node节点，不管在新表上还是在老表上 hash
　　　&(n-1) 所得result的结果后4位都一样，这时hash值倒数第5位就决定result。而二进制只有0和1表示，所以倒数第5位数要么是‘0’要么是‘1’，那若同一Node节点在老表中result = 
　　　xxxx,那么在新表中result值只可能有 0xxxx 和 1xxxx, 而1xxxx = xxxx + 10000,10000是16的二级制表示。到这里结论已经显而易见了。扩容后，老表节点迁移到新表的后节点的
　　　索引只有两种情况，要么是原索引位置，要么是原索引位置+原容量(老表容量)，我们再看源码,源码设计者巧妙用 e.hash & oldCap == 0 一步直击要点（真妙！令老夫诚服）
　　　配个图帮助大家更好理解：
　　　

图4

　　5. get()方法实现

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;
    // table不为空 && table长度大于0 && table索引位置(根据hash值计算出)不为空
    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;    // first的key等于传入的key则返回first对象
        if ((e = first.next) != null) { // 向下遍历
            if (first instanceof TreeNode)  // 判断是否为TreeNode
                // 如果是红黑树节点，则调用红黑树的查找目标节点方法getTreeNode
                return ((TreeNode)first).getTreeNode(hash, key);
            // 走到这代表节点为链表节点
            do { // 向下遍历链表, 直至找到节点的key和传入的key相等时,返回该节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;    // 找不到符合的返回空
}

 　　总结

　　　1.HashMap结构由Node数组+单向链表+黑红树组成，在数组的桶位上若存在多个节点在同一桶位，则可能以单向链表或黑红树结构存在，当一个桶位个结构根据在该桶位的Node节点个数的
　　　　变化，在链表和红黑树直接变化，桶中Node节点个数为 0-8 个时以链表结构存在，当个数 >8时链表转红黑树结构，当红黑树结构中Node节点 减少到6 个时转为链表结构。
　　　2.HashMap的默认容量16，默认加载因子0.75，容量必须是2的幂，扩容阈值为容量*加载因子的值。
　　　3.HashMap put的过程，对key计算hash值，然后hash*(容量-1)得到index（桶位），如果没有冲突直接放入桶中，如果发生冲突以链表的结构链接在后面，当链表结构节点的个数超过8个
　　　　链表结构变成红黑树结构存储，如果节点已存在直接替换，如果桶满了（容量*加载因子）就执行resize进行扩容。
　　　4.HashMap 中hash函数实现方式：将key.hashCode()值进行高16位与低16位的异或运算，充分增加参与运算的位数，增大hash结果的可能性，降低冲突概率。 解决冲突的办法有开放定址
　　　　法和拉链法(开放定址法：如线性探查法，平方探查法，伪随机序列法，双哈希函数法；拉链法：把所有hash值相同的记录用单链表连接起来)。
　　　5.HashMap 扩容后的对原数据的迁移，原表中的Node节点迁移至新表的下标位置变化，只可能在两个位置，一个在原下标位置，另一个在原下标+原表容量位置。源码通过 hash & oldCap
　　　　判断是否为0区分该两中情况。导致这样的根本原因是：1）table的容量始终为2的n次幂 2）索引的计算方法为 hash & (table.length-1)
　　　6.线程安全性 hashMap是线程非安全的，hashtable和ConcurrentHashMap是线程安全的(hashtable和ConcurrentHashMap的区别这里就不细说了，在后面CurrentHashMap源码解读
　　　　一章再详细介绍)，所以在并发的场景下需要用ConcurrentHashMap来确保线程安全。