Java8 HashMap
Java8 在 Java7 的基础上对 HashMap 进行优化，由数组+链表结构，改为了数组+链表+红黑树结构组成。
查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，在 Java8 中，当链表中的元素达到了 8 个时，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。
Java8 HashMap 结构
put过程
put 过程
1、在第一进入会触发resize（）进行一次扩容操作
2、根据位置判断该位置是否有参数，如果没有参数则将创建一个新结点
3、否则，进入查询，首先，判断该位置的第一个数据和我们要插入的数据，key 是不是"相等"，如果是，取出这个节点
4、如果该节点是代表红黑树的节点，调用红黑树的插值方法
5、如果该节点不是红黑树，则表示是链表结构，则插入到最后的位置
6、TREEIFY_THRESHOLD 为 8，所以，如果新插入的值是链表中的第 8 个，会触发下面的 treeifyBin，也就是将链表转换为红黑树
7、如果在该链表中找到了"相等"的 key(== 或 equals)，此时 break，那么 e 为链表中[与要插入的新值的 key "相等"]的 node
8、e!=null 说明存在旧值的key与要插入的key"相等"，做 value 覆盖操作
9、如果 HashMap 由于新插入这个值导致 size 已经超过了阈值，需要进行扩容
/**
* Tree version of putVal.
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K, V> root =(parent != null) ? root() : this;
for (TreeNode< K, V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0
) {
if (!searched) {
TreeNode<K, V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null)
)
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K, V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K, V> xpn = xp . next;
TreeNode<K, V> x = map . newTreeNode (h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K, V>) xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
红黑树插入：
1、 红黑树初始为空树
2、插入结点，设置结点为黑结点，并设置为根结点
3、插入结点的父结点为黑结点，则可以直接插入
4、插入结点的父结点为红结点，插入结点的父结点是祖父结点的左子结点，且叔叔结点为空或者为黑结点
5、如果该结点是父结点的左子结点，进行右旋操作，并将父结点变黑，祖父结点变红
6、如果该结点是父结点的右子结点，进行左旋操作，并将父结点变黑，祖父结点变红
7、插入结点的父结点为红结点，插入结点的父结点是祖父结点的右子结点，且叔叔结点为空或者为黑结点
8、如果该结点是父结点的右子结点，进行左旋操作，并将父结点变黑，祖父结点变红
9、如果该结点是父结点的左子结点，进行右旋操作，并将父结点变黑，祖父结点变红
get过程
相对于 put 过程，get 过程就要简单很多：
1、通过 hash 值，确定在数组中的位置
2、判断数组中取到结点是否要取的结点，如果是则直接进行返回；如果不是则进行链表或红黑树结点查询
3、进行判断该位置使用数据结构是链表结构还是树形结构
4、如果是树结点，查询树结点并将数据返回
5、如果是链表结构，进入循环体，根据 hash值 与 key 相匹配获取结点对象并返回
resize 过程
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K, V>[] oldTab = table;
int oldCap =(oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
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
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;
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;
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;
}
resize过程
1、如果hash表容量已达到最大临界值，则返回原数组，并且扩容临界值保持不变，否则，数组扩容一倍且扩容后的表不能大于限制值，将扩容临界值（该临界值还未乘以加载因子）翻倍
2、第一次创建，使用默认值生成相关参数
3、第一次扩容初始化阈值
4、更新扩容临界值
5、遍历数组中每个结点
6、如果取出来的结点不存在下一个元素，则重新计算对应新结点的位置
7、判断当前节点的hash值的比hash表容量高一位的二进制位是否为1，如果为0，则结点保持原位，如果为1，到新的结点位置
8、原位置的链表尾，将当前结点设置为链表头
9、当前前点追加到尾结点的下一结点
