详解HashMap

底层实现

JDK1.8 之前

HashMap的底层数据结构是数组和链表。

key 的 hashcode 经过二次哈希处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

二次哈希用来优化哈希值的分布，通过对原始的 hashCode() 进行额外处理，二次哈希可以减小哈希碰撞，从而提高数据的分布均匀性。

JDK1.8之后

HashMap的底层数据结构是数组、链表和红黑树。

如果当前数组长度大于等于64，且链表长度大于阈值（默认为 8）时，将链表转化为红黑树；如果数组长度没到64，则会进行扩容。数组扩容能减少哈希冲突的发生概率（即将元素重新分散到新的、更大的数组中），这在多数情况下比直接转换为红黑树更高效。

而且，转化为红黑树目的是减少搜索时间，但是红黑树需要保持自平衡，维护成本较高，因此过早引入红黑树反而会增加复杂度，花费更多的时间。

数组的长度为什么一定是2的x次方

因为hash值的范围是-2147483648 ~ 2147483647，这个范围过大，因此需要让hash值对数组的长度取模运算得到的余数作为存放的位置（数组下标），但是取余(%)操作是复杂的。

如果取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作，换句话说，hash % n == hash & (n-1) 的充要条件是 n 是 2 的 x 次方。而与(&)操作是比取余操作简单很多的，所付出的代价很小，效率更高。因此，数组长度选用了2的x次方。

除此之外，长度是 2 的幂次方，可以让 HashMap 在扩容的时候更均匀。而且，扩容机制也变得简单和高效：扩容后只需检查哈希值高位的变化来决定元素的新位置，要么位置不变（高位为 0），要么就是移动到新位置（高位为 1，原索引位置+原容量）。

为什么HashMap线程不安全

HashMap线程不安全主要体现在因为在多线程的情况下，HashMap会发生死循环和数据丢失问题。

死循环

死循环问题发生在JDK1.8之前的HashMap，当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。

JDK1.8将头插法替换为了尾插法，从而避免了死循环问题。

数据丢失

两个线程 1,2 同时进行 put 操作，并且发生了哈希冲突（hash 函数计算出的插入下标是相同的）。不同的线程可能在不同的时间片获得 CPU 执行的机会，当前线程 1 执行完哈希冲突判断后，由于时间片耗尽挂起。线程 2 先完成了插入操作。随后，线程 1 获得时间片，由于之前已经进行过 hash 碰撞的判断，所有此时会直接进行插入，这就导致线程 2 插入的数据被线程 1 覆盖了。