新老鸟:从源码分析一下TreeSet(基于jdk1.8)

来源: 百家号 日期: 2月前 人气: - 评论: 0

  这个TreeSet其实和HashSet类似。HashSet底层是通过HashMap实现的,TreeSet其实底层也是通过TreeMap实现的。这篇文章就通过源码来分析一下TreeSet.

  

  一、简介

  

  TreeSet的作用是保存无重复的数据,不过还对这些数据进行了排序。TreeMap的底层是通过红黑树实现的,所以TreeSet底层也是通过红黑树实现的。TreeSet最主要的特点就是对元素进行了排序。我们对其特点进行总结一下:

  

  (1)TreeSet是基于TreeMap的NavigableSet实现。

  

  (2)TreeSet的元素存储在TreeMap中的key中,TreeMap的value是一个常量对象。

  

  (3)非线程安全 。

  

  (4)java8新增分割器spliterator() 方法。

  

  在源码分析中我们也是基于jdk1.8来分析。下面我们就直接来看一下;

  

  二、源码分析

  

  1、继承关系


源码-继承关系

  

  2、参数变量


源码-参数变量

  

  第一个疑问:不是说TreeSet是基于TreeMap实现的,为什么这里的参数是NavigableMap?

  

  这是因为TreeMap实现了NavigableMap接口。

  

  第二个疑问,既然TreeSet只使用了NavigableMap的key,那么直接使用null作为NavigableMap的value不就完了,还方面节省内存。

  

  这个疑问就要好好说一下了,如果看过我HashSet那篇文章想必你一定很清楚了。这里可以直接跳过,如果你没看过,我们直接定位到TreeSet的增删方法。深入源码中找寻答案。


直接定位到TreeSet

  

  在add方法中,我们会出现两种put情况

  

  情况1:元素e不重复,直接插入即可。

  

  情况2:元素e重复,m.put(e, PRESENT)一看e这个key已经存在了,就会将PRESENT替换掉相应的value值。然后map返回这个value.value不等于null,于是返回false.很明显插入失败了。

  

  但是如果我们把PRESENT替换成null呢?这时候m.put(e, PRESENT)一看e这个key已经存在了,于是map返回null.完了这时候你会发现null等于null.整个add方法返回的就是true.这不就矛盾了嘛。命名插入的是重复数据,返回的结果依然还是true.所以这里使用了PRESENT这个对象就能有效地避免这种情况。

  

  3、构造方法


构造方法

  

  这五个构造方法,基本上把HashSet的几个特性全部说完了,底层就是new一个TreeMap来实现的,我们还可以假如自己的比较器和排序器。

  

  4、其他方法

  

  增删方法我们已经看了其实就是通过map的put的remove方法来实现的。我们来看一些其他的常见方法:

  

  (1)返回子Set


返回子Set

  

  (2)返回Set的头部和尾部


返回Set的头部和尾部

  

  (3)返回set中大于小于等于e的元素


返回Set中大于小于e的元素

  

  (4)获取首尾元素并移除


获取首尾元素并移除

  

  (5)读写数据


读写数据

  

  还有一个读数据


d01373f082025aaf41a070a8b4e42a61024f1ad5.jpeg

  

  源码很简单基本上都在这。下面我们总结一下。

  

  对于HashSet是用Hash表来存储数据,而TreeSet是用二叉树来存储数据。 在不需要排序的时候,还是建议优先使用HashSet,因为速度更快,二叉树需要排序就免不了跳转旋转,所以速度会很慢。