HashMap
引子
HashMap是很重要的数据结构，大部分的语言都实现了HashMap，Java也不例外，读HashMap源码可以了解到很多数据结构、计算机底层知识，难度中等，放心阅读。（基于JDK1.8）
背诵点
1、是无序且不安全的数据结构。
2、以key–value对的形式存储的，key值是唯一的（可以为null），一个key只能对应着一个value，但是value是可以重复的。
3、如果再次添加相同的key值，它会覆盖key值所对应的内容，这也是与HashSet不同的一点，Set通过add添加相同的对象，不会再添加到Set中去。
4、提供了get方法，通过key值取对应的value值，但是HashSet只能通过迭代器Iterator来遍历数据，找对象。
5、String的基础：重写了 equals ，就必须要重写 hashCode。所以我们平时都喜欢用 String 字符串来作为 key 的原因。因为String 类默认就帮我们实现了 equals 和 hashCode 方法的重写。
存放数据元素的数据结构
Java HashMap底层采用哈希表结构（数组+链表、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(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
源码中很重要的常量：
// 数组默认的初始化长度16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 数组最大容量，2的30次幂，即1073741824
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;
// 链表转换为红黑树时，数组容量必须大于等于64
static final int MIN_TREEIFY_CAPACITY = 64;
// HashMap里键值对个数
transient int size;
// 扩容阈值，计算方法为 数组容量*加载因子
int threshold;
// HashMap使用数组存放数据，数组元素类型为Node<K,V>
transient Node<K,V>[] table;
// 加载因子
final float loadFactor;
// 用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），直接抛出ConcurrentModificationException异常
transient int modCount;
为什么初始化大小为什么是16？
将二进制进行按位于，(16-1) 是 1111，末位是1，这样能保证计算后的index既可以是奇数也可以是偶数，并且只要传进来的key足够分散，均匀那么按位于的时候获得的index就会减少重复，这样也就减少了hash的碰撞以及hashMap的查询效率。
如何序列化的？
实际：用于存储数据的table字段使用transient修饰，通过transient修饰的字段在序列化的时候将被排除在外。
那么HashMap在序列化后进行反序列化时，是如何恢复数据的呢？
HashMap通过自定义的readObject/writeObject方法自定义序列化和反序列化操作。
这样做主要是出于以下两点考虑：
1、table一般不会存满，即容量大于实际键值对个数，序列化table未使用的部分不仅浪费时间也浪费空间；
2、key对应的类型如果没有重写hashCode方法，那么它将调用Object的hashCode方法，该方法为native方法，在不同JVM下实现可能不同；换句话说，同一个键值对在不同的JVM环境下，在table中存储的位置可能不同，那么在反序列化table操作时可能会出错。
所以在HashXXX类中（如HashTable，HashSet，LinkedHashMap等等），我们可以看到，这些类用于存储数据的字段都用transient修饰，并且都自定义了readObject/writeObject方法。
红黑树的作用
JKD1.8之后的底层结构是：数组 + 链表 + 红黑树 (预值为8 如果链表长度>=8则会把链表变成红黑树 )
为了解决：JDK1.8以前hash冲突所导致的链化严重的问题。
因为链表结构的查询效率是非常低的，不像数组，能通过索引快速找到想要的值，链表只能挨个遍历，当hash冲突非常严重的时候，链表过长的情况下，本身散列列表最理想的查询效率为O(1)，当时链化后链化特别严重，查询退化为O(n)。
当链表中的元素超过8个（TREEIFY_THRESHOLD）并且数组长度大于64（MIN_TREEIFY_CAPACITY）时，会将链表转换为红黑树，转换后数据查询时间复杂度为O(logN)链表就会变成红黑树，红黑树其实就是一颗特殊的二叉排序树，红黑树相当于排序数据，可以自动的使用二分法进行定位，性能较高。
put方法
HashMap通过hash方法计算key的哈希码，然后通过(n-1)&hash公式（n为数组长度）得到key在数组中存放的下标。当两个key在数组中存放的下标一致时，数据将以链表的方式存储。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果数组(哈希表)为null或者长度为0，则进行数组初始化操作；创建HashMap对象的时候并不会直接初始化数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 根据key的哈希值计算出数据插入数组的下标位置，公式为(n-1)&hash
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果该下标位置还没有元素，则直接创建Node对象，并插入
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果目标位置key已经存在，则直接覆盖
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果目标位置key不存在，并且节点为红黑树，则插入红黑树中
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)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);
// 如果链表长度大于等于TREEIFY_THRESHOLD，则考虑转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); // 转换为红黑树操作，内部还会判断数组长度是否小于MIN_TREEIFY_CAPACITY，如果是的话不转换
break;
}
// 如果链表中已经存在该key的话，直接覆盖替换
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;
}
如何降低hash碰撞
1、把高16位值和当前h的低16位进行了混合，这样可以尽量保留高16位的特征。
2、选择异或运算来混合，可以让结果的随机性更大，哈希碰撞的概率就更小。
get方法
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 判断数组是否为空，数组长度是否大于0，目标索引位置下元素是否为空，是的话直接返回null
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<K,V>)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;
}
resize扩容
阈值(threshold) = 负载因子(loadFactor) x 容量(capacity)
当HashMap中table数组(也称为桶)长度 >= 阈值(threshold) 就会自动进行扩容。
比如数组容量为16，加载因子为0.75，那么扩容阈值为16*0.75=12，即HashMap数据量大于等于12时，数组就会进行扩容。
因为：数组容量的大小在创建的时候就确定了，所以扩容实质是：重新创建一个指定容量的数组，然后将旧值复制到新的数组里。
特点：扩容这个过程非常耗时，会影响程序性能。所以加载因子是基于容量和性能之间平衡的结果。
JDK1.8在扩容时通过高位运算e.hash & oldCap结果是否为0，来确定元素是否需要移动，也就是有的hash值会移动位置，有的不移动位置。
为什么是以2的整数次幂扩容？
table数组长度必须是2的次方数，扩容其实每次都是按照上一次tableSize位运算得到的就是做一次左移1位运算，假设当前tableSize是16的话，16转为二进制再向左移一位就得到了32 即 16 « 1 == 32 即扩容后的容量。
有个函数，tableSizeFor 的功能（不考虑大于最大容量的情况）是返回大于等于输入参数且最近的2的整数次幂的数。比如10，则返回16。
该算法让最高位的1后面的位全变为1。最后再让结果n+1，即得到了2的整数次幂的值了。
为什么扩容采用位移运算？
因为cpu不支持乘法运算，所有的乘法运算它最终都是再指令层面转化为了加法实现的，这样效率很低，如果用位运算的话对cpu来说就非常的简洁高效。
遍历
HashMap是无序的，输出元素顺序和插入元素顺序一般都不一样。但是多次发现每次遍历的顺序都是一样的，如何做到的？
编译成class文件后，发现下面这段代码实际会被转换为iterator遍历
Set<Entry<String, Object>> entries = map.entrySet();
Iterator var3 = entries.iterator();
while(var3.hasNext()) {
Entry<String, Object> entry = (Entry)var3.next();
System.out.println((String)entry.getKey() + ": " + entry.getValue());
}
过程：从头查找HashMap数组中的不为空的结点，如果该结点下存在链表，则遍历该链表，遍历完链表后再找HashMap数组中下一个不为空的结点，以此进行下去直到遍历结束。
那么，如果某个结点下是红黑树结构的话，怎么遍历？
其实当链表转换为红黑树时，链表节点里包含的next字段信息是保留的，所以我们依旧可以通过红黑树节点中的next字段找到下一个节点。
将当前模数值赋值给期待的模数值，所以在遍历的时候，别的线程调用了当前hashMap实例的增删改方法，模数值会改变，那么expectedModCount和modCount就不相等了，遍历操作直接抛出ConcurrentModificationException
这就是2个modCount的比较导致的快速失败（fast fail）