HashMap
JDK8版本对HashMap进行优化，对哈希冲突产生的链表，设置了阈值长度8，当超过8个元素的时候，就会转换为红黑树
因此 JDK8 的HashMap 是由 数组+链表+红黑树 组成的
让链表查找的 O(n) 复杂度降到了红黑树的 O(logn) 复杂度
首先了解一些属性：
DEFAULT_INITIAL_CAPACITY = 1 << 4;：默认的初始容量为16MAXIMUM_CAPACITY = 1 << 30;： 最大容量DEFAULT_LOAD_FACTOR = 0.75f;： 默认的负载因子为 0.75fTREEIFY_THRESHOLD = 8;：单链表转为红黑树的节点数目阈值（大于等于该值时转化）UNTREEIFY_THRESHOLD = 6;：红黑树退化为单链表的节点数目阈值（小于该值时退化）MIN_TREEIFY_CAPACITY = 64;：单链表能够转换为红黑树的最小容量（大于等于该值才能转换为红黑树，否则进行扩容）
哈希表的组成单元：
Nodestatic class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; }数据结构的一些字段（
transient关键字用于表示序列化时不应该序列化该字段）：// 哈希表的基本结构：数组 transient Node<K,V>[] table; // 键值对集合 transient Set<Map.Entry<K,V>> entrySet; // 大小 transient int size; // HashMap 的修改次数，用来防止在迭代时修改 ConcurrentModificationException transient int modCount; // 扩容的阈值 int threshold; // 加载因子，用于计算扩容阈值：threshold = capacity * loadFactor final float loadFactor;计算表容量的方法（返回一个等于或大于
cap的2次幂数）：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; } 计算键的哈希值：将 hashCode 的高16位和低16位进行异或，让哈希码更均匀
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
计算哈希值对应table对应的下标：
// capacity 是 table 的长度 // 这样子可以通过位运算快速的计算出对应的下标 (capacity - 1) & hashcode
构造方法
初始化 HashMap，通常是指定加载因子 loadFactor（默认是0.75f）以及计算表的阈值 threshold（默认是大于等于 initalCapacity 的2次幂值）
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}put 方法
先看看 HashMap 是如何存储一个键值对的
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}putVal
首先检查 table 是否为空（在构造函数中并未对该 table 初始化）或其长度为0，调用
resize()方法，将 table 初始化长度为16的数组；
计算对应的位置
(n - 1) % hash，判断是否有元素，如果没有元素则直接赋值；
如果有元素，进行下面的判断：
该元素是否和 key 相同，如果相同则覆盖
是否为红黑树节点，如果是则插入到红黑树中；
不是红黑树且对应位置上的 key 不相同，遍历链表并统计链表节点个数
binCount:在该链表中找到了相同的 key 节点，则覆盖；
如果没有找到则插入到链表的最后面（尾插法）
如果此时链表个数超过了 8 则调用
treeifyBin转换为红黑树
如果是覆盖已有的值，里面的
e是被覆盖的节点，在后面将里面的 value 替换为新的；如果是新增加的值，里面的
e是为空，因此会 size ++，同时判断是否超过 threshold 值，超过则进行扩容resize
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;
// 对应位置为空，直接赋值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 对应位置不为空，则判断是链表还是红黑树
else {
Node<K,V> e; K k;
// p 是对应位置的元素
// 如果 p 的键和 key 相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 红黑树，
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 统计当前链表的节点个数
for (int binCount = 0; ; ++binCount) {
// 到链表最后都没有找到相同的key，则插入到最后面
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 链表节点个数超过8，转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果在链表中找到相同的 key，则覆盖原来的值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 覆盖相同 key 的节点的 value
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;
}里面的
afterNodeAccess和afterNodeInsertion都是类似回调的方法，当节点插入或者访问时回调该方法，HashMap 内是空实现，LinkedHashMap重写了这部分方法
resize扩容
初始化 table 或者将 table 的容量扩大两倍，返回扩容的 table；
计算新的 capacity 和 threthold
如果已经超过
MAXIMUM_CAPACITY则不会进行扩容（最大值是1 << 30，一般数组也开不了比这个还要长）新容量是旧容量的两倍，新的 threshold 也是旧的两倍;
如果都没有进行初始化（都是0，调用空构造函数会这样），则赋值默认值，容量是 16，threshold 是
16 * 0.75 = 12
创建长度为新容量大小的数组；并将之前的数组内容赋值到新数组
对于只有一个节点，直接赋值到新数组的新位置
e.hash & (newCap - 1)
如果是红黑树，则将其分为两部分（当红黑树的节点小于等于 6时， 会退化为单链表）
如果是单链表，则根据和
oldCapacity（2次幂值）进行 与运算，判断最高位是否为1分为两部分，为0的放在原来的位置，为1的放在 原来位置 +oldCapacity的位置；（这里的最高位是指oldCapacity二级制中 1 的位置）
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 计算新的容量以及 threshold
// 当前已经容量
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 当前还没有容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// threshold 和 capacity 都没有初始化，因此进行初始化
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 判当前 j 位置是否为空
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 原本位置只有这么一个节点
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 将红黑树的节点重新分配
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 根据最高位是0 还是1来判断放在哪个单链表
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
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;
}
}
}
}
}
return newTab;
}treeifyBin转换为红黑树
将链表转换为红黑树：
只有 table 的容量大于等于 64 时才会触发转换操作，否则只会进行扩容（扩容会将这个单链表分为两部分）
将链表的Node转换为TreeNode（此时还是单链表结构）
调用
TreeNode#treeify将单链表结构转换为红黑树结构；
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果当前长度小于 64，就会扩容，而不是转换为二叉树
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
// 将 Node 组成的单链表转换为 TreeNode 组成的单链表
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 转换为红黑树
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}put方法总结
put 方法的大致流程：
对 key 进行哈希运算
hash(key.hashCode())，通过(capacity - 1) & hashcode来计算出在哈希表的位置；检查位置上是否存在 key 相同的节点，如果有则覆盖，否则插入到对应位置（如果是链表则尾插，如果是红黑树则以红黑树的方式插入）
如果当前位置的链表结点个数大于等于8个，且table的容量大于等于64时，则将链表转换为红黑树，否则进行扩容；
如果是新插入节点，当哈希表大小超过 threshold 时触发扩容；
resize 方法总结：
计算新的容量和threshold，都是原来的两倍；如果没有设置则初始化为 16 和 16 * loadFactor 加载因子；
将原来数组的元素复制到新数组：
对于红黑树，分为两部分（当红黑树的节点数量小于等于6时，会退化为单链表结构）
对于单链表，分为两部分
对于单个元素，直接赋值
分为两部分是通过和旧容量进行与运算，判断是放在原来的位置还是更高位的位置；
get 方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}getNode
先计算 hash 对应的位置 (n - 1) & hash:
对于单链表：遍历判断是否存在 key 相同的节点；
对于红黑树：通过
TreeNode.getTreeNode来获取与 key 相同的节点；这个查找过程是类似二分，因此时间复杂度是 O(logn)
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> 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<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;
}注意点
允许插入键为null或值为null的键值对
哈希计算方法 hash 对于 null 值是返回 0，因此绝对会分配到数组下标为0的位置；
put 方法并不会对键为null或者值为null进行检查，因此允许插入键为 null 或者值为 null 的键值对；
键的比较
put 和 key 方法比较已有键和传入键的方法是比较 hashcode 和 equals，只有两者都返回 true 的时候才会判断为相同；
因此对于自定义的类，除了需要重写 equals 外，还需要重写 hashCode
重写 equals：默认的
Object#equals是比较两者的引用地址是否相同，对于内容相同对象该方法会返回false，重写保证对象内容都相同时返回true；重写 hashcode：默认的
Object#hashCode会根据内存地址返回哈希码，因此也需要进行重写保证内容相同的对象返回 true（不保证内容不相同的 hashcode 一定不一样）
CurrentModificationException
在开头中的属性介绍中，有一个属性 modCount 记录着 HashMap 的修改次数，作用是为了检测并发修改的行为；
在多线程中，可能存在一个线程在迭代 HashMap，另一个线程修改了这个 HashMap，就会导致一些未知的异常，因为 HashMap 并不是一个线程安全的集合；
因此使用 modCount 统计修改次数，在迭代前后会比较这个值是否相同，如果不同则会抛出 CurrentModificationException 异常；
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount; // 迭代前统计数量
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
// 迭代结束后比较
if (modCount != mc)
throw new ConcurrentModificationException();
}
}因此如果想要在迭代过程中删除元素，需要使用迭代器实现，使用其提供的 Iterator#remove ；
红黑树介绍
只是作为简单的介绍，并不解析代码相关的东西（或许以后有空再补充）；
红黑树是一种自平衡的平衡二叉树，可以再 O(logn) 的时间复杂度内完成查找、插入、删除的操作；
为什么需要红黑树？
对于普通的二叉搜索树，如果插入的元素是升序，就会导致二叉搜索树退化为一个单链表的结构，时间复杂度从
O(logn)退化到O(n)红黑树能够对于子树高度差大于1时旋转，使其重新平衡，在上面的二叉搜索树的例子中，就能避免退化成单链表
相关问题
为什么默认负载因子是0.75？
0.75被认为在大多数场景下能在时间和空间之间取得较好的平衡的数值；
如果负载因子小了，就会导致频繁扩容，空间利用率不高，哈希冲突的概率降低，导致查找效率比较高，但是扩容频繁会增加性能开销（需要申请更大长度数组，还需要进行 rehash 移动原来的数据）
如果负载因子大了，会减少扩容次数，空间利用率比较高，但增加哈希冲突的概率，导致查找效率降低（元素可能都存在某一个位置上）
为什么JDK8增加了红黑树？
在JDK8之前，哈希表是由数组+链表组成的，哈希冲突比较频繁时，单链表可能会比较长，查找时需要遍历单链表会导致时间复杂度不是 O(1) 了；
因此使用红黑树对单链表进行优化，当单链表的长度超过指定长度（8）时，会将单链表转换为红黑树，以提高查找效率；
为什么红黑树的转换阈值是8，而不是直接使用红黑树？
红黑树的节点大小是普通节点的两倍（包含了维持红黑树结构的字段），不直接使用红黑树是为了节省空间；
注释上面说，根据泊松分布（一种描述随机事件发生次数的分布），哈希冲突导致节点数量到达8的概率是0.00000006，这个概率非常小；少于这个数值使用单链表的查找效率也比较高，相较于红黑树也会比较节省内存；
选择8这个值是基于空间和时间的平衡；
为什么红黑树的节点少于等于6是就会退化为链表？
为了节省空间和时间，单链表相较于红黑树在节点少的情况下，遍历速度比较快，同时也比较省内存；
为什么不小于 8 就直接退化为链表呢？
需要留有一个缓冲的空间，避免反复转换为红黑树和退化为链表（转化过程也是有开销的）
为什么数组的容量要被设计为2次幂？
方便计算键的哈希值在数组中对应的位置下标，通过 (capacity - 1) & hash 就能直接计算，效果等同于模运算，同时比模运算高效；
同时在扩容时，利用原位置和新位置的二进制关系，快速确认新位置，避免了重新hash计算带来的开销；
原位置的下标是和 后面x位都是1 的二进制数进行与运算得到的；
扩容时容量为原来的两倍，新位置的下标是和后面的 x+1位都是1 的二进制进行与运算得到，
原位置和新位置的区别只有第 x +1 位的区别，因此只需要判断 第 x + 1 的区别，就能直接计算出新位置；