JavaSE Set集合
目录
Set 集合是什么？有什么用？
Set 集合类似于一个罐子，对于加入集合的元素，集合通常不能记住元素的添加顺序。
Set 集合与 Collection 集合基本相同，没有提供任何额外的方法。不同在于，Set 集合不允许包含重复元素。
Set 集合和 Map 集合关系密切，HashSet 底层是 HashMap，LinkedHashSet 底层是 LinkedHashMap，TreeSet 底层是 TreeMap。
Set 集合怎么用？
1 Set 集合的继承图（常用部分）
2 Set 接口
Set 接口是 Collection 接口的子接口，没有提供任何额外的方法。
public interface Set<E> extends Collection<E> {
...
// 增：向集合中添加元素
boolean add(E e);
boolean addAll(Collection<? extends E> c);
// 删：从集合中删除指定的元素
boolean remove(Object o);
boolean removeAll(Collection<?> c);
void clear();
// 从当前集合中，删除集合c不包含的元素。相当于留下当前集合和集合c的交集。
boolean retainAll(Collection<?> c);
// 查：判断集合是否包含指定的元素
boolean contains(Object o);
boolean containsAll(Collection<?> c);
// 返回集合中元素的数量
int size();
// 判断集合是否为空
boolean isEmpty();
...
}
3 HashSet 类
-
3-1 介绍
HashSet 类实现了 Set 接口。HashSet 的底层是 HashMap。
HashSet 是线程不安全的。
HashSet 的元素可以为 null，但是只能有一个。
HashSet 不能保证元素的顺序。
HashSet 根据元素的 hashCode，将其添加到数组的特定位置上。通过 equals 方法判断两个元素是否相等。
-
3-2 底层结构
HashSet 的底层是 HashMap。HashSet 的元素保存在 key 上，value 上用一个空值 PRESENT 占位。
（1）HashMap 底层是数组+链表的数据结构。
数组是 Node[] table，数组的每个位置上，存放着 Node 节点，该节点可以指向下一个 Node节点，从而形成链表。
（2）k-v 包装在 Node 类中，该类是 HashMap 的内部类。
public class HashSet<E>...{
...
// HashMap
private transient HashMap<E,Object> map;
// 占位的空值
private static final Object PRESENT = new Object();
// 无参构造器
public HashSet() {
map = new HashMap<>();
}
// 有参构造器，自定义容量
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
// 有参构造器，自定义容量、负载因子
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
...
}
-
3-3 扩容机制
与 HashMap 的扩容机制一样。
public class HashSet<E>...{
...
// HashMap
private transient HashMap<E,Object> map;
// 占位的空值
private static final Object PRESENT = new Object();
// 添加元素
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
...
}
-
3-4 常用方法
移步 Set 接口。
4 LinkedHashSet 类
-
4-1 介绍
LinkedHashSet 是 HasSeth 的子类。LinkedHashSet 底层是 LinkedHashMap。
HashSet 是无序的，即它不能保证元素的迭代顺序和插入顺序一致。
而 LinkedHashSet 可以保证元素的迭代顺序和插入顺序一致。
-
4-2 底层结构
LinkedHashSet 底层是 LinkedHashMap。
public class LinkedHashSet<E> extends HashSet<E>...{
...
// 无参构造器
public LinkedHashSet() {
super(16, .75f, true);
}
// 有参构造器，自定义容量
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
// 有参构造器，自定义容量，负载因子
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
...
}
public class HashSet<E>...{
...
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
...
}
-
4-3 扩容机制
和 LinkedHashMap 一样。
-
4-4 常用方法
移步 Set 接口。
5 TreeSet 类
-
5-1 介绍
TreeSet 类实现了 Set 接口。TreeSet的底层是 TreeMap。
TreeSet 可以保证所有的元素处于有序状态。
-
5-2 底层结构
TreeSet 底层是 TreeMap。
public class TreeSet<E>...{
...
// TreeMap 类实现了 NavigableMap 接口
private transient NavigableMap<E,Object> m;
// 占位空值
private static final Object PRESENT = new Object();
// 无参构造器
public TreeSet() {
this(new TreeMap<E,Object>());
}
// 有参构造器，传入比较器
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
...
}
-
5-3 常用方法
移步 Set 接口。
6 不同 Set 集合的使用场景
HashSet：允许元素无序时使用。
LinkedhashSet：需要元素的取出顺序和插入顺序一致时使用。
TreeSet：需要对元素进行排序时使用。