Java TreeMap源码分析

前言

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的,关于红黑树的详细原理介绍可以参考这篇文章《教你透彻了解红黑树》。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×