我们在介绍Collection的时候对
Set的了解是:存无序、唯一不可重复的元素的 Collection。通过这篇文章我们来详细理解Set接口以及实现类,通过这篇文章,我们可以了解到以下几点:
- Set接口概要和主要(特有)方法
- Set相关主要实现类主要功能、使用场景以及源码实现
- Set如何判断对象相等
目录:
一、Set概要
官方描述:
1 | /** |
从官方描述我们可以对set的作用做出如下归纳:
- set注重独一无二的性质,该体系集合可以已知某个元素是否存在这个集合中并且不会存储重复元素。
- set的相等比较是基于 hashCode 和 equals 方法比较的
除了以上两点,其实Set主要由内部的Map决定的,可以说Set就是Map的一个马甲。Set的单个元素由HashMap
承载。
Set继承和实现关系:
Set的结构关系如上,总结关系和上篇文章说到的List类似,其中最重要的两个实现类为:HashSet和TreeSet。
二、Set主要实现类讲解
HashSet
HashSet可以看做是一个包装之后的HashSet,具体点说就是HashSet里面有一个HashMap(适配器模式)。
他是一个哈希表结构,新增元素相当于HashMap的key,value默认为一个固定的Object。它继承于AbstractSet,
实现了Set, Cloneable, Serializable接口。HashSet是线程不安全,若2个线程同时操作HashSet,必须通过代码实
现同步。
关于HashSet的方法我们需要关注的方法是add方法。
1 | // Dummy value to associate with an Object in the backing Map |
通过查看以上的源码,我们可以了解到:实际的逻辑都是在HashMap的put()方法中,关于put的实现,我们会在之后的文章讲解。
我们还需要关注的是,hashSet如何保证Set的数据的不重复,元素的哈希值是通过元素的hashcode方法 来获取
的, HashSet首先判断两个元素的哈希值,如果哈希值一样,接着会比较equals方法 如果 equls结果为true ,
HashSet就视为同一个元素。如果equals 为false就不是同一个元素。哈希值相同equals为false的元素是怎么存储
呢,就是在同样的哈希值下顺延(可以认为哈希值相同的元素放在一个哈希桶中)。也就是哈希一样的存一列。如
下图所示
总结:通过hashCode值来确定元素在内存中的位置。一个hashCode位置上可以存放多个元素。
当hashcode() 值相同equals() 返回为true 时,hashset 集合认为这两个元素是相同的元素.只存储一个(重复元素无
法放入)。调用原理:先判断hashcode 方法的值,如果相同才会去判断equals 如果不相同,是不会调用equals方法
的。
遍历HashSet的时候,由于Set集合中并没有角标的概念,所以并没有像List一样提供get()方法。当获取
HashSet中某个元素时,只能通过遍历集合的方式进行equals()比较来实现
TreeSet
从名字上可以看出,此集合的实现和树结构有关。与HashSet集合类似,TreeSet也是基于Map来实现,具体实现
TreeMap(后面讲解),其底层结构为红黑树(特殊的二叉查找树);与HashSet不同的是,TreeSet具有排序功
能,分为自然排序(123456)和自定义排序两类,默认是自然排序;在程序中,我们可以按照任意顺序将元素插入
到集合中,等到遍历时TreeSet会按照一定顺序输出–倒序或者升序;
具有如下特点:
- 对插入的元素进行排序,是一个有序的集合(主要与HashSet的区别);
- 底层使用红黑树结构,而不是哈希表结构;
- 允许插入Null值;
- 不允许插入重复元素;
- 线程不安全;
关于排序,对集合元素排序,有两种方法是分为自然排序和自定义排序,那么这两种方式如何实现呢?在TreeSet
调用add方法时,会调用到底层TreeMap的put方法,在put方法中会调用到compare(key, key)方法,进行key大小
的比较;此外,还有另一种方式,那就是实现Comparetor
三、Set是如何判断两个对象相等
set想要保证两个元素不重复,那么它是怎么保证的呢?这就是Object.equals方法了。但是,如果每增加一个
元素就检查一次,那么当元素很多时,后添加到集合中的元素比较的次数就非常多了。 也就是说,如果集合中现
在已经有1000个元素,那么第1001个元素加入集合时,它就要调用1000次equals方法。这显然会大大降低效率。
那么就要引入哈希算法,当我们调用哈希容器的get(Object obj)方法时,它会首先利用查看当前容器中是否存在有
相同哈希值的对象,如果不存在,那么直接返回null;如果存在,再调用当前对象的equals()方法比较一下看哈希
处的、对象是否和要查找的对象相同;如果不相同,那么返回null。如果相同,则返回该哈希处的对象。关于
hashCode的介绍可以参考博文https://www.jianshu.com/p/2c1b6dd312eb。
比如说,如果想要让两个不同的User对象视为相等的,就必须覆盖Object继下来的hashCode方法和equals方
法,因为Object hashCode方法返回的是该对象的内存地址(可以这么理解但是实际上不一定是内存地址),所以必
须重写hashCode方法,才能保证两个不同的对象具有相同的hashCode,同时也需要两个不同对象比较equals方
法会返回true