java基础（二）HashMap相关问题，HashMap 1.7和HashMap 1.8的区别

1.时间复杂度

常见的时间复杂度排序：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n²)<Ο(n³)＜…＜Ο(2ⁿ)＜Ο(n!)

2.HashMap的时间复杂度

由于HashMap底层是通过 数组加链表 的方式实现的，要找到数组对应的下标，只需要进行一次取模运算，但是找到数组对应下标之后，如果entry链表太长的话，还是需要时间遍历比较。所以说entry链表越短越好，最好每个数组后面只跟一个链表，这样就能达到 O(1) 的时间复杂度，
如果最差的情况下，即所有元素的hashCode都一样，那就放在同一个bucket后面，这样时间复杂度就会达到 O(n)，但这种情况概率几乎没有。

3.为什么采用哈希码 与（&） （数组长度-1） 计算数组下标？

数组长度要求为2的幂原因：

（1） 数组长度 = 2的幂，（二进制）表示为100…00，首位为1，后面位数均为0；
       （数组长度-1）的结果 = （二进制）表示为0111.111，首位为0，后面位数均为1.
（2）提高运算效率。
         哈希码“与运算” 实绩长度 = hash值 对数组长度取模，但是取余效率较低，
         只有当数组长度为2的幂的时候，h&(length-1) 才等价于 h%length
（3）保证哈希码的均匀性。
        数组长度为2的幂 = 偶数（二进制最后一位为0），（length-1）为奇数（二进制最后一位为1），使得哈希码 & （数组长度-1）的结果最后一位可能是0或者1（取决于哈希码），即求与运算结果可能是奇/偶,保证了存储位置的均匀分布性。

4.HashMap为什么不安全？

（1）  多线程put的时候导致数据不一致。
        比如有两个线程A和B，A在向HashMap中put数据的时候，首先计算出数组的下标，然后获取该桶的链表表头节点，此时线程A的时间片用完了，而此时线程B得以调用，
线程B成功的插入了数据。假设线程A和线程B的hashCode值计算出来的桶索引是一样的，当线程B成功插入后，线程A再度调用执行，线程A持有过期的链表头而不知道，
导致线程A直接覆盖了之前线程B插入的数据，造成数据不一致的结果。

（2）当两个线程同时执行扩容的时候，容易线程不安全。
详情参考：http://www.importnew.com/22011.html

5.HashMap 1.7和HashMap 1.8的区别

5.1
1.8的存储结构为数组+链表+红黑树，1.7的为数组+链表。

引入红黑树原因：
提高HashMap性能，解决了由于哈希碰撞链表过长导致索引效率慢的问题。利用红黑树增删改查的特点，时间复杂度从O(n)降低为O(logn)

1.8中HashMap中的数组元素 & 链表节点 采用 Node类 实现,HashMap中的红黑树节点 采用 TreeNode 类 实现

5.2
添加红黑树之后，添加的核心参数。
（1）.桶的树化阈值
即链表转成红黑树的阈值，在存储数据时，当链表长度大于该值时，则将链表转换成红黑树。
（2）.桶的链表还原阈值
-即红黑树转换为链表的阈值。
-当在扩容之后，HashMap的存储位置会重新计算，此时如果原有的红黑树内数量 小于 阈值时，将红黑树转换为链表
（3）. 最小树形化容量阈值
-当哈希表中的容量 > 该值时，才允许树形化链表。
-否则，若桶内元素过多，则直接扩容，而不是树形化。
-为了避免扩容和树形化的冲突，这个值不能小于 4 * 桶的树形化阈值

5.3.插入数据方式不同：
JDK1.8采用尾插法，JDK1.7采用的是头插法。

5.4.扩容之后存储位置的计算方式：
（1）按照扩容后的规律计算：扩容后的位置=原位置 or 原位置+旧容量
（2）1.7全部按照原来的计算方式计算，hashCode（）->>扰动处理->>(h&(length-1))

图片转载自：
区别详解：https://blog.****.net/carson_ho/article/details/79373026
JDK1.8详解：https://blog.****.net/carson_ho/article/details/79373134