Set家族简介

背景

Set家族是Collection Framework中重要的一个分支,它的含义就是数学意义上的set概念,也就是说它的元素满足互斥性,如果e1,e2都属于一个Set,则e1.equals(e2)一定返回false,否则,在添加的时候,后面加入的元素无法被添加进来。Set在存储互斥元素的时候有很好的作用,如果我们希望在一个集合中存储唯一元素,如key值,则可以选择Set的子类进行存储。

Set简述

Set不能存储相等的两个元素,那么就有一个问题,如果元素存入后改变了怎么办?通常的,一个元素的值得改变如果影响到了equals方法的返回值,Set并没有规定必须抛出异常,但在添加的时候,尽量不要添加会改变equals返回值的元素。

Set中的方法与父接口中方法签名一致,但我在阅读源码的时候,发现Set还是重写了父接口的方法,这在语法上并不是必要的,在此我就暂且“以小人之心度一下源码大大之意“吧。

  • Set中的方法虽然签名与Collection相同,但具体含义不一样,如add方法,Collection是随意添加一个元素,而Set是添加一个之前在集合中不存在的元素
  • 为了写方法的doc注释,Collection中add方法和Set中add方法的注释不同

Set家族中有几个重要的成员,HashSet、SortedSet、TreeSet,下面简单介绍一下各自的含义

  • HashSet:Set接口的实现类,内部存储结构为Hash表,实际上是由HashMap实现的HashSet
  • SortedSet:Set接口的子接口,代表了一类排序的Set,其元素排列顺序为自然排序或者通过具体的comparator比较
  • TreeSet:SortedSet的一个实现类,内部存储结构为红黑树,实际是由TreeMap实现的

HashSet

HashSet是一个Hash表实现的Set结构,其内部具体存储元素的是HashMap对象(HashMap是Map家族的重要成员,将在Map中进行分析),其具体代码如下:

1
2
3
4
5
6
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 boolean add(E e) {
return map.put(e, PRESENT)==null;
}

由上面代码可以看出,HashSet中的元素实际上被存储为HashMap的key值,其唯一性由HashMap来保证,而HashMap的value值为一个静态常量PRESENT,它是一个Object对象。该对象用于判断map.remove时的返回值是否与其相同,来确保remove方法正确的删除了指定元素。

HashSet中有两个比较重要的概念是initialCapacity和loadFactor,它们也是HashMap中的重要概念,在此只做简单的描述,详细的在Map中进行分析。

  • initialCapacity是bucket的默认大小,bucket也就是Hash表中一个key值对应的存储容量,是为了解决key冲突的,一个理想的Hash表应当是每个key对应一个值,这样可以在O(1)的时间内读取到一个值,但这需要Hash算法能把key值散列的完全没有重复才可以达到,而这在现实中是不可能的,因此bucket的存在就很关键,由此可见HashMap是通过开链法解决冲突的
  • loadFactor是bucket的默认填充因子,是一个0~1间的小数,代表了一个bucket最多可以填充多少百分比

HashSet是线程不安全的,如果需要获取一个同步Set,可以使用下面的代码

1
Set s = Collections.synchronizedSet(new HashSet(...));

HashSet的iterator也是fail-fast的,如果在iterator遍历时,使用了除iterator的remove方法之外的方法改变了HashSet,则会抛出ConcurrentModificationException,这部分的实现是与

LinkedHashSet

LinkedHashSet是HashSet的子类,是从1.4版本开始加入Set家族的(HashSet从1.2就存在了),它主要解决的问题是HashSet在返回iterator的时候,顺序不统一的问题,因此LinkedHashSet使用了链表的方式,确保了元素的遍历顺序,该顺序与元素插入顺序一致。LinkedHashSet内部使用了LinkedHashMap存储元素值,它的iterator也是调用了LinkedHashMap的iterator方法。

LinkedHashSet的典型使用场景是客户端展示数据,因为相同的集合,客户端希望展示的数组顺序是一样的,此时可以选择使用LinkedHashSet返回元素集合。严格意义上也可以使用TreeSet实现相同的功能,但TreeSet耗时比LinkedHashSet更大,因此LinkedHashSet是更好的选择。

SortedSet

SortedSet是Set的一个子接口,它的含义跟它的名字一样——排序集合。它可以根据元素的自然顺序进行存储,也可以通过指定Comparator,来实现自己的排序逻辑。插入的元素必须实现Comparable接口(或者可以接受Comparator的compare方法),e1.compareTo(e2)或者comparator.compare(e1, e2)方法必须不能抛出ClassCastException异常。

SortedSet的实现类有以下几点限制:

  • 一个无参构造方法,创建一个自然顺序的SortedSet
  • 一个传入Comparator的构造方法,根据Comparator的compare方法进行排序
  • 一个传入Collection的构造方法,根据自然顺序创建一个Collection的拷贝
  • 一个传入SortedSet的构造方法,创建一个跟传入对象相同的SortedSet

SortedSet中定义了几个方法:

  • comparator() 返回用于排序的Comparator
  • first() 返回Set的第一个元素
  • headSet(E toElement) 返回toElement之前所有元素组成的集合
  • subSet(E fromElement, E toElement)返回一个half-open的子集合,范围为[fromElement, toElement)
  • tailSet(E fromElement) 返回fromElement之后所有元素组成的集合

NavigableSet是SortedSet的一个子接口,也是TreeSet实现的接口,因此在这里简单介绍。NavigableSet顾名思义,是一个可以查找的Set,而且通常意义上很快(TreeSet通过红黑树实现,可以实现O(logN)的查找)。因此可以通过指定一个target,来返回想要查找的元素。

NavigableSet提供了几个实用的方法:

  • lower(E e)返回小于e的最大元素
  • floor(E e) 返回小于或等于e的最大元素
  • ceiling(E e)返回大于或等于e的最小元素
  • higher(E e) 返回大于e的最小元素
  • descendingSet() 和 descendingIterator()分别返回一个倒序的Set和Iterator
  • pollFirst() 和 pollLast() 分别返回第一个、最后一个元素

TreeSet

TreeSet实现了NavigableSet,它是基于TreeMap存储的,由于TreeMap实现了红黑树,因此TreeSet也提供了O(logN)的插入、删除、查找操作。

TreeSet的方法是NavigableSet和SortedSet的方法并集,在此不再进行罗列。源码中各个方法都是使用TreeMap的相应方法实现,在此也不过多描述,在TreeMap中进行详细的分析。

总结

分析到这里,发现Set家族的儿子都是从别人家偷的(HashSet使用了HashMap,TreeSet使用了TreeMap),真是精致的拿来主义者啊。不过这在代码的实现中,确实很高的技巧,完美的实现了DRY(Don’t repeat yourself)原则。Set家族的分析相对比较简单,因为大多都是Map家族的成员帮助它们完成了功能,因此,在下一步Map的分析就显得任重道远了。Set家族使用的场景虽然不多,但经过一番分析之后,也是挖掘了不少潜在价值,合理利用HashSet和TreeSet,可以减少很多代码的工作量。