Java 集合系列17之 TreeSet详细介绍(源码解析)和使用示例

  1 package java.util;
  2 
  3 public class TreeSet<E> extends AbstractSet<E>  4 implements NavigableSet<E>, Cloneable, java.io.Serializable  5 {  6 // NavigableMap对象  7 private transient NavigableMap<E,Object> m;  8  9 // TreeSet是通过TreeMap实现的，  10 // PRESENT是键-值对中的值。  11 private static final Object PRESENT = new Object();  12  13 // 不带参数的构造函数。创建一个空的TreeMap  14 public TreeSet() {  15 this(new TreeMap<E,Object>());  16  }  17  18 // 将TreeMap赋值给 "NavigableMap对象m"  19 TreeSet(NavigableMap<E,Object> m) {  20 this.m = m;  21  }  22  23 // 带比较器的构造函数。  24 public TreeSet(Comparator<? super E> comparator) {  25 this(new TreeMap<E,Object>(comparator));  26  }  27  28 // 创建TreeSet，并将集合c中的全部元素都添加到TreeSet中  29 public TreeSet(Collection<? extends E> c) {  30 this();  31 // 将集合c中的元素全部添加到TreeSet中  32  addAll(c);  33  }  34  35 // 创建TreeSet，并将s中的全部元素都添加到TreeSet中  36 public TreeSet(SortedSet<E> s) {  37 this(s.comparator());  38  addAll(s);  39  }  40  41 // 返回TreeSet的顺序排列的迭代器。  42 // 因为TreeSet时TreeMap实现的，所以这里实际上时返回TreeMap的“键集”对应的迭代器  43 public Iterator<E> iterator() {  44 return m.navigableKeySet().iterator();  45  }  46  47 // 返回TreeSet的逆序排列的迭代器。  48 // 因为TreeSet时TreeMap实现的，所以这里实际上时返回TreeMap的“键集”对应的迭代器  49 public Iterator<E> descendingIterator() {  50 return m.descendingKeySet().iterator();  51  }  52  53 // 返回TreeSet的大小  54 public int size() {  55 return m.size();  56  }  57  58 // 返回TreeSet是否为空  59 public boolean isEmpty() {  60 return m.isEmpty();  61  }  62  63 // 返回TreeSet是否包含对象(o)  64 public boolean contains(Object o) {  65 return m.containsKey(o);  66  }  67  68 // 添加e到TreeSet中  69 public boolean add(E e) {  70 return m.put(e, PRESENT)==null;  71  }  72  73 // 删除TreeSet中的对象o  74 public boolean remove(Object o) {  75 return m.remove(o)==PRESENT; 76 } 77 78 // 清空TreeSet 79 public void clear() { 80 m.clear(); 81 } 82 83 // 将集合c中的全部元素添加到TreeSet中 84 public boolean addAll(Collection<? extends E> c) { 85 // Use linear-time version if applicable 86 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<E,Object> map = (TreeMap<E, Object>) m; 91 Comparator<? super E> cc = (Comparator<? super E>) set.comparator(); 92 Comparator<? super E> mc = map.comparator(); 93 if (cc==mc || (cc != null && cc.equals(mc))) { 94 map.addAllForTreeSet(set, PRESENT); 95 return true; 96 } 97 } 98 return super.addAll(c); 99 } 100 101 // 返回子Set，实际上是通过TreeMap的subMap()实现的。 102 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, 103 E toElement, boolean toInclusive) { 104 return new TreeSet<E>(m.subMap(fromElement, fromInclusive, 105 toElement, toInclusive)); 106 } 107 108 // 返回Set的头部，范围是：从头部到toElement。 109 // inclusive是是否包含toElement的标志 110 public NavigableSet<E> headSet(E toElement, boolean inclusive) { 111 return new TreeSet<E>(m.headMap(toElement, inclusive)); 112 } 113 114 // 返回Set的尾部，范围是：从fromElement到结尾。 115 // inclusive是是否包含fromElement的标志 116 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { 117 return new TreeSet<E>(m.tailMap(fromElement, inclusive)); 118 } 119 120 // 返回子Set。范围是：从fromElement(包括)到toElement(不包括)。 121 public SortedSet<E> subSet(E fromElement, E toElement) { 122 return subSet(fromElement, true, toElement, false); 123 } 124 125 // 返回Set的头部，范围是：从头部到toElement(不包括)。 126 public SortedSet<E> headSet(E toElement) { 127 return headSet(toElement, false); 128 } 129 130 // 返回Set的尾部，范围是：从fromElement到结尾(不包括)。 131 public SortedSet<E> tailSet(E fromElement) { 132 return tailSet(fromElement, true); 133 } 134 135 // 返回Set的比较器 136 public Comparator<? super E> comparator() { 137 return m.comparator(); 138 } 139 140 // 返回Set的第一个元素 141 public E first() { 142 return m.firstKey(); 143 } 144 145 // 返回Set的最后一个元素 146 public E first() { 147 public E last() { 148 return m.lastKey(); 149 } 150 151 // 返回Set中小于e的最大元素 152 public E lower(E e) { 153 return m.lowerKey(e); 154 } 155 156 // 返回Set中小于/等于e的最大元素 157 public E floor(E e) { 158 return m.floorKey(e); 159 } 160 161 // 返回Set中大于/等于e的最小元素 162 public E ceiling(E e) { 163 return m.ceilingKey(e); 164 } 165 166 // 返回Set中大于e的最小元素 167 public E higher(E e) { 168 return m.higherKey(e); 169 } 170 171 // 获取第一个元素，并将该元素从TreeMap中删除。 172 public E pollFirst() { 173 Map.Entry<E,?> e = m.pollFirstEntry(); 174 return (e == null)? null : e.getKey(); 175 } 176 177 // 获取最后一个元素，并将该元素从TreeMap中删除。 178 public E pollLast() { 179 Map.Entry<E,?> e = m.pollLastEntry(); 180 return (e == null)? null : e.getKey(); 181 } 182 183 // 克隆一个TreeSet，并返回Object对象 184 public Object clone() { 185 TreeSet<E> clone = null; 186 try { 187 clone = (TreeSet<E>) super.clone(); 188 } catch (CloneNotSupportedException e) { 189 throw new InternalError(); 190 } 191 192 clone.m = new TreeMap<E,Object>(m); 193 return clone; 194 } 195 196 // java.io.Serializable的写入函数 197 // 将TreeSet的“比较器、容量，所有的元素值”都写入到输出流中 198 private void writeObject(java.io.ObjectOutputStream s) 199 throws java.io.IOException { 200 s.defaultWriteObject(); 201 202 // 写入比较器 203 s.writeObject(m.comparator()); 204 205 // 写入容量 206 s.writeInt(m.size()); 207 208 // 写入“TreeSet中的每一个元素” 209 for (Iterator i=m.keySet().iterator(); i.hasNext(); ) 210 s.writeObject(i.next()); 211 } 212 213 // java.io.Serializable的读取函数：根据写入方式读出 214 // 先将TreeSet的“比较器、容量、所有的元素值”依次读出 215 private void readObject(java.io.ObjectInputStream s) 216 throws java.io.IOException, ClassNotFoundException { 217 // Read in any hidden stuff 218 s.defaultReadObject(); 219 220 // 从输入流中读取TreeSet的“比较器” 221 Comparator<? super E> c = (Comparator<? super E>) s.readObject(); 222 223 TreeMap<E,Object> tm; 224 if (c==null) 225 tm = new TreeMap<E,Object>(); 226 else 227 tm = new TreeMap<E,Object>(c); 228 m = tm; 229 230 // 从输入流中读取TreeSet的“容量” 231 int size = s.readInt(); 232 233 // 从输入流中读取TreeSet的“全部元素” 234 tm.readTreeSet(size, s, PRESENT); 235 } 236 237 // TreeSet的序列版本号 238 private static final long serialVersionUID = -2479143000061671589L; 239 }

 1 import java.util.*;
 2 
 3 /**  4  * @desc TreeSet的遍历程序  5  *  6  * @author skywang  7  * @email kuiwu-wang@163.com  8 */  9 public class TreeSetIteratorTest { 10 11 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"); 19 20 // 顺序遍历TreeSet 21  ascIteratorThroughIterator(set) ; 22 // 逆序遍历TreeSet 23  descIteratorThroughIterator(set); 24 // 通过for-each遍历TreeSet。不推荐！此方法需要先将Set转换为数组 25  foreachTreeSet(set); 26  } 27 28 // 顺序遍历TreeSet 29 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  } 35 36 // 逆序遍历TreeSet 37 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  } 42 43 // 通过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 }

 1 import java.util.*;
 2 
 3 /**  4  * @desc TreeSet的API测试  5  *  6  * @author skywang  7  * @email kuiwu-wang@163.com  8 */  9 public class TreeSetTest { 10 11 public static void main(String[] args) { 12  testTreeSetAPIs(); 13  } 14 15 // 测试TreeSet的api 16 public static void testTreeSetAPIs() { 17  String val; 18 19 // 新建TreeSet 20 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); 30 31 // 打印TreeSet的实际大小 32 System.out.printf("size : %d\n", tSet.size()); 33 34 // 导航方法 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)); 55 56 57 // 删除“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); 63 64 // 打印TreeSet 65 System.out.printf("TreeSet:%s\n", tSet); 66 67 // 遍历TreeSet 68 for(Iterator iter = tSet.iterator(); iter.hasNext(); ) { 69 System.out.printf("iter : %s\n", iter.next()); 70  } 71 72 // 删除并返回第一个元素 73 val = (String)tSet.pollFirst(); 74 System.out.printf("pollFirst=%s, set=%s\n", val, tSet); 75 76 // 删除并返回最后一个元素 77 val = (String)tSet.pollLast(); 78 System.out.printf("pollLast=%s, set=%s\n", val, tSet); 79 80 // 清空HashSet 81  tSet.clear(); 82 83 // 输出HashSet是否为空 84 System.out.printf("%s\n", tSet.isEmpty()?"set is empty":"set is not empty"); 85 } 86 }