Java集合HashSet，TreeSet与LinkedHashSet怎么使用(hashset,java,linkedhashset,编程语言)

HashSet继承AbstractSet类，实现Set、Cloneable、Serializable接口。其中AbstractSet提供 Set 接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。 ==Set接口是一种不包括重复元素的Collection，它维持它自己的内部排序，所以随机访问没有任何意义。==

本文基于1.8jdk进行源码分析。

基本属性

基于HashMap实现，底层使用HashMap保存所有元素

构造函数

既然HashSet是基于HashMap，那么对于HashSet而言，其方法的实现过程是非常简单的。

iterator()方法返回对此 set 中元素进行迭代的迭代器。返回元素的顺序并不是特定的。

底层调用HashMap的keySet返回所有的key，这点反应了HashSet中的所有元素都是保存在HashMap的key中，value则是使用的PRESENT对象，该对象为static final。

contains()，判断某个元素是否存在于HashSet()中，存在返回true，否则返回false。更加确切的讲应该是要满足这种关系才能返回true：(o==null ? e==null : o.equals(e))。底层调用containsKey判断HashMap的key值是否为空。

这里注意一点，hashset只是不允许重复的元素加入，而不是不允许元素连成链表，因为只要key的equals方法判断为true时它们是相等的，此时会发生value的替换，因为所有entry的value一样，所以和没有插入时一样的。

而当两个hashcode相同但key不相等的entry插入时，仍然会连成一个链表，长度超过8时依然会和hashmap一样扩展成红黑树，看完源码之后笔者才明白自己之前理解错了。所以看源码还是蛮有好处的。hashset基本上就是使用hashmap的方法再次实现了一遍而已，只不过value全都是同一个object，让你以为相同元素没有插入，事实上只是value替换成和原来相同的值而已。

当add方法发生冲突时，如果key相同，则替换value，如果key不同，则连成链表。

add()如果此 set 中尚未包含指定元素，则添加指定元素。如果此Set没有包含满足(e==null ? e2==null : e.equals(e2)) 的e2时，则将e2添加到Set中，否则不添加且返回false。

由于底层使用HashMap的put方法将key = e，value=PRESENT构建成key-value键值对，当此e存在于HashMap的key中，则value将会覆盖原有value，但是key保持不变，所以如果将一个已经存在的e元素添加中HashSet中，新添加的元素是不会保存到HashMap中，所以这就满足了HashSet中元素不会重复的特性。

remove如果指定元素存在于此 set 中，则将其移除。底层使用HashMap的remove方法删除指定的Entry。

clear从此 set 中移除所有元素。底层调用HashMap的clear方法清除所有的Entry。

clone返回此 HashSet 实例的浅表副本：并没有复制这些元素本身。

后记：

由于HashSet底层使用了HashMap实现，使其的实现过程变得非常简单，如果你对HashMap比较了解，那么HashSet简直是小菜一碟。有两个方法对HashMap和HashSet而言是非常重要的，下篇将详细讲解hashcode和equals。

与HashSet是基于HashMap实现一样，TreeSet同样是基于TreeMap实现的。在《Java提高篇（二七）-----TreeMap》中LZ详细讲解了TreeMap实现机制，如果客官详情看了这篇博文或者多TreeMap有比较详细的了解，那么TreeSet的实现对您是喝口水那么简单。

我们知道TreeMap是一个有序的二叉树，那么同理TreeSet同样也是一个有序的，它的作用是提供有序的Set集合。通过源码我们知道TreeSet基础AbstractSet，实现NavigableSet、Cloneable、Serializable接口。

其中AbstractSet提供 Set 接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。

NavigableSet是扩展的 SortedSet，具有了为给定搜索目标报告最接近匹配项的导航方法，这就意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。Cloneable支持克隆，Serializable支持序列化。

同时在TreeSet中定义了如下几个变量。

其构造方法：

二、TreeSet主要方法

1、add：将指定的元素添加到此 set（如果该元素尚未存在于 set 中）。

2、get：获取元素

该方法与put的流程类似，只不过是把插入换成了查找

3、ceiling：返回此 set 中大于等于给定元素的最小元素；如果不存在这样的元素，则返回 null。

4、clear：移除此 set 中的所有元素。

5、clone：返回 TreeSet 实例的浅表副本。属于浅拷贝。

6、comparator：返回对此 set 中的元素进行排序的比较器；如果此 set 使用其元素的自然顺序，则返回 null。

7、contains：如果此 set 包含指定的元素，则返回 true。

8、descendingIterator：返回在此 set 元素上按降序进行迭代的迭代器。

9、descendingSet：返回此 set 中所包含元素的逆序视图。

10、first：返回此 set 中当前第一个（最低）元素。

11、floor：返回此 set 中小于等于给定元素的最大元素；如果不存在这样的元素，则返回 null。

12、headSet：返回此 set 的部分视图，其元素严格小于 toElement。

13、higher：返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。

14、isEmpty：如果此 set 不包含任何元素，则返回 true。

15、iterator：返回在此 set 中的元素上按升序进行迭代的迭代器。

16、last：返回此 set 中当前最后一个（最高）元素。

17、lower：返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。

18、pollFirst：获取并移除第一个（最低）元素；如果此 set 为空，则返回 null。

19、pollLast：获取并移除最后一个（最高）元素；如果此 set 为空，则返回 null。

20、remove：将指定的元素从 set 中移除（如果该元素存在于此 set 中）。

该方法与put类似，只不过把插入换成了删除，并且要进行删除后调整

21、size：返回 set 中的元素数（set 的容量）。

22、subSet：返回此 set 的部分视图

23、tailSet：返回此 set 的部分视图

由于TreeSet是基于TreeMap实现的，所以如果我们对treeMap有了一定的了解，对TreeSet那是小菜一碟，我们从TreeSet中的源码可以看出，其实现过程非常简单，几乎所有的方法实现全部都是基于TreeMap的。

LinkedHashSet是HashSet的一个“扩展版本”，HashSet并不管什么顺序，不同的是LinkedHashSet会维护“插入顺序”。HashSet内部使用HashMap对象来存储它的元素，而LinkedHashSet内部使用LinkedHashMap对象来存储和处理它的元素。这篇文章，我们将会看到LinkedHashSet内部是如何运作的及如何维护插入顺序的。

我们首先着眼LinkedHashSet的构造函数。在LinkedHashSet类中一共有4个构造函数。这些构造函数都只是简单地调用父类构造函数（如HashSet类的构造函数）。 下面看看LinkedHashSet的构造函数是如何定义的。

在上面的代码片段中，你可能注意到4个构造函数调用的是同一个父类的构造函数。这个构造函数（父类的，译者注）是一个包内私有构造函数（见下面的代码，HashSet的构造函数没有使用public公开，译者注），它只能被LinkedHashSet使用。

这个构造函数需要初始容量，负载因子和一个boolean类型的哑值（没有什么用处的参数，作为标记，译者注）等参数。这个哑参数只是用来区别这个构造函数与HashSet的其他拥有初始容量和负载因子参数的构造函数，下面是这个构造函数的定义，

显然，这个构造函数内部初始化了一个LinkedHashMap对象，这个对象恰好被LinkedHashSet用来存储它的元素。

LinkedHashSet并没有自己的方法，所有的方法都继承自它的父类HashSet，因此，对LinkedHashSet的所有操作方式就好像对HashSet操作一样。

唯一的不同是内部使用不同的对象去存储元素。在HashSet中，插入的元素是被当做HashMap的键来保存的，而在LinkedHashSet中被看作是LinkedHashMap的键。

这些键对应的值都是常量PRESENT（PRESENT是HashSet的静态成员变量，译者注）。

LinkedHashSet使用LinkedHashMap对象来存储它的元素，插入到LinkedHashSet中的元素实际上是被当作LinkedHashMap的键保存起来的。

LinkedHashMap的每一个键值对都是通过内部的静态类Entry<K, V>实例化的。这个 Entry<K, V>类继承了HashMap.Entry类。

这个静态类增加了两个成员变量，before和after来维护LinkedHasMap元素的插入顺序。这两个成员变量分别指向前一个和后一个元素，这让LinkedHashMap也有类似双向链表的表现。

从上面代码看到的LinkedHashMap内部类的前面两个成员变量——before和after负责维护LinkedHashSet的插入顺序。LinkedHashMap定义的成员变量header保存的是 这个双向链表的头节点。header的定义就像下面这样，

接下来看一个例子就知道LinkedHashSet内部是如何工作的了。