Collection中Set家族:
### TreeSet关于他的一些详细特性在Collection调集系统全景图(三)已经详细讲过, > TreeSet底层是选用TreeMap完成的一种Set,所以它是有序的,同样也对错线程安全的。TreeMap 底层数据结构是红黑树
TreeSet特点
- 有序性:TreeSet中的元素是有序的,它们依照天然次序或许指定的比较器次序进行排序。
- 仅有性:TreeSet中的元素是仅有的,它们不会重复。
- 可排序性:TreeSet中的元素能够依照天然次序或许指定的比较器次序进行排序。
- 底层数据结构:TreeSet底层选用红黑树完成,因而刺进、删去、查找等操作的时刻复杂度为O(log n)。
- 线程不安全:TreeSet不是线程安全的,假如多个线程一起拜访一个TreeSet方针,可能会出现并发问题。
- 不允许空元素:TreeSet不允许刺进空元素,不然会抛出NullPointerException异常。
运用事例
import java.util.TreeSet;
public class TreeSetExample {
public static void main(String[] args) {
// 创立一个TreeSet方针
TreeSet<Integer> set = new TreeSet<>();
// 增加元素
set.add(5);
set.add(2);
set.add(8);
set.add(1);
set.add(10);
// 打印调集元素
System.out.println("TreeSet调集元素:" + set);
// 获取第一个元素
int first = set.first();
System.out.println("第一个元素:" + first);
// 获取最终一个元素
int last = set.last();
System.out.println("最终一个元素:" + last);
// 获取小于等于指定元素的最大元素
int floor = set.floor(6);
System.out.println("小于等于6的最大元素:" + floor);
// 获取大于等于指定元素的最小元素
int ceiling = set.ceiling(6);
System.out.println("大于等于6的最小元素:" + ceiling);
// 获取小于指定元素的最大元素
int lower = set.lower(6);
System.out.println("小于6的最大元素:" + lower);
// 获取大于指定元素的最小元素
int higher = set.higher(6);
System.out.println("大于6的最小元素:" + higher);
// 删去元素
set.remove(5);
System.out.println("删去元素5后的调集元素:" + set);
// 获取调集巨细
int size = set.size();
System.out.println("调集巨细:" + size);
// 判别调集是否为空
boolean empty = set.isEmpty();
System.out.println("调集是否为空:" + empty);
// 清空调集
set.clear();
System.out.println("清空调集后的元素:" + set);
}
}
TreeSet源码剖析
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
它承继了 AbstractSet类,因而它具有 Set 接口的一切基本功能,如增加、删去、查找等操作。一起,它还完成了 NavigableSet接口,这意味着它支撑一些高档操作,如获取子集、查找最小值和最大值、查找前驱和后继元素等。此外,它还完成了 Cloneable 和 Serializable 接口,这意味着它能够被克隆和序列化。
//用于存储 TreeSet 中的元素。其间,NavigableMap 是一个支撑依照排序次序拜访键值对的 Map 接口,
//它扩展了 SortedMap 接口
//transient关键字表明该字段不会被序列化
private transient NavigableMap<E,Object> m;
//表明一个静态常量,用于作为NavigableMap中的 value,因为NavigableMap的完成是依据Map的
//而Map中的 value 是能够为 null 的,但是`TreeSet`中的元素是不能重复的,
//因而需求一个非 null 的 value 来占位。
private static final Object PRESENT = new Object();
//结构办法,接受一个NavigableMap类型的参数m,将其赋值给成员变量m
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
//无参结构办法,创立一个默许的空的TreeSet,底层运用TreeMap完成
public TreeSet() {
this(new TreeMap<E,Object>());
}
//创立一个新的TreeSet实例,运用指定的Comparator来比较元素,并运用一个新的TreeMap实例来存储元素
//TreeSet是一个有序的调集,它依据元素的天然次序或许指定的Comparator来排序元素
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
事例教学
// 创立一个依照字符串长度从小到大排序的 TreeSet
TreeSet<String> set = new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length() - o2.length();
}
});
// 增加元素
set.add("hello");
set.add("world");
set.add("java");
// 输出结果
System.out.println(set); // [java, hello, world]
持续源码剖析TreeSet
//这个结构函数是用来创立一个 TreeSet 方针,并将指定调集中的一切元素增加到 TreeSet 中。其间,参数 c 是一个调集,它包括了要增加到 TreeSet 中的元素
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
//用于将一个调集中的一切元素增加到另一个调集中。
//它还查看源调集是否是一个有序调集,而且方针调集是否是一个TreeMap。假如是,则将源调集中的元素增加到方针调集中
//并回来true。假如不是,则调用父类的addAll办法
public boolean addAll(Collection<? extends E> c) {
//Map方针m的巨细为0;
// 调集c的巨细大于0,且c是SortedSet类型,m是TreeMap类型
//instanceof是 Java 中的一个关键字,用于判别一个方针是否属于某个类或其子类的实例
//c instanceof SortedSet判别调集c是否是SortedSet类或其子类的实例,
//m instanceof TreeMap判别映射m是否是TreeMap类或其子类的实例
//说明调集c是有序调集,映射m是依据红黑树完成的有序映射。
//SortedSet是Java调集结构中的一个接口,它承继自Set接口,表明一个有序的调集
if (m.size()==0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) {
SortedSet<? extends E> set = (SortedSet<? extends E>) c;
TreeMap<E,Object> map = (TreeMap<E, Object>) m;
Comparator<?> cc = set.comparator();
Comparator<? super E> mc = map.comparator();
if (cc==mc || (cc != null && cc.equals(mc))) {
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
return super.addAll(c);
}
//用于将一个调集中的一切元素增加到当前调集中
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
}
TreeSet(Collection<? extends E> c) 的运用事例:
List<Integer> list = new ArrayList<>();
list.add(3);
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(2);
TreeSet<Integer> set = new TreeSet<>(list);
System.out.println(set);//输出结果为:[1, 2, 3, 4]
持续源码剖析TreeSet
//完成了SortedSet接口中的iterator()办法,回来一个迭代器,
//用于遍历调集中的元素。详细完成是经过调用TreeMap的navigableKeySet()办法获取一个有序的键调集,然后回来该键调集的迭代器
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
}
//逆序迭代
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
}
//return m.put(e, PRESENT)==e不存在于m中,则将其增加到m中,并回来true,不然不做任何操作并回来false
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
//该办法回来一个NavigableSet,该调集包括从fromElement到toElement规模内的元素。
//fromInclusive和toInclusive参数指定是否包括fromElement和toElement自身。
//该办法运用TreeMap的subMap办法来完成子集的创立。
//规模取值
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
//该办法回来一个NavigableSet,其间包括小于(或等于,假如包括toElement)给定元素的一切元素
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new TreeSet<>(m.headMap(toElement, inclusive));
}
//该办法回来一个NavigableSet,其间包括大于(或等于,fromElement)给定元素的一切元素
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
return new TreeSet<>(m.tailMap(fromElement, inclusive));
}
subSet事例完成
import java.util.NavigableSet;
import java.util.TreeSet;
public class TreeSetExample {
public static void main(String[] args) {
// 创立一个TreeSet
TreeSet<Integer> treeSet = new TreeSet<>();
// 增加元素
treeSet.add(10);
treeSet.add(20);
treeSet.add(30);
treeSet.add(40);
treeSet.add(50);
// 获取子集
NavigableSet<Integer> subSet = treeSet.subSet(20, true, 40, true);
// 输出子集
System.out.println("子集元素:");
for (Integer i : subSet) {
System.out.println(i); //20,30,40
}
}
}
以上就是TreeSet 源码中比较重要的点,其他的一些办法大家能够自行学习探讨
LinkedHashSet特点
- 有序性:LinkedHashSet中的元素是依照刺进次序进行排序的,因而能够保证元素的次序性。
- 能够避免重复元素:LinkedHashSet中不允许存储重复元素,假如尝试增加重复元素,将会被忽略。
- 性能较好:LinkedHashSet的性能与HashSet适当,但是因为需求维护元素的刺进次序,因而在刺进和删去元素时可能会略微慢一些。
- 底层完成是HashMap:LinkedHashSet的底层完成是一个HashMap,因而具有HashMap的一切特点,如快速查找、高效存储等。
LinkedHashSet源码剖析
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
LinkedHashSet 是一个有序的调集,它保留了元素刺进的次序。它承继了 HashSet 的一切办法,而且增加了一些额外的办法来支撑有序调集。
//LinkedHashSet类的结构办法,它接受两个参数:initialCapacity
//和loadFactor。initialCapacity表明调集的初始容量,loadFactor表明负载因子
//适当创立一个指定参数HashSet调集
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
//给一个初始容量,负载因子默许扩容参数,0.75,能够包容75%的元素,然后就需求扩展容量。
//适当创立一个初始值
HashSet调集
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
//给一个初始容量16,负载因子为0.75
public LinkedHashSet() {
super(16, .75f, true);
}
//,它包括从指定调集中获取的元素。它首先调用父类HashSet的结构函数,
//该结构函数将初始容量设置为指定调集巨细的两倍或11(取两者中的较大值),负载因子为0.75,
//以及指定LinkedHashSet实例的拜访次序为刺进次序。
//它调用addAll办法将指定调集中的一切元素增加到新的LinkedHashSet中
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
LinkedHashSet事例演示
import java.util.LinkedHashSet;
public class LinkedHashSetExample {
public static void main(String[] args) {
LinkedHashSet<String> set = new LinkedHashSet<>();
// 增加元素
set.add("apple");
set.add("banana");
set.add("orange");
set.add("apple"); // 重复元素不会被增加
// 打印元素
System.out.println(set); // 输出 [apple, banana, orange]
// 删去元素
set.remove("banana");
// 判别元素是否存在
System.out.println(set.contains("apple")); // 输出 true
System.out.println(set.contains("banana")); // 输出 false
// 获取元素数量
System.out.println(set.size()); // 输出 2
// 清空调集
set.clear();
System.out.println(set); // 输出 []
}
}