HashMap底层是如何实现的？

1、典型回答

不同的JDK 版本，HashMap 的底层实现是不一样的，总体来说：在JDK 1.8 之前(不包含JDK 1.8)，HashMap 使用的是数组 + 链表实现的，而JDK 1.8之后(包含JDK 1.8)使用的是数组 + 链表或红黑树实现的

HashMap 在JDK 1.8 以前 (不包含JDK 1.8) 的版本中的实现如下图所示：

 HashMap 在JDK 1.8+ 中 (包含JDK 1.8)的实现如下图所示：

2、全面剖析

HashMap 在JDK 1.8 之前 (不包含JDK 1.8) ，使用的是数组 + 链表实现的；而JDK 1.8 之后(包含 JDK 1.8)，使用的是数组 + 链表或红黑树实现的。 

3、知识扩展

为什么在JDK1.8中要引入红黑树？

主要原因是为了提高查询效率，大家知道链表在很长的时候查询效率是比较低的，因为链表在查询一个元素时，需要从头开始一个一个的进行查询，所以它的查询时间复杂度时 O(n)，那么当链表过长时，查询效率就会比较低。

而红黑树是一种平衡二又搜索树，而平衡二叉搜索树，也就是红黑树中的每一个节点，其左子树中的所有节点的值均小于右子树的值，这个特点使得在红黑树上进行查找操作时，可以利用节点的值进行二分查找，从而它的查询的时间复杂度为 O(log n)。

所以，当数据量比较大时，使用红黑树的性能要远远大于链表，因此在 JDK 1.8 中就引入了红黑树，在数据量比较大时就采用红黑树替代链表进行数据存储。

为什么HashMap要使用红黑树？-CSDN博客