Java Set简介
Set的主要实现有HashSet、LinkedHashSet和TreeSet,本文尝试简单探究一下它们的实现.本文中的源码都来源于Oracle JDK1.8.
HashSet
历史
HashSet是JDK1.2中引入的,并且是非同步的,如果需要线程安全的,可以使用以下方法返回一个线程安全的实现:
Set s = Collections.synchronizedSet(new HashSet(...));
容量和load factor
HashSet底层使用HashMap存储数据,因此HashSet的容量也就是HashMap的容量,HashMap默认的初始容量是16.load factor是加载因子,即已存在元素和容量的比值超过load factor时会触发HashMap的扩容操作,默认加载因子值为0.75.每次扩容是2倍扩容,但是容量是有上限的,最大容量为2的30次方.如果需要初始化时自定义容量或者load factor,可以使用如下构造器:
HashSet() //默认,初始容量16,加载因子0.75
HashSet(int initialCapacity) //自定义初始容量的构造器
HashSet(int initialCapacity, float loadFactor) //自定义初始容量和加载因子的构造器
HashSet和HashMap
HashSet底层使用的HashMap定义如下:
private transient HashMap<E,Object> map;
再来看看add方法:
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
其实就是调用了map的put方法,只不过只用了map的key部分存储元素,value部分存储的都是一个名为PRESENT的变量,来看看它的定义:
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
其实就是一个普通的Object对象.
元素顺序
HashSet不保证插入元素的顺序,顺序是动态变化的.因此需要保证元素顺序请考虑使用TreeSet和LinkedHashSet.
使用案例
代码为:
@Test
public void hashSetTest() {
HashSet<String> hs = new HashSet<>();
hs.add("ab");
hs.add("aa");
hs.add("ea");
hs.add("bd");
Iterator<String> iterator = hs.iterator();
while (iterator.hasNext()) {
String string = (String) iterator.next();
System.out.println(string);
}
}
打印结果为
aa
ab
bd
ea
可以看到和插入顺序是不一样的.但是排好序了,但是这个排序是不可靠的,编写程序不能依赖这个排序.
LinkedHashSet
历史
LinkedHashSet是JDK1.4中引入的,并且是非同步的,如果需要线程安全的,可以使用以下方法返回一个线程安全的实现:
Set s = Collections.synchronizedSet(new LinkedHashSet(...));
LinkedHashSet和HashSet
翻开LinkedHashSet的源码,发现LinkedHashSet代码很简单,它继承自HashSet:
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable
并且源码中没有出现add、remove等常用的操作元素的方法,使用的是从HashSet中继承的方法.
再来看看几个构造方法
//默认构造方法
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
可以看到3个构造方法都是调用了父类中的同一个私有构造方法,这个私有构造方法定义在HashSet的源码中,这个方法专门是给LinkedHashSet用的:
/**
* Constructs a new, empty linked hash set. (This package private
* constructor is only used by LinkedHashSet.) The backing
* HashMap instance is a LinkedHashMap with the specified initial
* capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the hash map
* @param loadFactor the load factor of the hash map
* @param dummy ignored (distinguishes this
* constructor from other int, float constructor.)
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
HashSet中只有这个私有构造方法底层使用LinkedHashMap存储数据,其它的公共构造方法都是使用HashMap存储数据.
使用案例
代码如下:
@Test
public void linkedHashSetTest() {
LinkedHashSet<String> lhs = new LinkedHashSet<>();
lhs.add("ab");
lhs.add("aa");
lhs.add("ea");
lhs.add("bd");
Iterator<String> iterator = lhs.iterator();
while (iterator.hasNext()) {
String string = (String) iterator.next();
System.out.println(string);
}
}
执行测试结果如下:
ab
aa
ea
bd
可以发现打印的顺序和元素被添加的顺序是完全一致的.
TreeSet
历史
TreeSet是JDK1.2中引入的,并且不是线程安全的.
TreeSet和NavigableMap
TreeSet底层使用一个实现了NavigableMap接口的对象存储数据,定义如下:
/**
* The backing map.
*/
private transient NavigableMap<E,Object> m;
这个具体的对象是在构造的时候赋值的:
public TreeSet() {
this(new TreeMap<E,Object>());
}
这个公开的构造方法调用一个私有的构造方法,私有构造方法如下:
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
把上一步中的TreeMap赋值给了m变量.
有序性
TreeSet中的元素是有序的,插入以后会自动排序.默认使用元素的自然排序(natural ordering),如果使用自定义排序可以通过构造器传入一个Comparator:
TreeSet(Comparator<? super E> comparator) //使用自定义排序的构造器.
使用案例
代码如下:
@Test
public void treeSetTest() {
TreeSet<String> ts = new TreeSet<>();
ts.add("h");
ts.add("z");
ts.add("p");
ts.add("g");
ts.add("b");
ts.add("w");
Iterator<String> iterator = ts.iterator();
while (iterator.hasNext()) {
String string = (String) iterator.next();
System.out.println(string);
}
}
执行测试结果如下:
b
g
h
p
w
z
可以看到是有序排列的.
