HashMap

JDK7和JDK8中的HashMap有什么区别？

• JDK7中的HashMap，是基于数组+链表来实现的，它的底层维护一个Entry数组。它会根据计算的hashCode将对应的key-value键值对存储到该数组中，如果发生hashCode冲突，会将该key-value键值采用头插法插入已有元素的前面， 形成了一个链式的存储结构。

• 采用头插***导致的问题 -> 并发情况下的扩容死链：扩容的过程 resize 方法又调用了一个 transfer 的方法，把里面的一些 Entry 进行了一个 rehash， 在这个过程中可能会造成链表的一个循环，会在下一个 get 的时候出现一个死循环的情况

• JDK7中HashMap的实现方案有一个明显的缺点，即当Hash冲突严重时，在桶上形成的链表会变得越来越长，这样在查询时的效率就会越来越低，其时间复杂度为O(N)。

• JDK8中的HashMap，是基于数组+链表+红黑树来实现的，它的底层维护一个Node数组。当链表的存储的数据个数大于等于8且数组的长度大于等于64时，不再采用链表存储，而采用了红黑树存储结构。这么做主要是在查询的时间复杂度上进行优化，链表为O(N)，而红黑树一直是O(logN)，可以大大的提高查找性能。

• 1.7 是大于等于阈值且没有空位时才扩容，而 1.8 是大于阈值就扩容

• 1.8 在扩容计算 Node 索引时，会优化

介绍一下HashMap底层的实现原理

• 它基于 hash 算法，通过 put 方法和 get 方法存储和获取对象。
• 存储对象时，我们将 key-value 传给 put 方法时，它调用 key 的 hashCode 计算 hash 从而得到桶位置，进一步存储，HashMap 会根据当前桶的占用情况自动调整容量。获取对象时，我们将 key 传给 get 方法，它调用 hashCode 计算 hash 从而得到桶位置，并进一步调用equals()方法确定键值对。

介绍一下HashMap的扩容机制

• 在初始化 HashMap 的时候，如果没有指定容量，默认初始容量是 16 ， 负载因子是 0.75 ，根据容量和负载因子计算出扩容的阈值，在 put 的时候判断当前的 size 是否大于阈值，大于阈值的话会扩容成原来的两倍大小

为什么容量选择 2 的次方

• 在进行下标计算时可以用 & （size - 1） 代替 % size ，提升一定的计算性能
• 扩容后重新计算桶下标时 二次 hash 值 & 原始容量为 0 的留在原位，不为 0 的移到新的位置，新位置为 原始位置 + 原始容量

树化意义

• 红黑树用来避免 DoS 攻击，防止链表超长时性能下降，树化应当是偶然情况，是保底策略
• hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过 8 的链表出现概率是 0.00000006，树化阈值选择 8 就是为了让树化几率足够小

索引计算

• 首先，计算对象的 hashCode()再进行调用 HashMap 的 hash() 方法进行二次哈希二次 hash() 是为了综合高位数据，让哈希分布更为均匀，最后 & (capacity – 1) 得到索引

扩容（加载）因子为何默认是 0.75f

• 在空间占用与查询时间之间取得较好的权衡，大于这个值，空间节省了，但链表就会比较长影响性能，小于这个值，冲突减少了，但扩容就会更频繁，空间占用也更多

多线程下的问题

• 没有加锁，在多线程的情况下不能保证他的数据是安全的，就是 put 进去的值不再是原来的那个值

key 的设计要求

• HashMap 的 key 可以为 null，但 Map 的其他实现则不然
• 作为 key 的对象，必须实现 hashCode 和 equals，并且 key 的内容不能修改（不可变）
• key 的 hashCode 应该有良好的散列性