HashMap线程不安全，底层数组+链表+红黑树
面试重点是put方法，扩容
总结
put方法
HashMap的put方法，首先通过key去生成一个hash值，第一次进来是null，此时初始化大小为16，i = (n - 1) & hash计算下标值，第一次获取是null，直接放入一个Node节点，如果不是null，分成下面三种情况
1）如果发现hash和key相等，将原来的覆盖
2）不相等，就要用到链表，通过尾插法插入到尾部。超过8转成红黑树
3）如果是TreeNode，插入即可
扩容
首先，上面put方法每次都会计算大小
如果超过16*0.75，即12就会r调用resize方法
这里主要是老数组上面元素转到新数组上面去的逻辑
遍历，如果老数组上面元素不是null
这里又是几种情况
1）如果next下标是null，
说明只有一个元素，直接重新计算下标放入新数组
2）判断是否是TreeNode
对TreeNode树进行拆分，转到新数组，不一定在一起。拆分后不一定还是树，这里各种情况，看节点对应的是高位还是低位。判断低位个数如果不超过6，转成链表（TreeNode转成Node）。高位也一样。否则重新生成红黑树（根据是否有高地位判断是否需要重新生成红黑树）
3）否则说明是个链表，
将链表转到新数组上面去，扩容后重新计算hash后下标不一定还是相同的，所以不能直接转到新数组，但是扩容后下标是有规律的。扩容后只有两种情况，低位和高位。 哪些节点是在低位链表上面，哪些节点是在高位链表上面。然后放到新数组即可。
源码如下：
/**
* 默认的初始容量-必须是二的幂。2的4次方=16，
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 如果隐式指定了更高的值，则使用最大容量由带有参数的构造函数中的任何一个执行。必须是二次方<=1<<30。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 在构造函数中未指定时使用的负载系数。
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 使用树而不是列表作为存储箱的存储箱计数阈值。当向至少有这么多节点的bin添加元素时，bin会转换为树。该值必须大于2，并且应至少为8，以符合树木移除中关于收缩后转换回普通垃圾箱的假设。
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 在调整大小操作期间取消尝试（拆分）垃圾箱的垃圾箱计数阈值。应小于TREEIFY_THRESHOLD，并且最多6个，以便在去除时进行收缩检测。
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 可以将垃圾箱树化的最小桌子容量。（否则，如果一个bin中的节点太多，则会调整表的大小。）应至少为4*TREEIFY_THRESHOLD，以避免调整大小阈值和树化阈值之间的冲突。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 基本hash bin节点，用于大多数条目。（TreeNode子类见下文，Entry子类见LinkedHashMap。）
*/
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
new HashMap，默认无参构造，负载因子0.75
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 这个是0.75f
}
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;//记录修改次数
put方法
//put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 计算key.hashCode（）并将哈希的高位扩展（XOR）到低位。因为该表使用了两个掩码的幂，所以仅在当前掩码之上以位为单位变化的哈希集总是会发生冲突。（已知的例子包括在小表中保存连续整数的浮点键集。）因此，我们应用了一种变换，将高位的影响向下扩展。比特扩展的速度、效用和质量之间存在权衡。由于许多常见的哈希集已经合理分布（因此不会从扩展中受益），并且因为我们使用树来处理箱中的大型冲突集，所以我们只需以最便宜的方式对一些移位的比特进行异或，以减少系统损失，并将最高比特的影响纳入其中，否则由于表绑定，这些比特将永远不会用于索引计算
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
首先通过hash方法，传入key计算出一个int类型的hash值。
这里为什么不直接用key.hashCode()的值呢？
key.hashCode()计算出一个hash值，然后赋值给h，h右移16位，然后两个做异或运算
计算的值右移16位，右移之前和右移之后的值进行异或^运算，得到最终的hashcode，这个最终的值时通过低位和高位一起异或运算算出来的。这样高位也参加到了计算中，高位都是0.
下面还有计算数组下标的
i = (n - 1) & hash，第一次n=16，做&运算，何为&运算，即都为1则为1。
比方15的二进制时是 0000 1111 而上面计算得到的hash值和这个做&运算，值在0-15之间。这样(n - 1) & hash计算是为了使均匀分布。0-15出现频率都差不多。hash值比较均匀，最后计算的i就比较均匀。为啥要n-1，如果16的话，做&运算得到结果就两种
然后调用putVal方法，入参事key的hash值，key，value，false，true
这里是put的核心方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//定义tab，p，n，i，初始化一些变量
Node<K,V>[] tab; Node<K,V> p; int n, i;
//这里为啥不直接用table？性能问题，我们自己初始化变量是属于栈中，而table是堆中，不用每次从堆中去拿table。
//第一次进来是null
if ((tab = table) == null || (n = tab.length) == 0)
//这里调用resize，初始化及扩容，第一次返回16
n = (tab = resize()).length;//那=16
//下面这个i是如何来的？i = (n - 1) & hash，算出数组下标，如果没有值，是null，就放到这里。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果这个位置不是null，这里就涉及到链表
else {
//如果这个位置上不是null，说明这个位置有东西
Node<K,V> e; K k;
//如果发现hash和key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//直接赋值到e，下面不会走了
e = p;
//如果这个位置上的是TreeNode类型
else if (p instanceof TreeNode)
//进行红黑树的插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//不相等，就要用到链表，这里for循环，
//如何加？通过Node对象的next属性
for (int binCount = 0; ; ++binCount) {
//binCount=0，有一个节点，所以下面要8-1=7，binCount=8
//尾插法，找到尾节点，尾节点的next==null
if ((e = p.next) == null) {
//将新的节点给到next属性，完成链表插入
p.next = newNode(hash, key, value, null);
//如果bincount的大小>=8-1=7，binCount=7，链表有8个节点，但是你自己上面newNode还新增了一个，其实现在有9个节点
//为啥超过8个转红黑树，这个和红黑树的性能有关
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果发现链表中有相等的，也是无需做什么了，直接覆盖值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果e不是null，
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
更新value
e.value = value;
afterNodeAccess(e);
//将原来老的value返回
return oldValue;
}
}
++modCount;
//统计++size，hashmap大小，和域值threshold（16*0.75）比较
//不停往集合put，如果大于12（threshold）个，就会调用resize扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
* 初始化或加倍表大小。如果为null，则根据字段阈值中的初始容量目标进行分配。否则，因为我们使用的是二次幂展开，所以每个bin中的元素必须保持在同一索引，或者在新表中以二次幂偏移量移动。
*
* @return the table
*/
transient Node<K,V>[] table;
int threshold;
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//一开始时null
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)
//左移1位，翻倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//一开始0，走到这里执行
newCap = DEFAULT_INITIAL_CAPACITY;//默认16（1>>4）
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//16*0.75=12这个和扩容有关系，扩容的一个域值
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;//第一次将12赋值给threshold
@SuppressWarnings({"rawtypes","unchecked"})
//这里开始创建Node，第一次newCap=16，这里创建出一个16大小的node数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//将16给到table，table=16
table = newTab;
//老数组上面元素转到新数组上面去
if (oldTab != null) {
//遍历老数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果老数组这个元素不是null
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果为null，说明只有一个元素
if (e.next == null)
//重新计算放到新数组中
newTab[e.hash & (newCap - 1)] = e;
//判断是不是TreeNode
else if (e instanceof TreeNode)
//对TreeNode树进行拆分，转到新数组，不一定在一起。拆分后不一定还是树，这里各种情况，看节点对应的是高位还是低位。判断低位个数如果不超过6，转成链表（TreeNode转成Node）。否则还是TreeNode，然后判断高位低位，如果低位，不用动，如果有高位，说明树进行了拆分，重新生成红黑树。
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//是个链表，将链表转到新数组上面去，扩容后重新计算hash后下标不一定还是相同的，所以不能直接转到新数组，但是扩容后下标是有规律的。只有两种情况，低位和高位
//哪些节点是在低位链表上面，哪些节点是在高位链表上面
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//e.hash & oldCap==0判断在低位还是高位，等于0在低位
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);
//低位链表放到newTab
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//高位链表放到newTab
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;//第一次调用的最后返回16
}
转红黑树的方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//MIN_TREEIFY_CAPACITY=64，判断数组长度是否小于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;
do {
//将这个链表上面的Node节点遍历变成TreeNode节点，完成转换
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
//将prev也赋值，改成双向链表，方便去拿前一个节点
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
//将TreeNode节点转成红黑树
hd.treeify(tab);
}
}
红黑树查询删除等时间复杂度都是log（n），要快一点，提升查询性能
并不是超过8就一定转成红黑树，而是还要判断数组长度，64比较，小于64扩容
为啥要判断数组长度？和扩容有关，resize扩容，将链表拆分成两个短链表。
扩容，两个地方进行扩容
一个是计算hashmap大小大于12进行扩容
一个是链表长度大于8，不一定转成红黑树，而是通过判断数组长度是否小于64进行扩容
扩容先生成新数组，再把老数组上面元素放到新数组位置上
扩容，如果是TreeNode情况
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
//低位
TreeNode<K,V> loHead = null, loTail = null;
//高位
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;//低位和高位数量
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
//如果低位不是null
if (loHead != null) {
//如果低位数量不超过6
if (lc <= UNTREEIFY_THRESHOLD)
//将TreeNode转成Node，转成了链表
tab[index] = loHead.untreeify(map);
else {
//如果超过，说明要用红黑树，
tab[index] = loHead;
//如果高位不是null，说明有高位，此时需要重新生成红黑树，如果没有高位，就不用走到treeify方法，用之前的就行。不需要重新再生成红黑树。
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
红黑树
-
根节点是黑色的；
-
每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
-
任何相邻的节点都不能同时为红色，红色节点是被黑色节点隔开的；
-
每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//如果是null，父节点，返回
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//如果父节点是黑色，不用调整，返回root
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//父节点是红色的情况，
//父节点正好是xpp的左节点
if (xp == (xppl = xpp.left)) {
//开始变色
if ((xppr = xpp.right) != null && xppr.red) {
//父节点和叔叔节点变黑，祖父节点变红，
xppr.red = false;
xp.red = false;
xpp.red = true;
//最上面节点颜色变化，再次递归，继续进行调整
x = xpp;
}
else {
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
HashMap为什么用红黑树
R-B Tree。它是一种不严格的平衡二叉查找树
引入RB-Tree是功能、性能、空间开销的折中结果。
红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。
就插入节点导致树失衡的情况，AVL和RB-Tree都是最多两次树旋转来实现复衡rebalance，旋转的量级是O(1)
删除节点导致失衡，AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡，旋转的量级为O(logN)，而RB-Tree最多只需要旋转3次实现复衡，只需O(1)，所以说RB-Tree删除节点的rebalance的效率更高，开销更小！
hashmap使用红黑树的原因是：这样可以利用链表对内存的使用率以及红黑树的高效检索，是一种很有效率的数据结构。AVL树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利就有弊，AVL树为了维持这种高度的平衡，就要付出更多代价。每次插入、删除都要做调整，复杂、耗时。对于有频繁的插入、删除操作的数据集合，使用AVL树的代价就有点高了。而且红黑树只是做到了近似平衡，并不严格的平衡，所以在维护的成本上，要比AVL树要低。所以，hashmap用红黑树。
红黑树相比avl树，在检索的时候效率其实差不多，都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡，他允许局部很少的不完全平衡，这样对于效率影响不大，但省去了很多没有必要的调平衡操作，avl树调平衡有时候代价较大，所以效率不如红黑树，在现在很多地方都是底层都是红黑树的天下啦。
java8不是用红黑树来管理hashmap，而是在hash值相同的情况下（且重复数量大于8），用红黑树来管理数据。 红黑树相当于排序数据，可以自动的使用二分法进行定位，性能较高。一般情况下，hash值做的比较好的话基本上用不到红黑树。
AVL树用于自平衡的计算牺牲了插入删除性能，但是因为最多只有一层的高度差，查询效率会高一些。红黑树的高度只比高度平衡的AVL树的高度（log2n）仅仅大了一倍，在性能上却好很多。
HashMap为什么要转成树？为什么阈值是8？
当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。
选择8，是根据概率统计决定。
HashMap源码里有一段注解，大概意思是：
理想情况下使用随机的哈希码，容器中节点分布在hash桶中的频率遵循泊松分布(具体可以查看http://en.wikipedia.org/wiki/Poisson_distribution)，按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表，可以看到链表中元素个数为8时的概率已经非常小，再多的就更少了，所以原作者在选择链表元素个数时选择了8，是根据概率统计而选择的。
这里看到8的时候概率小的可怜了。
空间和时间的权衡
TreeNodes占用空间是普通Nodes的两倍，所以只有当bin包含足够多的节点时才会转成TreeNodes，而是否足够多就是由TREEIFY_THRESHOLD的值决定的。当bin中节点数变少时，又会转成普通的bin。并且我们查看源码的时候发现，链表长度达到8就转成红黑树，当长度降到6就转成普通bin。
为什么不用B+Tree
B+树在数据库中被应用的原因是其“矮胖”的特点，B+树的非叶子结点不存储数据，所以每个结点能存储的关键字更多。所以B+树更能应对大量数据的情况。Mysql就是用的B+Tree。
jdk1.7中的HashMap本来是数组+链表的形式，链表由于其查找慢的特点，所以需要被查找效率更高的树结构来替换。如果用B+树的话，在数据量不是很多的情况下，数据都会“挤在”一个结点里面。这个时候遍历效率就退化成了链表。
结论：b+树不属于二叉树，因为二叉查找树的查找效率是最高的,如果内存能装下完整的树,最好使用二叉查找树，b+树是退而求其次的方式。
所以就是根据数据量去选择，HashMap数据量不大，，没有必要用B+Tree。
