1.hashmap的底层数据结构
众所皆知map的底层结构是类似邻接表的结构，但是进入1.8之后，链表模式再一定情况下又会转换为红黑树
在JDK8中，当链表长度达到8，并且hash桶容量超过64(MIN_TREEIFY_CAPACITY)，会转化成红黑树，以提升它的查询、插入效率底层哈希桶的数据结构是数组，所以也会涉及到扩容的问题。
当MyHashMap的容量达到threshold域值时，就会触发扩容。扩容前后，哈希桶的长度一定会是2的次方。
1.1 为什么用红黑树
那么为什么用红黑树呢？之前都是用的链表，之前的文章有提到链表的随机访问效率是很低的，因为需要从head一个个往后面找，那么时间复杂度就是O(n),但是如果是红黑树因为红黑树是平衡二叉树，说白了就是可以索引的，那么时间复杂度只有O(logn),这样效率就可以得到很大的提高
也许有人就想问了，那为什么还搞个链表啊，直接用红黑树不就完了：
1.链表比红黑树简单，构造一个红黑树要比构造链表复杂多了，所以在链表不多的情况下，整体性能上来看，当链表不长的时候红黑树的性能不一定有链表高
2.还有一个节点的添加和删除的时候，需要对红黑树进行旋转，着色等操作，这个就比链表的操作复杂多了
3.所以为链表设置一个阈值用来界定什么时候进行树化，什么时候维持链表，从中间取得一个均衡是很重要的
1.2 为什么阈值是64，链表长度到8
刚刚讲到红黑树查找效率是O(logn)那么8的log是3，而使用链表，我们之前也有提到，源码会进行折半查找（参考之前linkedlist源码分析）那就是8/2 = 4 平均查找长度是4，所以在8的时候是比较合适的因为3比4小
再比如链表长度为6的时候，红黑树会退化为链表同理：6=》log=2~3 和8类似，但是6/2=3也很快，而且红黑树很复杂，所以是用的链表，至于其中的数字7的作用是缓冲一下，避免再长度为7，8徘徊的时候会频繁修改为红黑树和链表
还有为什么是64，参考网上记录是：再低于64的时候容量比较小，hash碰撞的几率比较大，这种时候出现长链表的可能性比较大，这种原因导致的长链表我们应该避免，而是采用扩容的策略避免不必要的树化
接下来我们观察一下hashmap的继承结构，了解一下
1.3 还有个问题负载因子的作用
0.75f负载因子过高会导致链表过长，查找键值对时间复杂度就会增高，负载因子过低会导致hash桶的个数过多，空间复杂度变高
注意构造函数：
hash桶没有再构造函数中进行初始化，而是再第一次存储键值的时候进行初始化，initialCapacity返回一个大于等于初始化容量大小的最小2的幂次方
2.hashmap的增长策略
2.1 插入数据
1.插入数据的时候首先会判断hash桶是否为空，如果为空会进行初始化，这是避免调用构造函数之后没有数据导致，而且再初始化的时候会调用扩容策略这个后面再讲
通过刚刚的学习我们知道hashmap有三种数据存放模式：数组，链表，红黑树
判断是否为空，如果为空，直接数组存放
这里有个细节
hash(key)和(n - 1) & hash 的使用
第一个对key进行hash取值
2.1.1 为什么要用hash(key)，当然hash肯定是必须的，不然object对象怎么定位数组索引但是hashcode不行么？
这里是因为hashcode是32位的数据，用hashcode和n相与的时候，如果n比较小，那么高位的数据基本就没用到(2的16次幂以上的数据)，那么就会导致hash碰撞的概率加大
这里hash（key）的操作是吧hashcode右移16位在和原来的hashcode进行异或操作，相当于是吧高位的信息合并到低位上，然后在和n做与运算，这样高位低位的信息全部都有，综合的话hash碰撞的概率相应减低
2.1.2 (n-1)&hash是什么操作hash%n不行么？
------------------------------------------------------------------------------------------------------------------------------------
说明一下，这两个操作都是取余操作，之前有人说是取模，这里科普一下，取模和取余是不一样的
取模（百度百科）：取模运算（“Module Operation”）和取余运算（“Complementation ”）两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机术语中。取余则更多是数学概念。模运算在数论和程序设计中都有着广泛的应用，从奇偶数的判别到素数的判别，从模幂运算到最大公约数的求法，从孙子问题到凯撒密码问题，无不充斥着模运算的身影。虽然很多数论教材上对模运算都有一定的介绍，但多数都是以纯理论为主，对于模运算在程序设计中的应用涉及不多。
7 mod 4 = 3（商 = 1 或 2，1<2，取商=1）
-7 mod 4 = 1（商 = -1 或 -2，-2<-1，取商=-2）
7 mod -4 = -1（商 = -1或-2，-2<-1，取商=-2）
-7 mod -4 = -3（商 = 1或2，1<2，取商=1）
R = a -c*b
比如-7 mod 4 => -7 = 1 -2 * 4
求模运算和求余运算在第一步不同: 取余运算在取c的值时，向0 方向舍入(fix()函数)；而取模运算在计算c的值时，向负无穷方向舍入(floor()函数)。
符号相同时，两者不会冲突。比如，7/3=2.3，产生了两个商2和37=3*2+1或7=3*3+（-2）。因此，7rem3=1，7mod3=1。符号不同时，两者会产生冲突。比如，7/（-3）=-2.3，产生了两个商-2和-37=（-3）*（-2）+1或7=（-3）*（-3）+（-2）。因此，7rem（-3）=1，7mod（-3）=（-2）
------------------------------------------------------------------------------------------------------------------------------------
好的，我们继续讨论(n-1)&hash和hash%n的问题
之前也有说到hashmap的扩容策略是大于等于初始化容量大小的最小2的幂次方，那么也就是说n是2的倍数，转换成2进制也就是最低位是0，再进行-1，那就是奇数
而且进行&操作
这里注意我们的n是2的多次幂，那么就是000100000000类似这样的二进制，减一的结果就是除了最高位其余一下都是1也就是：000011111111111
这个时候和原来的数据hash做&操作，就会把超出这个length范围的数据全部设置为0，也就是这个范围以内的数据不会变
Example：
8 =》 0000 0000 0000 1000
8 - 1 =》 0000 0000 0000 0111
然后不论什么数据与8-1做&操作，那么范围都在 0111之内，也就是7以内包含7范围再0~7，这样懂了吧，比如1000000&（7-1）结果就是0~7
当然出现这种情况有个必要的条件就是长度必须是2的n次幂，这样再二进制数列中，永远只有一个位置是1，其余位置是0，-1之后，这个位置一下的数据全包含再里面&就是截取低位的数据，吧高位去掉，相当于是取余了
因为不论什么数字都是x = a1*2^(n-1) + a2*2^(n-2) + … + a(n-1)*2^(1) + a(n)*2^(0),高位的肯定都是2的y次幂的倍数，所以去掉倍数，剩下的就是余数，不知道我这么说大家有没有理解。。。
大家还可以看看我之前的博客：https://www.cnblogs.com/cutter-point/p/11091727.html
如果不为空那么就要进行链表化或者树化了
2.1.3 如何链表化
说白了就是再hash桶的数组上获取这个位置上的node节点，然后循环遍历获取到最后一个节点，然后插入到节点末尾
//链表存放 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { //链表尾部插入，p的next判断是否为空 p.next = newNode(hash, key, value, null); //当链表的长度大于等于树化阀值，并且hash桶的长度大于等于MIN_TREEIFY_CAPACITY，链表转化为红黑树 // 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; }
2.1.4 构造红黑树树化
红黑树的变换规则可以参考我之前的博客：https://www.cnblogs.com/cutter-point/p/10976416.html
我们什么时候会进行树化呢？？？
就是当我们的链表长度超过或等于8个的时候
至于如何吧这个链表组建为红黑树，这个以后单独开章节细细探讨。。。。
2.2 扩容策略resize
//数组扩容 public Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; //如果旧hash桶不为空 if (oldCap > 0) { ////超过hash桶的最大长度，将阀值设为最大值 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //新的hash桶的长度2被扩容没有超过最大长度，将新容量阀值扩容为以前的2倍 //扩大一倍之后，小于最大值，并且大于最小值 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //左移1位，也就是扩大2倍 newThr = oldThr << 1; } else if (oldThr > 0) //如果旧的容量为空，判断阈值是否大于0，如果是那么就把容量设置为当前阈值 newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //如果阈值还是0,重新计算阈值 if (newThr == 0) { //当HashMap的数据大小>=容量*加载因子时，HashMap会将容量扩容 float ft = (float)newCap * loadFactor; //如果容量还没超MAXIMUM_CAPACITY的loadFactor时候，那么就返回ft，否则就是反馈int的最大值 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //hash桶的阈值 threshold = newThr; //初始化hash桶 @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; //如果旧的hash桶不为空，需要将旧的hash表里的键值对重新映射到新的hash桶中 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 //如果是多个节点的链表，将原链表拆分为两个链表，两个链表的索引位置，一个为原索引，一个为原索引加上旧Hash桶长度的偏移量 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // 在遍历原hash桶时的一个链表时，因为扩容后长度为原hash表的2倍，假设把扩容后的hash表分为两半，分为低位和高位， // 如果能把原链表的键值对， 一半放在低位，一半放在高位，这样的索引效率是最高的 //这里的方式是e.hash & oldCap， //经过rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。对应的就是下方的resize的注释 //为什么是移动2次幂呢？？注意我们计算位置的时候是hash&(length - 1) 那么如果length * 2 相当于左移了一位 //也就是截取的就高了一位，如果高了一位的那个二进制正好为1，那么结果也相当于加了2倍 //hash & (length * 2 - 1) = length & hash + (length - 1) & hash if ((e.hash & oldCap) == 0) { //如果这个为0，那么就放到lotail链表 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { //如果length & hash 不为0，说明扩容之后位置不一样了 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; //而这个loTail链表就放在原来的位置上 newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; //因为扩容了2倍，那么新位置就可以是原来的位置，右移一倍原始容量的大小 newTab[j + oldCap] = hiHead; } } } } } return newTab; }
总结就是扩容的时候吧数组大小扩大一倍，相当于左移1位，并且要重新计算hash散列值，找对应的位置填充
链表也要进行拆分，链表的拆分主要就体现在：
如果原来hash索引的位置就是这里，那么还是连接再原来的节点上，如果取余到对应的位置的节点，数组扩大一倍，我们原来的计算方式是hash&(n - 1)
那么如果我们大小扩大一倍结果就是：hash&(2n - 1)=hash&n + hash&(n-1)因为n是2的n次幂，除了对应的位置为1其余位置都为0
那么这里就可以转换为hash&(2n - 1)=hash&n + hash&(n-1) => n + hash&(n-1) => oldIndex + oldCap 也就是旧索引位置加上旧的容量大小
3.hashmap查找数据
查找对于红黑树部分我们略过：
至于其他部分，也就是跟之前大同小异了，还是hash取位置，然后取余获取对应的索引下标
首先检查是不是第一个，如果是那就直接返回了
如果不是循环遍历链表找到对应的key为止
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //注意这一步中(n - 1) & hash 的值 等同于 hash(k)%table.length if ((tab = table) != null && (n = tab.length) > 0 && //这里是计算相当于是取余的索引位置(n - 1) & hash 等价于hash % n //而且由于hashmap中的length再tableSizeFor的时候，就把长度设置为2的n次幂了，那么n-1之后的值，就是最高位全都是0，下面位数全是1 //这个也就是取hash的低位的值 (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; }
4.hashmap删除数据
4.1 树形退化
红黑树，我们就略过吧，这里篇幅有限不做探讨。。。。
5.关于hashmap的特殊操作
这里可以讲讲hashmap的特殊地方了
1.hashmap是允许null键和值的，而hashtable就不允许了
参考：
https://juejin.im/post/5a7719456fb9a0633e51ae14
https://blog.csdn.net/xingfei_work/article/details/79637878
https://juejin.im/post/5bed97616fb9a049b77fefbf
https://www.zhihu.com/question/30526656
https://juejin.im/post/5cb09c85e51d456e3428c0cf