Java中TreeMap和TreeSet的底层实现

TreeSet底层则采用NavigableMap这个接口来保存TreeSet集合,而实际上NavigableMap只是一个接口,实际上TreeSet还是用TreeMap来保存set元素。

TreeSet初始化的时候会new 一个TreeMap进行初始化;

private transient NavigableMap<E,Object> m;

TreeSet(NavigableMap<E,Object> m) { this.m = m; }

public TreeSet() { this(new TreeMap<E,Object>());

}

TreeMap采用一种被称为“红黑树”的排序二叉树来保存Map中的每个Entry——每个Entry都被当做红黑树的一个节点来对待;

TreeMap的插入就是一个“排序二叉树”算法:每当程序添加新节点时,总是从树的根节点开始比较,即将根节点当成当前节点,如果新增节点大于当前节点且当前节点的右节点存在,则以右节点作为当前节点;如果新增节点小于当前节点且当前节点的左节点存在,则以左节点作为当前节点;如果新增节点等于当前节点,则新增节点覆盖当前节点;直到某个节点的左右节点不存在,并结束循环;将新增的节点作为该节点的子节点,如果新增的节点大于该节点,则添加成该节点的右节点,如果新增的节点小于该节点,则添加成该节点的左节点;

TreeMap 根据Key来获取value。

相同点:

(1)都是有序集合,也就是说他们存储的值(key)都是排好序的。

(2)都是非同步的,因此它们不能在多线程之间共享,不过可以使用方法Collections.synchroinzedMap()或者Collections.synchroinzedSet()来实现同步。

(3)运行速度都要比Hash集合慢,它们内部对元素的操作时间复杂度为O(logN),而HashMap和HashSet则为O(1)。

不同点:

(1)TreeSet和TreeMap实现的接口规范不同,分别实现Set和Map接口。

注意:

TreeSet和TreeMap要求存放的对象(对TreeMap来说是键值对映射的键)所属的类必须实现Comparable接口(或者通过Comparator实例化TreeSet和TreeMap对象),该接口提供了比较元素的compareTo()方法,当插入元素时会调用该方法比较元素的大小。

补充:

Collections工具类的sort方法有两种重载的形式:sort(List list) 与sort(List list, Comparator<? super T> c)

第一种要求传入的待排序容器中存放的对象所属的类必须实现Comparable接口以实现元素的比较。 第二种不强制要求待排序容器中存放的对象所属的类必须实现Comparable接口,但是要求传入第二个参数,这个参数是Comparator接口的子类型(需要重写compare方法实现元素的比较),相当于一个临时定义的排序规则,其实就是通过接口注入比较元素大小的算法,也是对回调模式的应用(Java中对函数式编程的支持)。

经验分享 程序员 微信小程序 职场和发展