读懂Java集合（四）

本文承接上文读懂Java集合（三），主要整理总结一下集合框架Set接口的常用实现。

💡图中只列出了常见的，省略了部分子接口，本文内容基于JDK 1.8

Set

存储对象的集合，它是无序的(特别的,LinkedHashSet是有序的)，存储的对象不可重复,图中除了TreeSet其他实现类都允许null.值得一提的是所有的Set的实现都是依靠于Map实现的，所以其底层结构与Map一致。

此处的有序指插入与取出的顺序是一致的

HashSet

对Set接口基于哈希表的一种实现，底层是HashMap，跟HashMap key的特点一样,只能存储非重复的值或对象，它基于数组+链表+红黑树实现，初始化时可以指定大小和装载因子，未指定默认大小为16，默认装载因子0.75f,非线程安全。其所有方法都是使用的HashMap的方法。

构造方法

HashSet的构造方法就是对底层的Map进行初始化赋值的.

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
//无参构造
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);
}
//只能被LinkedHashSet使用调用的构造方法
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
  map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
//迭代器,同样是调用的HashMap的
public Iterator<E> iterator() {
  return map.keySet().iterator();
}

之前我知道HashSet底层使用的HashMap的结构和方法,但是对它遍历为什么就只是HashMap的Key,最近又看到它的迭代器我懂了,因为它调用的是map.keySet().iterator().

HashSet只有两种遍历方式:

一种是迭代器,一种是增强型的for循环;
但实际只有一种,因为增强型for循环的本质是迭代器,反编译代码就能发现.

LinkedHashSet

LinkedHashSet继承自HashSet,除了重写spliterator方法,以及自己的构造方法没有其他多余代码。与LinkedHashMap的特点一样是有序的

构造方法

LinkedHashSet的构造方法就是调用父类HashSet构造方法。

//给定初始容量和负载因子
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);
}

TreeSet

NavigableSet接口

从关系图中可以看到一个陌生的接口：NavigableSet，这是一个什么样的接口呢？

它继承自SortedSet接口，是对SortedSet的拓展，主要提供查找给定元素查找最接近匹配项的接口。方法 lower、floor、ceiling 和 higher 分别返回小于、小于等于、大于等于、大于给定元素的元素，如果不存在这样的元素，则返回 null。

构造方法

//底层数据结构NavigableMap
private transient NavigableMap<E,Object> m;
//静态空值value，调用Map的put方法时用到
private static final Object PRESENT = new Object();

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
//无参构造
public TreeSet() {
    this(new TreeMap<E,Object>());
}
//构造时传入比较器
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}
//构造时传入Collection集合
public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}
//构造时传入SortedSet
public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

其他的增删改查、匹配、清除等方法都是调用的Map接口实现。

不支持null的插入

跟TreeMap一样，由于在插入元素时需要比较大小，因此如果未传入自定义比较器对null进行处理的话，元素为null时会抛出空指针异常，所以不支持null值。

热爱生活｜分享技术｜鼓捣科技