HashMap存储结构
HashMap存储结构
这里需要区分一下，JDK1.7和 JDK1.8之后的 HashMap 存储结构。在JDK1.7及之前，是用数组加链表的方式存储的。
但是，众所周知，当链表的长度特别长的时候，查询效率将直线下降，查询的时间复杂度为 O(n)。因此，JDK1.8 把它设计为达到一个特定的阈值之后，就将链表转化为红黑树。
这里简单说下红黑树的特点：
- 每个节点只有两种颜色：红色或者黑色
- 根节点必须是黑色
- 每个叶子节点（NIL）都是黑色的空节点
- 从根节点到叶子节点，不能出现两个连续的红色节点
- 从任一节点出发，到它下边的子节点的路径包含的黑色节点数目都相同
由于红黑树，是一个自平衡的二叉搜索树，因此可以使查询的时间复杂度降为O(logn)。（红黑树不是本文重点，不了解的童鞋可自行查阅相关资料哈）
为什么要引入红黑树？
JDK 1.8以前是数组+链表，还未引入红黑树，这就导致了链表过长时查找的时间复杂度是O(n), 完全失去了设计HashMap时的设计初衷，针对这种情况JDK 1.8引入了红黑树（查找的时间复杂度为O(logN),什么是红黑树呢，红黑树是一种自平衡的二叉查找树，不是一种绝对平衡的二叉树，它放弃了追求绝对平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。从而获得更高的查找性能。
HashMap 结构示意图：