Java集合归纳-<二>Set

时间:2022-04-28 19:43:41

Set概要

上一篇说过,Set是Collection的实现之一,在这里我可以说其实Set和Collection基本相同,只是需要注意Set不得存放重复元素即可。下面详细说一下Set在日常开发中用的最多的两种实现,HashSet和TreeSet。

HashSet

特征

HashSet正如其名,因为是按照Hash算法来存储集合中的元素,所以HashSet具有良好的存取和查找性能。还有一点要说的是,感觉很多人认为查询效率和集合是有序还是无序有直接关系,其实不然,关键还是看集合的数据结构和实现算法。HashSet是无序的并不影响他查询性能出色,毕竟Hash算法的诞生就是为了用于快速查找和加密。

HashSet主要有以下三个特点:

  • 无序
  • 非线程同步
  • 集合元素值可以为null(有且仅允许有一个)

等价条件-equals()和hashCode()

这是经典的关于采用hash算法实现的集合逃不开的问题。首先说明HashSet判断两个元素相等的标准是两个对象通过equals()方法比较相等,并且两个对象的hashCode()方法也相等,即:

equals && hashCode

所以我们应该注意,当把一个对象放入HashSet中时,如果需要重写equals()方法,重新设定其返回true的条件的话,那么我们也应该重写hashCode()方法,以保证当equals()为true时hashCode()也为true。

那么为什么要遵循这个规则呢?

  1. 当hashCode()为true,equals()为false。
    此时,由于hashCode()为true,HashSet会认为两个元素存放的地址相同,这就产生了“hash冲突”。我们知道hash表里存储元素的位置被称为bucket(桶),理想情况下,每个桶中存放一个元素拥有最好的性能。现在产生了hash值上的冲突,那么这个桶中就会存放两(多)个元素,桶就会产生链式结构来存放这多个hash冲突的元素,会大大降低性能。

  2. 当hashCode()为false,equals()为true。
    这种情况就不仅仅是性能下降的问题了,因为hash值不一样,HashSet会把这两个对象存放在不同的位置,从而使两个对象都添加成功,但是,这就从根本特性上违背了Set的不可重复性。

重写hashCode()的规则

通过前面的讲解,我们知道了hashCode()方法的重要性,他是HashSet存放和查找元素时决定其物理地址的唯一标准,下面说一说针对集合存放的对象重写其hashCode() 方法时需要注意的几个点:

  • equals()方法返回true时,两个对象的hashCode()方法也应该返回true
  • HashSet中,同一对象多次调用hashCode()方法应该返回相同的结果
  • HashSet中,多个对象间用作equals()方法比较的实例变量,都应该用于计算hashCode值

LinkedHashSet

LinkedHashSet是HashSet的一个子类实现,具有HashSet的所有特性,不同的是,它可以使用链表来维护元素的插入顺序。当我们遍历LinkedHashSet时,LinkedHashSet会按照元素的插入顺序来访问集合中的所有元素。同时,由于需要链表结构来维护顺序,LinkedHashSet的性能是低于HashSet的,除非工作中对集合元素插入的顺序有特殊需求,在两者的取舍中我们都应该优先考虑使用HashSet。

TreeSet

特征

TreeSet是SortedSet接口的实现类,所以可以保证集合元素的排序状态,与HashSet相比,具有以下几个能够体现集合特征的方法:

  • Comparator comparator():TreeSet默认采用自然排序(可以近似的认为是有小到大),那么该方法返回null,如果TreeSet采用自己定制的排序规则comparator,则返回该comparator。
  • Object first():返回集合中排序后的第一个元素。
  • Object last():返回集合中排序后的最后一个元素。
  • Object lower(Object e):返回集合中位于制定元素之前的元素,即小于指定元素的最大元素,参考元素不要求一定是当前TreeSet集合中存在的元素。(比如一个TreeSet为[0,2,5,9],可以返回lower(3)->2,3并不是该集合中的元素,higher方法同理)。
  • Object higher(Object e):返回集合中位于制定元素之后的元素,即大于指定元素的最小元素,参考元素不要求一定是当前TreeSet集合中存在的元素。
  • SortedSet subSet(Object fromElement, Object toElement):返回此Set的子集合。
  • SortedSet headSet(Object toElement):返回此Set中由小于toElement元素组成的子集。
  • SortedSet tailSet(Object fromElement):返回此Set中由大于等于fromElement元素组成的子集。

记忆这些方法的诀窍很简单,就是返回TreeSet中的第一个,前一个,后一个,最后一个元素的方法,和截取TreeSet子集的方法。

实现

与HashSet采用hash算法来觉得元素的存储地址不同,TreeSet底层采用红黑树实现,关于红黑树的详细知识可以参考这篇文章:红黑树(一)之 原理和算法详细介绍。这篇文章讲得很细致,有兴趣的同学可以花时间好好看看,对于数据结构的学习也是很有帮助的。

Comparable接口

说到TreeSet的排序功能,自然要提到比较,TreeSet在插入元素时,会调用元素的compareTo(Object e)方法来比较元素之间的大小关系。compareTo()方法是Java提供的Comparable接口中的方法,要实现这个接口就必须实现compareTo()方法
在默认的自然排序下,obj1.compareTo(obj2)有三种结果:

  • 0,obj1等于obj2
  • 正整数,obj1大于obj2

当然,为了方便,Java中很多常用类都已经实现了Comparable接口,并且提供了排序标准,下面是实现了Comparable接口的常用类:

  • BigDecimal、BigInteger以及所有的数值型对应包装类,按照他们的数值大小进行比较。
  • Character:按照字符的UNICODE值进行比较。
  • Boolean:true的包装类实例大于false的包装类实例。
  • String:按照字符串中字符的UNICODE值进行比较。
  • Date、Time:越新的时间越大。

当我们试图将一个对象插入到TreeSet中时,该对象就必须实现Comparable接口,否则会抛出ClassCastException异常。同时,TreeSet默认情况下只允许存储统一类型的对象,否则会产生一些不正常的运行表现。这点很好理解,只有统一类型才能保证比较逻辑上的一致性。如果插入元素时,compareTo方法返回0,说明集合中已经存在了一样的元素,那么该集合就不能被插入,体现了Set元素的不可重复性。

总结

性能上,HashSet总比TreeSet摇号,尤其是添加和查询操作,由于hash算法的存在,HashSet都会快得多,因为TreeSet需要额外的红黑树算法来维护集合元素的排序。理论上,只有当需要一个能保持排序的Set时,我们才会考虑使用TreeSet,否则都该首选HashSet。
LinkedHashSet由于要使用链表来维护集合元素的插入顺序,也会带来额外的开销,但是因为链表的实现方式,它的遍历操作相较于HashSet会更快捷。
还有一点就是,HashSet和TreeSet都是线程不安全的。为了防止多线程访问同一个Set而导致的不同步问题,我们必须手动保证Set的线程安全,通常可以使用Collections工具类的SynchronizedSortedSet装饰符在创建Set时来包装Set集合,如下所示:

SortedSet sortedSet = Collections synchronizedSortedSet(new TreeSet(...));