Java数据结构（一）- HashMap的实现原理

Java中HashMap的基本结构是数组+链表，数组中的每个地址位置称作“桶”，新添加的元素通过rehash判断存放在哪个桶里，如果桶中已存在元素则形成链表，将新元素插入链表中，JDK1.8之前采用头插法，之后改为尾插法。在JDK1.8之后，当链表长度达到8时则会重构成红黑树。

Q: 可以将HashMap底层的数组换成链表吗？
A：不可以，如果将底层数组换成链表HashMap的查找效率将会从O(1)降低至O(n)。

Q: 为什么JDK1.8要引入红黑树？
A：HashMap的遍历复杂度是O（1），但这是建立在Hash函数分布式均匀的基础上的，如果链表长度过长会导致查询效率降低，甚至极端条件下会降为O（n），引入红黑树保证了哪怕是最极端条件下HashMap的查询效率也能是O（logn）。

Q：为什么将链表重构成红黑树的临界值是8？为什么不直接用红黑树？
A: 红黑树的查找效率提高，但是插入效率降低了，8是通过泊松分布找出的一个比较均衡的临界值。

Q：解决Hash碰撞的方法还有哪些？
A：Java中解决Hash碰撞的方法为链表法，除此之外还有开放寻址法，即通过某种特定算法找到下一个可用的地址。

HashMap的Hash构造需要一步rehash的操作，与HashTable不同，HashMap并非直接使用对象的HashCode，而是将HashCode和当前HashMap的容量（length - 1）按位做与操作得到新的hash值，新的hash值即对应该对象应当放入的桶。
HashMap的扩容：HashMap的初始容量为16，默认扩容系数为0.75，当HashMap的当前容量达到容量扩容系数（160.75 = 12）时会自动扩容，新的容量为旧容量的两倍（newCapacity = oldCapacity << 1，源码里因为是二进制所以是左移一位），由此可以看出HashMap的容量永远都是2的幂。

Q：为什么HashMap的容量必须是2的幂？
A：这是因为HashMap做rehash的时候我们要保证length-1的每一位都为1（例如10000 - 1 = 1111），否则若length-1的某一位为0，在做与操作的时候，由于0&0和0&1都为0，势必造成HashMap的某些桶一直为空，如此一来Hash函数分布就不均匀了，从而导致HashMap性能下降。

Q：如果手动将容量设置成不为2的幂的数呢？
A：那么HashMap会自动将容量向上转换为下一个2的幂。

Q：为什么默认的扩容系数是0.75？
A：大量的实验表面0.75是效率和空间利用率最为均衡的一个值。

注：HashMap在扩容之后还要再次对里面的元素进行rehash, 举个例子，原先一个HashCode是0X...10010的元素和在容量为16的时候和1111做与操作，此时只用比前四位，0010&1111 = 0010，所以它应该在下标为2的桶中，当HashMap的容量扩容到32后，该元素则要和11111做与操作，比原来多比一位， 10010&1111 = 10010，所以扩容后它应该在下标为18的桶中。通过上面一个例子我们不难发现，一个原先处于下标为n的桶中的元素在扩容后进行rehash时要比原来多比一位，如果这一位为1，那么扩容后它将处于下标为n + oldCapacity的桶中，若这一位为0，那扩容后它依然处于下标为n的桶中，且它在扩容后只可能处于这两个桶中。到这里我们可以发现，HashMap扩容的本质其实就是把每个长链表拆分成两个短链表。

HashMap的查询原理：HashMap重写了Object类的equals方法，在查询中会先通过hash值找到对应的地址，再通过equals方法比较对象。
HashMap的线程安全性：HashMap不是线程安全的数据结构，不适用与多线程。

Q：HashMap线程安全吗？不安全怎么办？
A：HashMap在设计之初就没有考虑线程安全的措施，在JDK1.7以前，HashMap在扩容时链表顺序会打乱，此时在多线程情况下有可能形成环，当再次查询到该桶中时就会进入死循环。JDK1.8之后通过将头插法改为尾插法，分别指向新链表和旧链表头尾节点的四个指针保证了扩容之后链表顺序不会乱，从而解决了这一问题，但是HashMap依旧不是一个线程安全的数据结构，若需要保证线程安全可以考虑使用HashTable，ConcurrentHashMap等线程安全的数据结构。