前言
A Red-Black tree based {@link NavigableMap} implementation. The map is sorted according to the {@linkplain Comparable natural ordering} of its keys, or by a {@link Comparator} provided at map creation time, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the {@code containsKey}, {@code get}, {@code put} and {@code remove} operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest’s Introduction to Algorithms.
上面是一段关于TreeMap的官方Javadoc描述，简单来说就是，TreeMap底层是基于红黑树，保持了key的大小有序性，因此查找等操作的时间复杂度为O(logn)；
在这篇文章中我主要分析Java中是如何利用红黑树实现TreeMap的，关于红黑树的详细原理介绍可以参考这篇文章《教你透彻了解红黑树》。