HashSet、LinkedHashSet和TreeSet介绍

我们先认识一下框架图

集合四课之二　Set接口下，HashSet、LinkedHashSet和TreeSet介绍与区别附带速记卡

HashSet

HashSet有以下特点

不能保证元素的排列顺序，顺序有可能发生变化
不是同步的
集合元素可以是null,但只能放入一个null
没有set和get方法只能通过迭代器取值

当向HashSet结合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据 hashCode值来决定该对象在HashSet中存储位置。

HashSet集合判断两个元素相等的标准是着些判断俩个对象的hashCode值是否相等，第2步会调用equals方法比较相等，返回false，做add操作。

那为什么要同时判断equals方法和hashCode方法呢？问题一
而且还要先判断hashCode然后再判断equals方法? 问题二

问题一

关于同时判断equals方法和hashCode方法的必要性

因为存在“hashCode值不同，对象相同的情况，对象相同的情况，hashCode也不同的情况”; 哎，这个说法，怎么感觉有点不对呢？不是之前都是这样认定的嘛“俩个对象的equals方法返回true,hashCode肯定相等；hashCode相等的俩个对象，equals方法返回不一定为true”

其实红色的这句说法，确实是大家普便认为的，但这种情况如果是自定义对象，只重写了equals方法，或只重写了hashCode方法，如果此种情况，结论就成了绿色的那条了。

why?

系统重写的equals方法，是判断俩个对象的属性值是否相等，如果全相等，则默认返回true,而原生的equals方法比的是引用地址值;
系统重写的hashCode方法，一般是基础数值上加上对应的属性值得到的结果，那如果俩个对象能重写的equals方法对比为true,则hashCode值也相同；而原生的hashCode值是对象内存中地位根据特定算法得到，跟内存地址有关，而重写的hashCode值已然和内存地址值无关了

所以综合上述分析：通过系统自动生成重写了equals和hashCode方法的类，通过空参构造或通过相同值的带参构造生成的不同对象，它们的equals方法返回肯定为true，hashCode也应当相同;但如果，你只重写了其中的一个方法，那结论就是我绿色标的内容

呵呵，别怪我太贫，因为一般我们有IDE，都是自动生成equals方法和hashCode方法的，所以，结论就是大家普遍认为的红色的部分，但至少里面的逻辑，你应该清楚

那么第一个问题应该结束了

问题二

判断hashCode然后再判断equals方法，主要是考虑性能。

HashSet 根据这个名字，我们可以联想到，它里面肯定用到了HashTable 哈希表相关的结构，HashTable根据索引找对象的时间复杂度为O(1),效率是很高的，比如有1000个数据的,插入一个对象，如果先调用equals方法，那就是说这1个对象要调用1000次equals方法，是不是效率很低。

所以，聪明的底层框架人员，当然选择效率高的方式，（默认一个类正常重写hashCode和equals方法情况下）hashCode不相等，equals方法肯定返回flase,但为了避免没有正常重写这个方法，又加上再次对比equals方法。

所以说，如果一个自定义类，重写hashCode方法，但未重写equals方法，当同时通过空参构造或者相同值带参构造器生成对象，然后，把这俩个对象add到HashSet中，会重复加入吗？

答案当然是。虽然第一关判断hashCode值相得，但当调用equals方法时，返回true,也会当作一个新对象加进来。

也就是说，只有同时满足hashCode相同，equals方法返回true（原生的equals方法用的是==比较，比的内存地址值）,才算是相同对象。

讲到这里，我相信有些猿肯定会有一个问题，HashSet是无序的，说是根据hashCode码存值，其实是根据散列函数来确定在hashTable中的索引，在hashTable中是有序的。
但在这里我也不再赘述，有兴趣的猿可查看本人下面的链接博文

Ted 带你学习数据结构之哈希表

想了解更深入hashCode方法和equals方法关系，可参考本人博文
重写equals()时为什么也得重写hashCode()？深度解读重写equals方法以及equals方法和hashCode方法渊源

下面我们来查看一下HashSet的源码，你会有惊讶的发现

public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;

private transient HashMap<E,Object> map;

private static final Object PRESENT = new Object(); 
// 构造器 
public HashSet() {
map = new HashMap<>();
}

public boolean add(E e) {
return map.put(e, PRESENT)==null;
} 
 
 public Iterator<E> iterator() {
    return map.keySet().iterator();
}

}

下面我把根据源码的信息，罗列出具体的梗概

HashSet是由HashMap构造出的，并且，它的每个对象是HashMap（HashMap的存储结构为key-value）的key值
HashSet中申明了一个PRESENT的常量，做为构建HashMap的value值；那么可以说，构建的每个HashMap者有相同的value值

好吧，我知道，知道这样的结果，确实有些让人惊讶，毕竟Map类它不属于Collection接口下，但确帮Collection接口制造子类，哎，不知道Collection对自己的绿帽身份，有何感想

LinkedHashSet

LinkedHashSet继承自HashSet，源码更少、更简单，唯一的区别是LinkedHashSet内部使用的是LinkHashMap。

有序，按照插入顺序
不是同步的
集合元素可以是null,但只能放入一个null
没有set和get方法只能通过迭代器取值

个人感觉，linkedHashSet没什么可讲，方法和构造上和HashSet相差无几，只是通过Link链的数据结构，使得它有了顺序。

TreeSet

TreeSet内部是通过TreeMap构造出来的
特点：

有序，按照比较器排序，并非按照插入顺序
不是同步的
集合元素可以是null,但只能放入一个null
没有set和get方法只能通过迭代器取值

注意，TreeSet里面涉及到树的概念，树结构也是一种很重要的数据结构建议有空一定研究研究，树结构也是一种很重要的数据结构

TreeSet是SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。向 TreeSet中加入的应该是同一个类的对象。
TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0

自然排序(内部比较器)
自然排序使用要排序元素的CompareTo（Object obj）方法来比较元素之间大小关系，然后将元素按照升序排列。
Java提供了一个Comparable接口，该接口里定义了一个compareTo(Object obj)方法，该方法返回一个整数值，实现了该接口的对象就可以比较大小。
obj1.compareTo(obj2)方法如果返回0，则说明被比较的两个对象相等，如果返回一个正数，则表明obj1大于obj2，如果是负数，则表明obj1小于obj2。
如果我们将两个对象的equals方法总是返回true，则这两个对象的compareTo方法返回应该返回0

定制排序（外部比较器）
自然排序是根据集合元素的大小，以升序排列，如果要定制排序，应该使用Comparator接口，实现 int compare(To1,To2)方法

如果是内部比较器的话，对象一定要实现Comparable接口，重写其compareTo()方法如果是外部比较器的话，外部比较器类一定要实现Comparator接口，重写其Compare方法

集合四课之二　Set接口下，HashSet、LinkedHashSet和TreeSet介绍与区别附带速记卡