HashMap简介
在 Java8 中，HashMap 是由数组和链表构成的数据结构，当它的链表长度超过8时，会将链表转成红黑树。它是基于哈希算法实现的一个结构，存取时，根据键值来计算出 HashCode, 再根据 HashCode 来定位到数组中相应的位置，同时它支持 null 键值对，但是不保证有序，也不保证顺序永远不会变化，而且它是线程不安全的。
HashCode
上面说到了 HashCode, HashCode 用于指定数组的索引， 可以快速找到对象再数组的位置，再通过遍历这个数组下的链表来获取存储的值，在存入的时候，也会根据键值生成对应的 HashCode。
时间复杂度
如果在理想的状况下， 例如每个对象都有独属于自己的 HashCode,那么获取这个对象的时间复杂度是 O(1), 反之，最坏的情况是 O(N)，所以一个好的哈希算法可以让时间复杂度趋向于 O(1)。
负载因子
默认 HashMap 的长度为16，但是当 HashMap 需要扩容时，参与影响的参数还有负载因子。
默认的负载因子大小为 0.75，即当前使用的容量超过 总容量*负载因子 的数量时，则会扩容，默认的扩容是一次扩大两倍。
所以可以根据计算知道， 默认情况下，HashMap 第一次扩容是在存入第13个对象的时候。
当然我们也可以自己定义数组的容量和负载因子。
public HashMap(int initialCapacity, float loadFactor)
//第一个参数为数组大小， 第二个参数为负载因子
值得一提的时，HashMap 的扩容也是体力活，需要创建一个新的数组，再把原来的数据存放到新的数组里，同时需要重新计算 HashCode，来确定原来的对象在新的数组中的位置。
至于默认是0.75的原因，我认为是在数组容量不变的情况下，存放的键值对越多，会导致链表越长（红黑树也是），从而影响查找的效率，所以扩容可以有效的解决这个问题，而0.75的默认值也是一个权衡问题，如果后期存储的键值对数量庞大起来，那么可以比较好的提升查找效率，但是也会牺牲相当一部分大的空间。
哈希碰撞
听着厉害，其实就是 一个以上的键值对同时分配到了同一个 HashCode, 这个时候就往这个 HashCode 对应的数组位置里的链表里塞，如果是 Java8, 链表长度大于8后，就会转化为红黑树。
当然一个好的 Hash 算法，应该尽量少的避免哈希碰撞，在一定范围内， 也该尽量平均的分配 HashCode。
源码分析 Java8
put 过程
public V put(K key, V value) {
//这里调用了 putVal 方法， 传入了 HashCode, key, value 等信息。
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
//这两个 boolean 值我直接引用源码中的注释 可以知道 onlyIfAbsent 为 true 则不能覆盖已经存在的值，
//evict 为 false 时 则需要创建新的表，使用时这两个值与我们无关，我们只需要调用 put 方法就好了。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//如果数组为空或者数组长度为0 扩容！
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//如果 HashCode 对应的位置没有其它对象，则创建一个新的 Node
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//（1）如果这个位置有对象，并且 HashCode 和 key 相等，那么先获取这个对象的索引，后面用作替换
e = p;
else if (p instanceof TreeNode)
//如果这个Node已经被转成红黑树的话，那么根据红黑树的规则插入
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);
//如果当前链表长度大于最大值（默认是8），则转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//和注释（1）中一样的逻辑
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)
//如果 onlyIfAbsent 为false，说明可以替换旧值，或者旧值是空值的情况下
//都可以替换
e.value = value;
afterNodeAccess(e);
//返回旧值，
return oldValue;
}
}
++modCount;
if (++size > threshold)
//如果存储的键值对达到扩容的要求，则扩容
resize();
afterNodeInsertion(evict);
return null;
}
总结 put 流程
首先判断数组是否为空或者长度为0，是的话则扩容，再判断对应的数组位置中是否有值，没有的话直接为其创建新的 Node 作为链表头放入，如果上述条件不符合
时，则遍历该数组位置中的链表，将新键值对放在链表尾部，如果是红黑树的话，则按红黑树的规则插入。
当链表长度大于8时，转为红黑树，当达到扩容阈值时，会扩容，put成功后，它将返回旧值。
扩容方法 resize
好长好累
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) {
// MAXIMUM_CAPACITY的大小是 1 << 30 ，所以这里就是太大了，直接返回最大值给它，表也不变了。
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果老数组*2在 HashMap 允许的范围内，那么计算出新数组的扩容阈值，就是原来的两倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
//这里是初始化，针对旧数组为空或者长度为0，但是扩容阈值大于0的情况
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//这里是默认的初始化，针对旧数组为空或者长度为0的情况。
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
// 如果扩容阈值为0， 则根据新的数组容积和负载因子计算。
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新 threshold
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) {
//将旧数组的对象替换为null，help GC
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
//接下来的过程可能比较复杂，大致是降一个链表分为两条链，
//然后根据它们对应的 HashCode 放到数组中相应的位置。
//这条链是应放在原位的链
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) {
//位运算为0时，留在原位。
if (loTail == null)
//lo链的链头
loHead = e;
else
//lo链长度不为0时，依次添加在尾部
loTail.next = e;
//lo链尾部是当前节点，目测主要是为了避免上面if一直执行
loTail = e;
}
else {
//如果位运算结果不为0后，则将节点放入hi链
//接下来的大致逻辑和上面一样
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);//遍历链表
if (loTail != null) {
//按原来的位置将lo链放到新数组中
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
//按 原来的位置+原来数组的容量 的位置将 hi链放入数组中
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//返回新的数组
return newTab;
}
扩容应该算是 HashMap 最为复杂的方法了，当然作为 Java8 添加了新特性的 HashMap, 其中引入了红黑树作为防止链表过长导致的查找时浪费也是很重要的一环。
这里需要注意的是，任何一个小于2的倍数的数与2的倍数 & 运算都是等于 0， 所以可以看扩容方法中的 loHead 链 和 hiHead 链是根据元素自身的HashCode与旧数组大小比较来区分的。
该部分小结
通过上面的 put 和 resize 方法的源码，可以很好的了解 HashMap 中的的数据结构，同时在这里也和 Java7 的 HashMap 做一些比较(程序员向前看，了解就好，主要还是看 Java8 的代码，还是懒)：
- 当 Hash 碰撞时（多个键值对分配到了同样的 HashCode），Java7 会在链表头插入新键值对，而 Java8 会在尾部插入。
- 扩容后转移数据时，Java7 链表的顺序会颠倒，而 Java8 依旧保持原来顺序
（源码上就这句注释醒目）
// preserve order
- Java8 引入了红黑树
接下来稍微介绍下红黑树
红黑树的特性
红黑树是一种不严格的二叉平衡查找树，但它的特性又让它成为一个合格的平衡二叉查找树。
这里的平衡，可以理解为稳定，即一个平衡二叉树在动态更新的情况下，还能很好的保持高度在 log2(N) 左右，在不高出太多的情况仍保持一个对数级的高度。
红黑树规则
一棵树如果是红黑树，那么它要满足如下规则
- 根节点是黑色的
- 每个叶子节点都是黑色的空节点
- 任何红色节点的相邻节点不能是红色，即红色节点之间需要用黑色节点隔开
- 每个节点，从该节点到叶子节点的所有路径，其中的黑色节点数量都是相等的
为什么说红黑树是近似平衡的
如果将红色节点都去掉，那么根据红黑树规则的第四点，那么将会得到一颗完全树，这时候黑树的高度是不会高于 log2(N)的。
这时候我们根据规则第三点，因为每个红色节点之间都有黑色节点隔开，所以红色节点的高度也不会超过 log2(N)。
因此红黑树的高度将近似于 2log2(N)。2 是一个常数，所以可以说红黑树是近似平衡的。
网友评论