3、Jdk1.7以前，当HashMap中某个桶的结构为链表时，遍历的时间复杂度为O(n)，1.8之后，桶中过多元素的话会转换成了红黑树，这时候的遍历时间复杂度就是O(logn)。
心得最后，说下心得，老实说，在写这篇文章之前，我对HashMap只是的了解仅仅停留在用过的层面，没有对源码做深入的了解，直到心血来潮想学习下Java的集合类才去看HashMap的源码，看完源码后，我被深深的震撼了，说实话，我没想过平时最常见的工具类的源码是这么复杂，一个HashMap就涉及到了如此众多的技术知识，比如红黑树，链表转换，hash运算等，通过简单的代码就整合了这些知识点，而且还保证了HashMap的高效性能。说实话，我对设计者是非常佩服的，估计此生我都写不出如此牛逼的代码。我也终于能理解为什么那么多公司面试时很喜欢问集合类的底层实现了，因为集合中涉及的技术知识是非常高深的，若能吃透集合类的源码，那人能不NB吗？
最后，感谢这几位大神的技术文章
https://blog.csdn.net/u011240877/article/details/53351188
https://blog.csdn.net/u011240877/article/details/53351188