HashMap为什么使用红黑叔而不是其他数据结构
|
为什么要使用红黑树以及什么时候使用红黑树？
向 HashMap 中添加数据时不可避免的会产生 Hash 冲突，而 HashMap 使用拉链法来解决 Hash 冲突，这就导致在 Hash 冲突较多的时候，会严重影响 HashMap 的查询效率（链表查询时间复杂度为O(n))，因此引入了红黑树（查询时间复杂度O(log n))这一数据结构来优化。
那么什么时候会使用红黑树呢？
在链表长度达到 8 并且 HashMap 存储的数据量大于 64 时，会将链表转化为红黑树。
为什么不一开始就直接用红黑树呢？
红黑树是二叉平衡树的一种，在插入和删除数据时红黑树需要通过旋转来保持“平衡”，这一过程是要付出代价的。而且红黑树节点的大小为链表节点的 2 倍，在节点太少时红黑树查找性能优势并不明显。
为什么不适用其他数据结构？
如上所述，引入红黑树的目的是为了优化查询效率，但是能够优化查询效率的数据结构又不止红黑树一种，为什么不适用其他的数据结构呢？
例如二叉树、平衡二叉树、B树、B+树这些数据结构查询效率也很高，为什么不适用他们呢？
二叉树
二叉树存在数据倾斜问题，极端情况下会退化成链表（只有左节点或只有右节点），不够稳定。
平衡二叉树
平衡二叉树和红黑树查询时间复杂度都是O（log n)。但是平衡二叉树有更加严格的”平衡“标准，在插入或者删除数据时，平衡二叉树需要更多的旋转才能达到平衡。
B树、B+树
B树和B+树的节点都能存储多个数据，在数据量不是很多的情况下，数据会”挤在“一个节点里面。这个时候遍历效率就退化成了链表。
