本文基于jdk1.8
介绍Set
接口下的常用实现类。
java 集合框架
在前两篇文章中, 我们介绍了Java集合框架下List
接口下的ArrayList
和LinkedList
两个实现类,今天我们来看一下Set
接口下的几个实现类HashSet
、LinkedHashSet
和TreeSet
。下面还是先来看一下Collection
接口的类图:
由类图我们可以看到,set
接口继承自Collection
接口且有四个实现类,分别为AbstractSet
、HashSet
、LinkedHashSet
和TreeSet
,其中AbstractSet
为抽象类,继承自AbstractCollection
,实现了最基本的Collection
骨架。下面我们分别来看一下其余三个实现类的实现原理。
HashSet
对于HashSet
而言,它是基于HashMap
实现的,可以看作是对HashMap
的封装,HashSet
底层使用HashMap
来保存所有元素,因此HashSet
的实现比较简单,相关HashSet
的操作,基本上都是直接调用底层HashMap
的相关方法来完成, 如果看过了HashMap
的源码之后,再来看HashSet
会比较好理解一些,如果对HashMap
的原理不熟悉的话,可以先回顾一下我们前几天对HashMap
分析的博文Java集合框架之HashMap详解。下面我们结合源码来具体分析一下HashSet
的具体实现。
成员变量
首先看一下两个成员变量
通过这两个成员变量我们可以看到,在HashSet
的内部维护着一个HashMap
类型的变量map
,这个map
就是用来存储元素的容器。那我们知道,HashMap
存储的是key-value
形式的键值对,而set
是一个单值对象,这要怎么存储呢?那就要看第二个成员变量PRESENT
了,PRESENT
是一个Object
对象,这个对象就是充当键值对的值的,也就是说,我们只会把需要存储的元素当作map
的key
,而对应的value
则默认为这个Object
对象,这就是HashSet
内部实现存储元素的数据结构。所以由HashMap
的特性我们可以知道,HashSet
存储的元素是无序的,元素不是不可重复的并且可以为null
,基于这个元素不允许重复的特性,HashSet
经常被用来做元素的去重。
构造方法
下面我们看一下HashSet
提供的构造方法。
|
|
HashSet
一共提供了5个构造方法,由构造方法也可以看到,底层是用了HashMap
的数据结构实现,构造方法也跟HashMap
比较类似,这里重点要说一下HashSet(int initialCapacity, float loadFactor, boolean dummy)
这个构造方法,这个构造方法是不对外部公开的,其实放在这里实现是为了给LinkedHashSet
使用,下文我们会讲到这一点。
存取实现
添加元素
由于底层使用了HashMap
作存储结构,这里直接调用了HashMap
的put
方法插入元素,元素被作为key
插入的map
中,而value
则是使用的默认值Object
对象。
遍历HashSet
支持两种遍历方式,Iterator
方式,foreach
方式,不支持随机访问方式遍历。
|
|
特性总结
1、由于底层基于HashMap
实现,内部使用基于哈希表的数组+链表方式存储,所以不保证元素的存取顺序。
2、基于key
的hash
值存储,同样的对象hash
值相同,所以元素不可重复,但是可以为null
,可以快速查找是否包含某个元素。
LinkedHashSet
由类图我们可以看到,LinkedHashSet
继承自HashSet
,内部是基于LinkedHashMap
来实现的。LinkedHashSet
底层使用LinkedHashMap
来保存所有元素,其所有的方法操作上又与HashSet
相同,因此LinkedHashSet
的实现上非常简单,只提供了四个构造方法和一个spliterator
方法,并通过传递一个标识参数,调用父类的构造方法,上文我们说到HashSet
预留了一个不对外部公开的构造方法,就是用在这里。底层构造一个LinkedHashMap来实现
,在相关操作上与父类HashSet
的操作相同,直接调用父类HashSet
的方法即可。
LinkedHashSet
源码,由于底层使用LinkedHashMap
作为存储结构,又继承了HashSet
的各种方法,所以源码比较简单,这里就不做分析了,具体实现原理,参照Java集合框架之LinkedHashMap详解 一文。
特性总结
1、底层存储基于LinkedHashMap
实现,内部使用双向链表存储元素,所以保证了元素的顺序性。
2、基于key
的hash
值存储,同样的对象hash
值相同,所以元素不可重复,但是可以为null
,可以快速查找是否包含某个元素。
TreeSet
还是先看类图,TreeSet
继承自AbstractSet
,实现了NavigableSet
接口,AbstractSet
为抽象类,继承自AbstractCollection
,实现了最基本的Collection
骨架。TreeSet
是基于TreeMap
实现的有序集合,TreeSet
中含有一个NavigableMap
类型的成员变量m
,而m
实际上是TreeMap
的实例。我们知道TreeMap
内部是用红黑树实现元素存储从而保证元素的顺序性的,那么同理TreeSet
同样也是一个有序的集合。通过源码我们知道TreeSet
继承自AbstractSet
,实现NavigableSet
、Cloneable
、Serializable
接口。其中AbstractSet
提供 Set
接口的骨干实现,从而最大限度地减少了实现此接口所需的工作。NavigableSet
是扩展的 SortedSet
,具有了为给定搜索目标报告最接近匹配项的导航方法,这就意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。Cloneable
支持克隆,Serializable
支持序列化。由于TreeSet底层通过调用TreeMap实现,这里不再重复分析了,具体实现原理,参照Java集合框架之TreeMap详解 一文。
成员变量
构造方法
特性总结
1、底层存储基于TreeMap
实现,内部使用红黑树结构表存储元素,所以保证了元素的顺序性。
2、元素不可为null
。
2、遍历时不支持随机访问,只能通过迭代器和for-each
遍进行遍历。
参考
http://www.jianshu.com/p/1f7a8dda341b
http://www.cnblogs.com/leesf456/p/5309809.html
http://blog.csdn.net/canot/article/details/51246944