专门做简历的网站软件/seo推广岗位职责

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。//第一次进来是nullif ((tab = table) == null || (n = tab.length) == 0)//这里调用resize，初始化及扩容，第一次返回16n = (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==nullif ((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 1sttreeifyBin(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 keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)更新valuee.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;//一开始时nullint 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 thresholdnewCap = 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=16table = newTab;//老数组上面元素转到新数组上面去if (oldTab != null) {//遍历老数组for (int j = 0; j < oldCap; ++j) {Node<K,V> e;//如果老数组这个元素不是nullif ((e = oldTab[j]) != null) {oldTab[j] = null;//如果为null，说明只有一个元素if (e.next == null)//重新计算放到新数组中newTab[e.hash & (newCap - 1)] = e;//判断是不是TreeNodeelse 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;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);//低位链表放到newTabif (loTail != null) {loTail.next = null;newTab[j] = loHead;}//高位链表放到newTabif (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，判断数组长度是否小于64if (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;elseloTail.next = e;loTail = e;++lc;}else {if ((e.prev = hiTail) == null)hiHead = e;elsehiTail.next = e;hiTail = e;++hc;}}
//如果低位不是nullif (loHead != null) {//如果低位数量不超过6if (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);}}}

红黑树

1. 根节点是黑色的；

2. 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；

3. 任何相邻的节点都不能同时为红色，红色节点是被黑色节点隔开的；

4. 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点

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;}//如果父节点是黑色，不用调整，返回rootelse 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。