JDK1.8 中的 HashMap 数据结构使用了数组 + 链表 + 红黑树, 数组和链表结构和 JDK1.7 中的基本一致, 红黑树是一个新增的方式, 具体实现类是内部类 TreeMap.
这是为了为了解决 hash 碰撞严重导致链表过长后查询占据较低的缺陷引进的.
想深入了解红黑树, 需要对树, 二叉树 23 树, 234 树有一定的认识, HashMap 信你得红黑树是 234 树的一种具体实现, 红黑树就是一个能维持相对平衡的二叉树, 使用红黑两种颜色来划分节点, 红黑树存在如下约束条件:
根节点必须为黑色
其余节点要嘛是红色要嘛是黑色
最底层的叶子结点为 null, 是黑色
父子节点不能同时为黑色
从任何一个叶子结点到根节点路径上的黑节点数量一致
来源: http://www.jianshu.com/p/1cb6eb0f8572