国外优秀营销网站设计,有趣网站建设无聊,雄安个人代做网站排名,新手学做网站需要注意的几点第1部分 TreeSet介绍TreeSet简介TreeSet 是一个有序的集合#xff0c;它的作用是提供有序的Set集合。它继承于AbstractSet抽象类#xff0c;实现了NavigableSet, Cloneable, java.io.Serializable接口。TreeSet 继承于AbstractSet#xff0c;所以它是一个Set集合#xff0c…第1部分 TreeSet介绍TreeSet简介TreeSet 是一个有序的集合它的作用是提供有序的Set集合。它继承于AbstractSet抽象类实现了NavigableSet, Cloneable, java.io.Serializable接口。TreeSet 继承于AbstractSet所以它是一个Set集合具有Set的属性和方法。TreeSet 实现了NavigableSet接口意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。TreeSet 实现了Cloneable接口意味着它能被克隆。TreeSet 实现了java.io.Serializable接口意味着它支持序列化。TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。TreeSet为基本操作(add、remove 和 contains)提供受保证的 log(n) 时间开销。另外TreeSet是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。TreeSet的构造函数// 默认构造函数。使用该构造函数TreeSet中的元素按照自然排序进行排列。TreeSet()// 创建的TreeSet包含collectionTreeSet(Collection extends E collection)// 指定TreeSet的比较器TreeSet(Comparator super E comparator)// 创建的TreeSet包含setTreeSet(SortedSet set)TreeSet的APIboolean add(E object)boolean addAll(Collection extends E collection)void clear()Object clone()boolean contains(Object object)E first()boolean isEmpty()E last()E pollFirst()E pollLast()E lower(E e)E floor(E e)E ceiling(E e)E higher(E e)boolean remove(Object object)int size()Comparator super E comparator()Iterator iterator()Iterator descendingIterator()SortedSet headSet(E end)NavigableSet descendingSet()NavigableSet headSet(E end, boolean endInclusive)SortedSet subSet(E start, E end)NavigableSet subSet(E start, boolean startInclusive, E end, boolean endInclusive)NavigableSet tailSet(E start, boolean startInclusive)SortedSet tailSet(E start)说明(01) TreeSet是有序的Set集合因此支持add、remove、get等方法。(02) 和NavigableSet一样TreeSet的导航方法大致可以区分为两类一类时提供元素项的导航方法返回某个元素另一类时提供集合的导航方法返回某个集合。lower、floor、ceiling 和 higher 分别返回小于、小于等于、大于等于、大于给定元素的元素如果不存在这样的元素则返回 null。第2部分 TreeSet数据结构TreeSet的继承关系java.lang.Object↳ java.util.AbstractCollection↳ java.util.AbstractSet↳ java.util.TreeSetpublic class TreeSet extends AbstractSetimplements NavigableSet, Cloneable, java.io.Serializable{}TreeSet与Collection关系如下图从图中可以看出(01) TreeSet继承于AbstractSet并且实现了NavigableSet接口。(02) TreeSet的本质是一个有序的并且没有重复元素的集合它是通过TreeMap实现的。TreeSet中含有一个NavigableMap类型的成员变量m而m实际上是TreeMap的实例。第3部分 TreeSet源码解析(基于JDK1.6.0_45)为了更了解TreeSet的原理下面对TreeSet源码代码作出分析。1 package java.util;23 public class TreeSet extends AbstractSet4 implements NavigableSet, Cloneable, java.io.Serializable5 {6 // NavigableMap对象7 private transient NavigableMap m;89 // TreeSet是通过TreeMap实现的10 // PRESENT是键-值对中的值。11 private static final Object PRESENT new Object();1213 // 不带参数的构造函数。创建一个空的TreeMap14 public TreeSet() {15 this(new TreeMap());16 }1718 // 将TreeMap赋值给 NavigableMap对象m19 TreeSet(NavigableMap m) {20 this.m m;21 }2223 // 带比较器的构造函数。24 public TreeSet(Comparator super E comparator) {25 this(new TreeMap(comparator));26 }2728 // 创建TreeSet并将集合c中的全部元素都添加到TreeSet中29 public TreeSet(Collection extends E c) {30 this();31 // 将集合c中的元素全部添加到TreeSet中32 addAll(c);33 }3435 // 创建TreeSet并将s中的全部元素都添加到TreeSet中36 public TreeSet(SortedSet s) {37 this(s.comparator());38 addAll(s);39 }4041 // 返回TreeSet的顺序排列的迭代器。42 // 因为TreeSet时TreeMap实现的所以这里实际上时返回TreeMap的“键集”对应的迭代器43 public Iterator iterator() {44 return m.navigableKeySet().iterator();45 }4647 // 返回TreeSet的逆序排列的迭代器。48 // 因为TreeSet时TreeMap实现的所以这里实际上时返回TreeMap的“键集”对应的迭代器49 public Iterator descendingIterator() {50 return m.descendingKeySet().iterator();51 }5253 // 返回TreeSet的大小54 public int size() {55 return m.size();56 }5758 // 返回TreeSet是否为空59 public boolean isEmpty() {60 return m.isEmpty();61 }6263 // 返回TreeSet是否包含对象(o)64 public boolean contains(Object o) {65 return m.containsKey(o);66 }6768 // 添加e到TreeSet中69 public boolean add(E e) {70 return m.put(e, PRESENT)null;71 }7273 // 删除TreeSet中的对象o74 public boolean remove(Object o) {75 return m.remove(o)PRESENT;76 }7778 // 清空TreeSet79 public void clear() {80 m.clear();81 }8283 // 将集合c中的全部元素添加到TreeSet中84 public boolean addAll(Collection extends E c) {85 // Use linear-time version if applicable86 if (m.size()0 c.size() 0 87 c instanceof SortedSet 88 m instanceof TreeMap) {89 SortedSet extends E set (SortedSet extends E) c;90 TreeMap map (TreeMap) m;91 Comparator super E cc (Comparator super E) set.comparator();92 Comparator super E mc map.comparator();93 if (ccmc || (cc ! null cc.equals(mc))) {94 map.addAllForTreeSet(set, PRESENT);95 return true;96 }97 }98 return super.addAll(c);99 }100101 // 返回子Set实际上是通过TreeMap的subMap()实现的。102 public NavigableSet subSet(E fromElement, boolean fromInclusive,103 E toElement, boolean toInclusive) {104 return new TreeSet(m.subMap(fromElement, fromInclusive,105 toElement, toInclusive));106 }107108 // 返回Set的头部范围是从头部到toElement。109 // inclusive是是否包含toElement的标志110 public NavigableSet headSet(E toElement, boolean inclusive) {111 return new TreeSet(m.headMap(toElement, inclusive));112 }113114 // 返回Set的尾部范围是从fromElement到结尾。115 // inclusive是是否包含fromElement的标志116 public NavigableSet tailSet(E fromElement, boolean inclusive) {117 return new TreeSet(m.tailMap(fromElement, inclusive));118 }119120 // 返回子Set。范围是从fromElement(包括)到toElement(不包括)。121 public SortedSet subSet(E fromElement, E toElement) {122 return subSet(fromElement, true, toElement, false);123 }124125 // 返回Set的头部范围是从头部到toElement(不包括)。126 public SortedSet headSet(E toElement) {127 return headSet(toElement, false);128 }129130 // 返回Set的尾部范围是从fromElement到结尾(不包括)。131 public SortedSet tailSet(E fromElement) {132 return tailSet(fromElement, true);133 }134135 // 返回Set的比较器136 public Comparator super E comparator() {137 return m.comparator();138 }139140 // 返回Set的第一个元素141 public E first() {142 return m.firstKey();143 }144145 // 返回Set的最后一个元素146 public E first() {147 public E last() {148 return m.lastKey();149 }150151 // 返回Set中小于e的最大元素152 public E lower(E e) {153 return m.lowerKey(e);154 }155156 // 返回Set中小于/等于e的最大元素157 public E floor(E e) {158 return m.floorKey(e);159 }160161 // 返回Set中大于/等于e的最小元素162 public E ceiling(E e) {163 return m.ceilingKey(e);164 }165166 // 返回Set中大于e的最小元素167 public E higher(E e) {168 return m.higherKey(e);169 }170171 // 获取第一个元素并将该元素从TreeMap中删除。172 public E pollFirst() {173 Map.Entry e m.pollFirstEntry();174 return (e null)? null : e.getKey();175 }176177 // 获取最后一个元素并将该元素从TreeMap中删除。178 public E pollLast() {179 Map.Entry e m.pollLastEntry();180 return (e null)? null : e.getKey();181 }182183 // 克隆一个TreeSet并返回Object对象184 public Object clone() {185 TreeSet clone null;186 try {187 clone (TreeSet) super.clone();188 } catch (CloneNotSupportedException e) {189 throw new InternalError();190 }191192 clone.m new TreeMap(m);193 return clone;194 }195196 // java.io.Serializable的写入函数197 // 将TreeSet的“比较器、容量所有的元素值”都写入到输出流中198 private void writeObject(java.io.ObjectOutputStream s)199 throws java.io.IOException {200 s.defaultWriteObject();201202 // 写入比较器203 s.writeObject(m.comparator());204205 // 写入容量206 s.writeInt(m.size());207208 // 写入“TreeSet中的每一个元素”209 for (Iterator im.keySet().iterator(); i.hasNext(); )210 s.writeObject(i.next());211 }212213 // java.io.Serializable的读取函数根据写入方式读出214 // 先将TreeSet的“比较器、容量、所有的元素值”依次读出215 private void readObject(java.io.ObjectInputStream s)216 throws java.io.IOException, ClassNotFoundException {217 // Read in any hidden stuff218 s.defaultReadObject();219220 // 从输入流中读取TreeSet的“比较器”221 Comparator super E c (Comparator super E) s.readObject();222223 TreeMap tm;224 if (cnull)225 tm new TreeMap();226 else227 tm new TreeMap(c);228 m tm;229230 // 从输入流中读取TreeSet的“容量”231 int size s.readInt();232233 // 从输入流中读取TreeSet的“全部元素”234 tm.readTreeSet(size, s, PRESENT);235 }236237 // TreeSet的序列版本号238 private static final long serialVersionUID -2479143000061671589L;239 }总结(01) TreeSet实际上是TreeMap实现的。当我们构造TreeSet时若使用不带参数的构造函数则TreeSet的使用自然比较器若用户需要使用自定义的比较器则需要使用带比较器的参数。(02) TreeSet是非线程安全的。(03) TreeSet实现java.io.Serializable的方式。当写入到输出流时依次写入“比较器、容量、全部元素”当读出输入流时再依次读取。第4部分 TreeSet遍历方式4.1 Iterator顺序遍历for(Iterator iter set.iterator(); iter.hasNext(); ) {iter.next();}4.2 Iterator顺序遍历// 假设set是TreeSet对象for(Iterator iter set.descendingIterator(); iter.hasNext(); ) {iter.next();}4.3 for-each遍历HashSet// 假设set是TreeSet对象并且set中元素是String类型String[] arr (String[])set.toArray(new String[0]);for (String str:arr)System.out.printf(for each : %s\n, str);TreeSet不支持快速随机遍历只能通过迭代器进行遍历TreeSet遍历测试程序如下1 import java.util.*;23 /**4 * desc TreeSet的遍历程序5 *6 * author skywang7 * email kuiwu-wang163.com8 */9 public class TreeSetIteratorTest {1011 public static void main(String[] args) {12 TreeSet set new TreeSet();13 set.add(aaa);14 set.add(aaa);15 set.add(bbb);16 set.add(eee);17 set.add(ddd);18 set.add(ccc);1920 // 顺序遍历TreeSet21 ascIteratorThroughIterator(set) ;22 // 逆序遍历TreeSet23 descIteratorThroughIterator(set);24 // 通过for-each遍历TreeSet。不推荐此方法需要先将Set转换为数组25 foreachTreeSet(set);26 }2728 // 顺序遍历TreeSet29 public static void ascIteratorThroughIterator(TreeSet set) {30 System.out.print(\n ---- Ascend Iterator ----\n);31 for(Iterator iter set.iterator(); iter.hasNext(); ) {32 System.out.printf(asc : %s\n, iter.next());33 }34 }3536 // 逆序遍历TreeSet37 public static void descIteratorThroughIterator(TreeSet set) {38 System.out.printf(\n ---- Descend Iterator ----\n);39 for(Iterator iter set.descendingIterator(); iter.hasNext(); )40 System.out.printf(desc : %s\n, (String)iter.next());41 }4243 // 通过for-each遍历TreeSet。不推荐此方法需要先将Set转换为数组44 private static void foreachTreeSet(TreeSet set) {45 System.out.printf(\n ---- For-each ----\n);46 String[] arr (String[])set.toArray(new String[0]);47 for (String str:arr)48 System.out.printf(for each : %s\n, str);49 }50 }运行结果---- Ascend Iterator ----asc : aaaasc : bbbasc : cccasc : dddasc : eee---- Descend Iterator ----desc : eeedesc : ddddesc : cccdesc : bbbdesc : aaa---- For-each ----for each : aaafor each : bbbfor each : cccfor each : dddfor each : eee第5部分 TreeSet示例下面通过实例学习如何使用TreeSet1 import java.util.*;23 /**4 * desc TreeSet的API测试5 *6 * author skywang7 * email kuiwu-wang163.com8 */9 public class TreeSetTest {1011 public static void main(String[] args) {12 testTreeSetAPIs();13 }1415 // 测试TreeSet的api16 public static void testTreeSetAPIs() {17 String val;1819 // 新建TreeSet20 TreeSet tSet new TreeSet();21 // 将元素添加到TreeSet中22 tSet.add(aaa);23 // Set中不允许重复元素所以只会保存一个“aaa”24 tSet.add(aaa);25 tSet.add(bbb);26 tSet.add(eee);27 tSet.add(ddd);28 tSet.add(ccc);29 System.out.println(TreeSet:tSet);3031 // 打印TreeSet的实际大小32 System.out.printf(size : %d\n, tSet.size());3334 // 导航方法35 // floor(小于、等于)36 System.out.printf(floor bbb: %s\n, tSet.floor(bbb));37 // lower(小于)38 System.out.printf(lower bbb: %s\n, tSet.lower(bbb));39 // ceiling(大于、等于)40 System.out.printf(ceiling bbb: %s\n, tSet.ceiling(bbb));41 System.out.printf(ceiling eee: %s\n, tSet.ceiling(eee));42 // ceiling(大于)43 System.out.printf(higher bbb: %s\n, tSet.higher(bbb));44 // subSet()45 System.out.printf(subSet(aaa, true, ccc, true): %s\n, tSet.subSet(aaa, true, ccc, true));46 System.out.printf(subSet(aaa, true, ccc, false): %s\n, tSet.subSet(aaa, true, ccc, false));47 System.out.printf(subSet(aaa, false, ccc, true): %s\n, tSet.subSet(aaa, false, ccc, true));48 System.out.printf(subSet(aaa, false, ccc, false): %s\n, tSet.subSet(aaa, false, ccc, false));49 // headSet()50 System.out.printf(headSet(ccc, true): %s\n, tSet.headSet(ccc, true));51 System.out.printf(headSet(ccc, false): %s\n, tSet.headSet(ccc, false));52 // tailSet()53 System.out.printf(tailSet(ccc, true): %s\n, tSet.tailSet(ccc, true));54 System.out.printf(tailSet(ccc, false): %s\n, tSet.tailSet(ccc, false));555657 // 删除“ccc”58 tSet.remove(ccc);59 // 将Set转换为数组60 String[] arr (String[])tSet.toArray(new String[0]);61 for (String str:arr)62 System.out.printf(for each : %s\n, str);6364 // 打印TreeSet65 System.out.printf(TreeSet:%s\n, tSet);6667 // 遍历TreeSet68 for(Iterator iter tSet.iterator(); iter.hasNext(); ) {69 System.out.printf(iter : %s\n, iter.next());70 }7172 // 删除并返回第一个元素73 val (String)tSet.pollFirst();74 System.out.printf(pollFirst%s, set%s\n, val, tSet);7576 // 删除并返回最后一个元素77 val (String)tSet.pollLast();78 System.out.printf(pollLast%s, set%s\n, val, tSet);7980 // 清空HashSet81 tSet.clear();8283 // 输出HashSet是否为空84 System.out.printf(%s\n, tSet.isEmpty()?set is empty:set is not empty);85 }86 }运行结果TreeSet:[aaa, bbb, ccc, ddd, eee]size : 5floor bbb: bbblower bbb: aaaceiling bbb: bbbceiling eee: eeehigher bbb: cccsubSet(aaa, true, ccc, true): [aaa, bbb, ccc]subSet(aaa, true, ccc, false): [aaa, bbb]subSet(aaa, false, ccc, true): [bbb, ccc]subSet(aaa, false, ccc, false): [bbb]headSet(ccc, true): [aaa, bbb, ccc]headSet(ccc, false): [aaa, bbb]tailSet(ccc, true): [ccc, ddd, eee]tailSet(ccc, false): [ddd, eee]for each : aaafor each : bbbfor each : dddfor each : eeeTreeSet:[aaa, bbb, ddd, eee]iter : aaaiter : bbbiter : ddditer : eeepollFirstaaa, set[bbb, ddd, eee]pollLasteee, set[bbb, ddd]set is empty
