1. HashMap的家族定位
接口java.util.Map有四个罕用的实现类，如图是它们之间的类继承关系。
上面我将一一介绍其性能特点。
HashMap：- 最罕用的Map实现类，通过应用Hash表构造，进步查找速度；
- 应用键值对作为存储节点，只容许一个key值为
null，容许多个value值为null； - 线程不平安，对于线程平安有要求的程序，能够思考应用：sychronizedMap或者ConcurrentHashMap；
HashTable- 同样应用Hash表构造，进步查找效率；
- 线程平安，然而平安层级低于ConcurrentHashMap，不罕用。
LinkedHashMap- 继承自HashMap，应用Hash表构造，进步查找效率；
- 链表插入维持插入程序。
TreeMap- sortedMap接口的实现类，可应用特定的排序规定对键值对进行排序；
对四种常见的实现类的性能比拟如下图所示：
2. HashMap的数据结构
2.1 Hash表的基本概念
Hash表是数据结构和算法课程中学习到的一种重要的数据结构。次要设计思维是：
- 应用一个长度为
n的数组存储相干数据。 应用
hash函数实现内容和数组下标的对应，也就是hash函数的函数值为0~n之间。hash函数雷同的输出参数肯定会产生雷同函数值，不同内容尽量做到函数值扩散。
- 在hash函数值对应的下标写入该内容。
- 下次查找某元素的时候，先依据
hash函数生成下标，而后再随机拜访数组，这样查找效率大大提高了。
相似于一个叫贾斯汀·费尔兰德·亨利皮特潘（简单内容）的人，在酒店前台（hash函数）入住酒店的房间编号是1004（hash函数值/数组下标）。须要找他的人，只须要去酒店前台查问他住在1004房间，间接去1004房间找人就能够了，不须要一个一个房间去找。
2.2 Hash抵触
在下面的流程阐明中，咱们能够发现Hash表的实现要害就在于Hash函数，一个好的hash函数应该保障不同的输出内容尽量扩散其函数值。
当存入的数据过多，hash函数性能较差的时候，可能会呈现hash抵触：
A和B是两个不同的存储内容，然而通过hash函数计算，失去的hash函数值雷同，因而两个内容存储在数组的同一地位。- 例如：
贾斯汀·费尔兰德·亨利皮特潘和特朗普·懂王·建国同志两个人在酒店前台调配到的房间号都是1004，然而房间只有一张床，这时两个人就会发生冲突。
解决抵触次要有两种思路：
- 凋谢定址法：发生冲突的时候，后到来的元素放弃已被占用的地位，寻找新的插入地位。（再找）
链地址法：发生冲突的时候，后到来的元素在原有地位的根底上，应用链表的形式存储。（排队）
- HashMap应用的就是
链地址法。
- HashMap应用的就是
2.3 HashMap数据结构
节点Node
Node是HashMap的一个根本存储单元，从源码中可见Node实现了Map.Entry接口，寄存的是键值对。在JDK1.8中的源码中，Node的定义如下所示：static class Node<K,V> implements Map.Entry<K,V> { final int hash; //用来定位数组索引地位 final K key; V value; Node<K,V> next; //链表的下一个node Node(int hash, K key, V value, Node<K,V> next) { ... } public final K getKey(){ ... } public final V getValue() { ... } public final String toString() { ... } public final int hashCode() { ... } public final V setValue(V newValue) { ... } public final boolean equals(Object o) { ... }}JDK1.7的HashMap数据结构
数组+链表- 如图所示
- 应用链地址形式解决hash抵触。
- 如图所示
JDK1.8的HashMap数据结构
数组+链表+红黑树如图所示
- 对红黑树的学习可参考此博客。
- 链表和红黑树的转换依据链表长度阈值判断，阈值为8，即链表长度大于8时，由链表转换为红黑树，小于6时，由红黑树转换为链表。
- 红黑树的引入目标：在链表长度较长的状况下，优化查找效率。
3. HashMap的重要变量
3.1 常量
DEFAULT_INITIAL_CAPACITY- 默认的数组初始容量，值为
2^4=16。 - 如果没有指定初始数组的容量的话，就会应用这个默认值。
- 默认的数组初始容量，值为
MAXIMUM_CAPACITY- 最大的数组容量，值为
2^30。 - 在扩容的时候，如果扩容后的容量大于这个值，就会应用这个值作为新的容量。
- 之后如果数据再减少，不再进行扩容，而是间接链表存储或者转为红黑树。
- 最大的数组容量，值为
DEFAULT_LOAD_FACTOR- 默认负载因子，值为
0.75。 - 在HashMap中，扩容的临界值计算公式为：
临界值（threshold） = 负载因子（loadFactor） * 容量（capacity） 负载因子能够设置为任意值，然而须要留神的是：
- 负载因子变大，hash抵触的概率就会变大，查找效率就会升高。【就义工夫】
- 负载因子过小，会导致数组空间利用率低，节约内存空间。【就义空间】
- 默认负载因子，值为
TREEIFY_THRESHOLD- 链表转化为红黑树的阈值，值为
8。 - 当一个数组节点所带着的链表长度大于8时，链表会转化为红黑树。
- 链表转化为红黑树的阈值，值为
UNTREEIFY_THRESHOLD- 红黑树转化为链表的阈值，值为
6。 - 当一个数组节点的红黑树节点小于6时，红黑树会转化为链表。
- 红黑树转化为链表的阈值，值为
MIN_TREEIFY_CAPACITY- 转换为红黑树的最小容量，值为
64。 这个变量的意思是，在HashMap一直减少新元素的过程中，如果此时数组中的元素个数小于64，那么就抉择扩容。当数组元素个数大于64的时候才会思考树化。
3.2 变量
- 转换为红黑树的最小容量，值为
size- HashMap中存储的键值对个数。
modCount- 对HashMap进行批改的次数记录，每次增删则加一。
threshold- 扩容的临界值，计算公式为：
threshold = loadFactor * capacity。其中capacity为数组总长度，通常为了进步阈值，会应用扩容减少capacity，而对于负载因子loadFactor，个别不会批改。
- 扩容的临界值，计算公式为：
loadFactor- 负载因子，用户可自行设置其值，否则等于默认值
0.75。
- 负载因子，用户可自行设置其值，否则等于默认值
3.3 辨析size、capacity、threshold
size:理论存储的键值对个数
capacity:数组的总长度
threshold:扩容的临界值
treeify_threshold/untreeify_threahold:链表和红黑树互相转化的阈值
4. HashMap重要办法和源码解析
4.1 构造方法
HashMap()
无参结构，应用默认的初始容量2^4和负载因子0.75，结构一个空的HashMap。// 结构一个空的 HashMap，初始容量为 16，负载因子为默认值 0.75public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}HashMap(int initialCapacity)
指定初始容量，应用默认的负载因子0.75。public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);//一次性实现容量和负载因子的赋值}HashMap(int initialCapacity, float loadFactor)
指定初始容量和负载因子，结构一个空的HashMap。public HashMap(int initialCapacity, float loadFactor) { // 如果初始容量为正数，抛出非负异常 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 初始容量大于最大值时1<<30，则取最大值 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // 负载因子不能小于 0，并且必须是数字，否则抛异样 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); //数值判断非法之后，赋值 this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity);//tableSizeFor() 办法返回一个值，比initialCapacity大的最小2的幂。}HashMap(Map<? extends K, ? extends V> m)
结构一个非空的HashMap，将m中的键值对存入HashMap中，默认的负载因子 0.75，应用默认的初始容量2^4。public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; // 将 Map 中的 key-value 赋值到新的 Map 中去 putMapEntries(m, false);}4.2 resize办法
当HashMap中数组的使用量超过阈值的时候，就须要进行扩容。JDK1.8的源码如下所示：
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table;// 以后 table int oldCap = (oldTab == null) ? 0 : oldTab.length;// 以后table的大小 int oldThr = threshold;// 以后 table 的 threshold int newCap, newThr = 0;// 新的 table 的大小和阀值临时初始化为 0 // 上面就是开始计算新的 table 的大小和阀值 // 第一种状况：以后 table 的大小大于 0，则意味着以后的 table 必定是有数据的 if (oldCap > 0) {// if (oldCap >= MAXIMUM_CAPACITY) {//原始容量大于最大容量，不再扩容，间接返回原始table threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)//翻倍之后不超过最大容量，原始容量小于最大容量，且大于默认容量，那么容量翻倍，阈值也对应翻倍 newThr = oldThr << 1; } // 第二种状况：以后的 table 中无数据，然而阀值不为零，阐明初始化的时候指定过容量或者阀值，然而没有被 put 过数据， else if (oldThr > 0) newCap = oldThr;//此时的阀值就是数组的大小，所以间接把以后的阀值当做新 table 的数组大小即可。threshold = tableSizeFor(t); // 第三种状况，这种状况就代表以后的 table 是调用的空参结构来初始化的，所有的数据都是默认值。 else {//初始阈值为0，示意应用默认值，新的 table 也只有应用默认值即可 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 如果新的阀值是 0，那么就简略计算一遍就行了 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; // 依据上文中计算的新表容量和阈值，初始化新的 table // 这个 newTab 就是新的 table，数组大小就是下面这一堆逻辑所计算出来的 @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { // 遍历以后 table，解决每个下标处的 bucket，将其解决到新的 table 中去 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { // 开释以后 table 数组的对象援用（for循环后，以后 table 数组不再援用任何对象） oldTab[j] = null; // a、只有一个 Node，则间接 rehash 赋值即可 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; // b、以后的 bucket 是红黑树，间接进行红黑树的 rehash 即可 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // c、以后的 bucket 是链表 else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; // 遍历链表中的每个 Node，别离判断是否须要进行 rehash 操作 // (e.hash & oldCap) == 0 算法是精华，充分运用了上文提到的 table 大小为 2 的幂次方这一劣势，下文会细讲 do { next = e.next; // 依据 e.hash & oldCap 算法来判断节点地位是否须要变更 // 索引不变 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); // 原 bucket 地位的尾指针不为空(即还有 node ) if (loTail != null) { // 链表开端必须置为 null loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { // 链表开端必须置为 null hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab;}- 为什么要*2扩容？或者说，为什么HashMap的数组大小为2的幂
在实践学习中，Hash表的大小最好是素数，因为素数可能无效升高hash碰撞。然而HashMap并没有采纳这种做法。
在下面的源码中，咱们能够看到，HashMap在扩容的时候，数组的大小都是原来的两倍，这是因为在计算索引的时候，咱们应用的是size-1的n个全1二进制串和hash值进行与运算，这样能够保障计算出来的索引值肯定在0~size-1之间，不会越界。如图所示：
当HashMap值为2的幂的时候，size-1为全1二进制字符串，且扩容之后，本来有抵触的两个元素会找到各自的新索引地位。如图所示：
在代码中，这个步骤被进一步简化。如代码片段所示：
if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e;}// 原索引 + oldCapelse { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e;}因为hash值是一个整数，所以hash & oldCap的后果要么是0，要么是oldCap。所以，hashMap的扩容，实际上是将原来的数组分成两局部，一部分的索引不变，一部分的索引变为原索引+oldCap。这样就保障了原来的两个元素，扩容之后，肯定不会在同一个索引地位上。具体解释如图所示：
4.3 hash办法
也就是之前在实践局部所说的hash函数局部，将关键字key的值转换为惟一hash值，JDK1.8源码如下:
static final int hash(Object key) { int h; // 高 16 位与低 16 位进行异或运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}hashCode()函数通常和equals()函数进行比拟，hashCode()函数是依据对象的内存地址生成一个特定的数，因而，hashCode值雷同的对象不肯定雷同，hashCode值不同的对象肯定不雷同。
个别判断两个对象是否相等，先应用hashCode()函数判断内存地址，如果hashCode()函数值雷同，再应用equals()函数判断内存中的内容，如果hashCode()函数值不同，就不须要再应用equals()函数判断了。
这里h先设置成key值的hashCode，而后右移16位，再和原来的h进行异或运算，这样做的目标是为了缩小hash碰撞，进步查找效率。
之后如何从hash值映射到数组下标，在JDK1.7的源码如下所示:
static int indexFor(int h, int length) { return h & (length-1);}这里也解释了为什么HashMap的数组大小为2的幂，因为这样能够保障length-1为全1的二进制串，与操作之后计算出来的索引值肯定在0~size-1之间，不会越界，具体操作如图所示：
4.4 put办法
put办法次要是在HashMap中存储键值对，JDK1.8源码如下所示：
public V put(K key, V value) { return putVal(hash(key), key, value, false, true);//重点在于putVal办法}// 参数 onlyIfAbsent,针对曾经存在的value，值为true示意不批改；否则示意会替换本来的value值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 为空则进行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // (n - 1) & hash 计算失去索引 i，算法在上文有提到，而后查看索引处是否有数据 // ② 如果没有数据，则新建一个新的 Node if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 索引处有数据 else { Node<K,V> e; K k; // ③ 索引处的第一个 Node 的 key 和参数 key 是统一的，所以间接批改 value 值即可（批改的动作放在上面） if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // ④ 索引处的 bucket 是红黑树，依照红黑树的逻辑进行插入或批改 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // ⑤ 索引处的 bucket 是链表 else { // 遍历链表下面的所有 Node for (int binCount = 0; ; ++binCount) { // 索引处的 Node 为尾链 if ((e = p.next) == null) { // 间接新建一个 Node 插在尾链处 p.next = newNode(hash, key, value, null); // 判断是否须要转换为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st // 链表转换为红黑树，此办法在上文中也有介绍 treeifyBin(tab, hash); break; } // 以后 Node 的 key 值和参数 key 是统一的，即间接批改 value 值即可（批改的动作放在上面） if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 找到了雷同 key 的 Node，所以进行批改 vlaue 值即可 if (e != null) { // existing mapping for key V oldValue = e.value; // 批改 value 值 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); // 批改操作，间接 return 完结掉代码逻辑 return oldValue; } } // 记录构造发生变化的次数 ++modCount; // ⑥ 判断是否须要扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); // 新增的 Node，返回 null return null;}源代码所形象进去的具体的put流程可如下图所示：
在JDK1.7中，链表插入应用头插法，而在JDK1.8中，链表插入应用尾插法，
- JDK1.7 应用头插法的起因：思考到热点数据，前面插入的元素更有可能被最近应用，因而应用头插法。
- 头插法会使链表上 Node 的程序调转，而尾插法令不会，另外，头插法也会造成环形链死循环等问题，
参考文献
- 知乎专栏-HashMap原理详解，看不懂算我输（附面试题）
- 掘金社区-详解 HashMap 数据结构
- 美团技术团队-Java 8系列之重新认识HashMap