HashMap实现原理：容量、负载因子、hash与定位都搞定了吗？( 六 )_HashMap是常考点

将旧entry的引用赋值给新entry的next属性，改将新entry放在该位置——即在该位置上存储一个链表，冲突节点从链表头部插入，这样插入新entry时不需要遍历链表，时间复杂度为O(1) 。但如果链表过长，查询性能仍将退化到O(n) 。 Java8中对链表长度增加了一个阈值，超过阈值链表将转化为红黑树，查询时间复杂度降为O(logn) ，提高了链表过长时的性能。

勘误：网上有朋友联系我指出了此处的错误， Java8中，发生碰撞时会遍历到链表的最后。

这篇文章写的时候读源码能力比较渣，就基于自己早期对Java7源码的分析改编，本以为除了红黑树部分，大体相同，就直接copy了过来，导致了这个错误——当然，现在想来，关于Java7中HashMap的分析也是错的，最后插入方式没错，但是插入前还是要O(n)的时间遍历一遍。不过其他涉及源码的文章就都是老老实实追源码写出来的，可以放心阅读。告诫自己，要坚持踏实，坚持怀疑。以下是改正的分析。

从该位置上的entry开始，遍历到找到相同的key（就替换），或到结尾还是没有相同的key（就衔接在尾节点的next上）。查询时过程相同。不考虑任何优化，插入、查询的性能都是O(n) 。 Java8中对链表长度增加了一个阈值，超过阈值链表将转化为红黑树，插入、查询的时间复杂度降为O(logn) ，提高了链表过长时的性能。调用get方法时，定位到该位置，再遍历红黑树，比较key值找到所需元素：