前言
本文使用用的是jdk1.8
Set 接口
我们前面再Collection集合的文章中已经简单的说过Set集合的特点。
- 不包含重复元素，即两个元素
e1.equals(e2)不可相等。
需要注意的是：
当可变对象存储到Set集合中的时候，如果通过一种可以影响对象的equals函数的比较结果的方式改变了该对象的话那么Set集合的行为则是不确定的。
Set 集合的常见实现类
image
- HashSet：底层是通过HashMap来实现的，所以底层数据结构式是 散列表+红黑树 的数据结构。
- TreeSet：底层数据结构是通过NavigableMap来实现的，底层数据结构是 红黑树。可保证元素的排列方式
- LinkedHashSet：继承自HashSet，和LinkedHashMap意义相似，底层数据结构是 散列表+双向链表
HashSet
总的来说：
- 实现了Set接口，底层其实是一个HashMap实例，所以由于HashMap的特性，无法保证元素的迭代的顺序(HashMap扩容后的重散列会导致元素存储位置的变更)。同时和HashMap一样可以使用null元素做键值，但只能是一个。
- 对Set结合进行迭代所需的时间与HashSet实例的大小(元素的数量)和底层HashMap实例（桶的数量）的“容量”的和成比例。如果某个Set的迭代性能比较重要，不要将初始容量设置的太高，或者将加载因子设置的太小(会出现很多空桶)。
- 非同步，并发不安全。可以程序外部手动同步，也可以借助
Collections.synchronizedSet函数来对该Set集合进行包装来实现同步。 - 迭代器是快速失败的
HashSet的属性及函数
image
一眼看上去还是很简单的。只有两个属性，一个是它具体实现类HsahMap，另一个则是一个Object实例。这个Object实例在这里是充当HashMap实例中所有元素的公共value的。因为我们HashSet底层是通过HashMap来实现的，所有元素实际都存储在key中，那么所对应的value如果不赋值则是null值得存在。所以HashSet的处理方式就是将所有元素的value都赋予该Object实例。
所以整个HashSet整体上来说几乎所有的操作都是在底层操作了一个HashMap实例。根据上图我们来看一下HashSet所实现的Set接口的函数都是怎么实现的。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public void clear() {
map.clear();
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public Iterator<E> iterator() {
return map.keySet().iterator();
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public int size() {
return map.size();
}
所有的构造函数所做的也是统一的初始化HashMap的操作
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
TreeSet
总的来说：
- 底层实现：和HashSet实现方式一样，底层其实是由一个TreeMap实例来实现的。并实现了NavigableSet接口，是一个基于TreeMap的NavigableSet的实现
-
有序：由于实现的NavigableSet接口继承自SortedSet接口，所以存入TreeSet的所有元素都必须是实现了Comparable接口的，即保证这些元素在存入TreeSet的时候在通过
compareTo函数进行比较并自然排序的时候不会报ClassCastException。或者也可以在Set实例构造的时候通过传入的 Comparator来进行控制排序。 -
非同步：并发线程不安全。还是老样子，倘若想同步需要函数外手动进行控制，或者在创建Set集合的时候借助
Collections类。Collections.synchronizedSortedSet的方法来对某个Set集合进行包装。 - 迭代器：迭代器是快速失败的
-
复杂度：基本操作函数如
add,remove,contains的复杂度都是log(n)级别的(TreeMap底层红黑树)。
TreeSet的属性和函数
image
从图可以很明显的看出它的实现机制和HashSet是一模一样的。底层通过NavigableMap来实现，而NavigableMap则只有TreeMap这一个实现类。我们也可以称之为底层是由TreeMap来实现的，而Object实例则是充当所有元素的value的存在。
image
我们来看一下TreeSet的5个构造函数都是如何实现的
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
还是清晰的。都是通过构造一个TreeMap来实现整个TreeSet的所有操作的。
LinkedHashSet
总的来说：
- 实现：LinkedHashSet底层由散列表和双向链表来实现的。这一点和LinkedHashMap一样。LinkedHashSet由HashSet和LinkedList共同来实现的。底层是HashMap，只是各节点Entry另外的还添加了两个属性before和after，通过双向列表来链接。
- 迭代：迭代有序，由于所有元素都通过LinkedeList双向链表来维护，所以将按照元素插入到set中的顺序（插入顺序）进行迭代。需要注意的是如果一个元素已经存在于LinkedHashSet中如果再插入该元素的话，该元素会被重新插入。并且迭代的时候和HashSet容量没有关系。因为它结构中维护的一个双向链表，迭代的时候是迭代这个双向链表。相比于此HashSet迭代时则要受到容器容量很大的限制。
-
优点
- 使用LinkedHashSet可以不用像HashSet一样元素杂乱无序，而保证元素一定的有序性，可以做到TreeSet的功能却不用TreeSet的成本。
- 初始容量的大小对LinkedHasSet的影响要比对HashSet小很多，因为它在迭代的时候不受容器大小的影响。
-
缺点
- 性能比HashSet要差一点儿，因为还要维护一个双向链表。
- 允许null。非同步的，迭代是快速失败的
LinkedHashSet的属性和函数
image
很纯粹的类，没有自己实现的东西。所有的函数都是继承自各个父类
我们来看一下它的构造函数：
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
可以看出，都是去构造其父类HashSet。
总结
可以看到整个Set集合的实现都是Map映射。
- HashSet：无序，允许为null，底层是HashMap(散列表+红黑树)，非线程同步
- TreeSet：有序，不允许为null，底层是TreeMap(红黑树)，非线程同步
- LinkedHashSet：迭代有序，允许为null，底层是HashMap+双向链表，非线程同步
网友评论