java TreeMap源码解析详解

java TreeMap源码解析详解

 在介绍TreeMap之前，我们来了解一种数据结构：排序二叉树。相信学过数据结构的同学知道，这种结构的数据存储形式在查找的时候效率非常高。

如图所示，这种数据结构是以二叉树为基础的，所有的左孩子的value值都是小于根结点的value值的，所有右孩子的value值都是大于根结点的。这样做的好处在于：如果需要按照键值查找数据元素，只要比较当前结点的value值即可（小于当前结点value值的，往左走，否则往右走），这种方式，每次可以减少一半的操作，所以效率比较高。在实现我们的TreeMap中，使用的是红黑树（一种优化了的二叉排序树）。

     一、TreeMap的超接口 

     TreeMap主要继承了类AbstractMap（一个对Map接口的实现类）和 NavigableMap（主要提供了对TreeMap的一些高级操作例如：返回第一个键或者返回小于某个键的视图等）。主要的一些操作有：put添加元素到集合中，remove根据键值或者value删除指定元素，get根据指定键值获取某个元素，containsValue查看是否包含某个指定的值，containsKey 查看是否包含某个指定的key数值等。

     二、构造函数 

           TreeMap 的构造函数主要有以下几种：

 private final Comparator<? super K> comparator;  public TreeMap() {comparator = null;}  public TreeMap(Comparator<? super K> comparator) {    this.comparator = comparator;  }