Java数据结构--13.Java8数据结构TreeSet.pdf
版权申诉
106 浏览量
2022-07-11
08:04:42
上传
评论
收藏 235KB PDF 举报
Java数据结构--13.Java8数据结构TreeSet
前⾔
，上⼀篇中对 Set 接⼝最终实现类 HashSet 与 LinkedHashSet 做了介绍与分析，本篇将对另⼀种 Set 接⼝的最终实现类 TreeSet 进⾏
介绍与分析。
先来看下 TreeSet 完整的继承结构图
可以看到 TreeSet 与 HastSet 不同，不仅继承⾃ AbstarctSet 类，还实现了 SortSet 与它的⼦类 NavigableSet 接⼝，所以在查看
TreeSet 的源码之前，必须先来看⼀下 SortedSet 与 NavigableSet 接⼝。
/**
*
⼀个进⼀步提供它的所有元素整个顺序的
Set
。
*
元素由它们的⾃然
Comparable
排序，或者通过⼀个由顺序
set
创建时特别提供的
* Comparator
。这个
set
的迭代器将会以递增元素顺序横穿
set
。提供多个额外的操作来⽀持排
*
序。（这个接⼝与
SortedMap
的
set
类似。）
*
*
所有加⼊⼀个有序的
set
的元素必须实现
Comparable
接⼝（或者接收⼀个特定的
* comparator
）。进⼀步说，这样的元素必须是彼此可以⽐较的：
e1.compareTo(e2)
（或者
* comparator.compare(e1, e2)
）
必须对于顺序
set
中的任何元素
e1
和
e2
不抛出⼀个
* ClassCastException
。
试图违反这个规约将导致侵犯⽅法或者调⽤构造器来抛出⼀个
* ClassCastException
。
*
*
注意，如果有序
set
要正确实现
Set
接⼝的话，由⼀个有序
set
（不管是不是明确提供了
* comparator
）
维护的顺序必须与
equals
⽅法等价。（查看
Comparable
接⼝或者
* Comparator
了解来了解与
equals
等价的明确定义。）必须这样的原因是
Set
接⼝是根据
* equals
操作定义的，但是⼀个有序
set
通过使⽤元素的
compareTo
或者
compare
⽅法⽐
*
对所有元素来完成它的表现，所以通过这个⽅法被认为相同的两个元素从有序
set
的⽴场，是
* equal
。这种有序
set
的⾏为是被完好定义的，即是它的顺序是与
equals
等价的；它只是
*
没有遵守
Set
接⼝的通⽤约定。
*
*
所有通⽤⽬的的有序
set
实现类应该提供
4
个
“
标准
”
的构造器：
1
）⼀个空的（没有参数）构造
*
的，构建⼀个空的对它的元素⾃然排序的有序
set
。
2
）⼀个接收⼀个
Comparator
类参数的构
*
造器，构建⼀个空的根指定
comparator
排序的有序
set
。
3
）⼀个接收⼀个
Collection
类
*
参数的构造器，构建⼀个包含参数重同样元素的新的有序
set
，根据元素的⾃然顺序排序。
4
）⼀
*
个接收⼀个
SortedSet
类型参数的构造器，构建⼀个新的包含了与输⼊有序
set
相同元素与顺
*
序的有序
set
。没有⽅法能强制执⾏这种推荐⽅法，因为接⼝不能包含构造器。
*
*
注意：多个⽅法返回有限范围的对象。⽐如范围是
half-open
，它的意思是，它们包含它们的低
*
端点⽽不是他们的⾼端点（适当的。）如果你需要⼀个
closed range
（包含两个端点），并且元
*
素类型允许是⼀个给定值的中继器计算后的结果，只要请求从低端点到中继器（⾼端点）的⼦范
*
围。例如，假设
s
是⼀个
strings
的有序
set
。下列惯⽤语义包含⼀个包含了所有
s
中从
* low
到
high
的视图，包括：
<pre>
* SortedSet<String> sub = s.subSet(low, high+" ");</pre>
*
*
⼀个类似的技术可以⽤来⽣成⼀个开放区间（两个端点都不包含）。下列惯⽤语义包含了⼀个所有
* s
中从
low
到
high
的视图，包括：
<pre>
* SortedSet<String> sub = s.subSet(low+" ", high);</pre>
*
* SortedSet
接⼝，继承⾃
Set
接⼝
资源评论
