我认为 HashMap 之所以没有一开始就使用红黑树，可能是因为时间和空间的折中考虑吧。在 Hash（）冲突比较小的时候，即使转化为红黑树之后，在时间复杂度上产生的效果也不是特别大。
而且在 put 的时候效率可能会降低，毕竟每次 put 都要进行非常复杂的红黑树这种旋转算法、旋转操作。另外在空间上的话每个节点都要维护更多的一个指针，这就显得有点得不偿失了。
最后就是，HashMap 之所以选择红黑树而不是二叉搜索树，我认为最主要的原因是，二叉树在一些极端情况下，它会变成一个倾斜的结构，查找效率就会退化成跟链表差不多的效率。而红黑树它是一种平衡树，可以防止这种极端情况，保持平衡，防止退化成链表。然后红黑树又不像其他的平衡二叉树那样有严格的平衡条件，所以红黑树插入效率要比完全的平衡二叉树要高。
所以 HashMap 选择红黑树，既可以避免极端情况下的退化，又可以兼顾查询和插入的这种效率。
