Java集合（七）Set、HashSet、LinkedHashSet、TreeSet

  本系列文章：
    Java集合（一）集合框架概述
    Java集合（二）List、ArrayList、LinkedList
    Java集合（三）CopyOnWriteArrayList、Vector、Stack
    Java集合（四）Map、HashMap
    Java集合（五）LinkedHashMap、TreeMap
    Java集合（六）Hashtable、ConcurrentHashMap
    Java集合（七）Set、HashSet、LinkedHashSet、TreeSet
    Java集合（八）BlockingQueue、ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue、DelayQueue

【Set】

  List是有序集合的根接口，Set是无序集合的根接口，无序也就意味着元素不重复。更严格地说，Set集合不包含一对元素e1和e2 ，使得e1.equals(e2) ，并且最多一个空元素。
  使用Set存储的特点与List相反：元素无序、不可重复。常用的实现方式：HashSet、LinkedHashSet和TreeSet。

  当向HashSet结合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据hashCode值来决定该对象在HashSet中存储位置。简单的说，HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode()方法返回值也相等。
  LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。

  在使用Set存储数据时，为保障元素唯一性，常常要重写hashCode。重写hashCode方法时，尽量遵循以下原则：

1. 相同的对象返回相同的hashCode值。
2. 不同的对象返回不同的hashCode值，否则，就会增加冲突的概率。
3. 尽量的让hashCode值散列开（用异或运算可使结果的范围更广）。

• HashSet
    HashSet中没有重复元素，底层由HashMap实现，不保证元素的顺序(此处的没有顺序是指：元素插入的顺序与输出的顺序不一致)，HashSet允许使用Null元素，HashSet是非同步的。
• LinkedHashSet
    LinkedHashSet继承自HashSet，其底层是基于LinkedHashMap来实现的，有序，非同步。
    LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。
• TreeSet
    TreeSet底层是基于TreeMap实现的，所以元素有序。TreeSet支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。当我们构造TreeSet时，若使用不带参数的构造函数，则TreeSet的使用自然比较器；若用户需要使用自定义的比较器，则需要使用带比较器的参数。
    TreeSet是线程不安全的。
    自然排序要求元素必须实现Compareable接口，并重写里面的compareTo()方法，元素通过比较返回的int值来判断排序序列，返回0说明两个对象相同。
    比较器排序需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象，或者采用匿名内部类的方式new一个Comparator对象，重写里面的compare()方法。
    TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0。
    在使用Set存储元素时，元素虽然无放入顺序，但Set的底层实现其实是Map，元素在Set中的位置是有该元素的HashCode决定的，所以其位置其实是固定的。
    TreeSet是SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。

  至于具体使用哪种集合时，参考：

  在List和Set两个分支中，ArrayList和HashSet是对应分支中适应性最广的，两者再比较，ArrayList则适用性更广一些。也就是说如果要确定用List，但不确定用哪种List，就可以使用ArrayList；如果确定用Set，但不确定用哪种Set，就可以使用HashSet。如果只知道用集合，就用ArrayList。

【HashSet】

一、HashSet介绍

  HashSet是一个无序集合，其底层结构是HashMap，简单来说，HashSet是value是固定值（Object PRESENT = new Object()）的HashMap。

1.2 HashSet的特点*

• 1、HashSet的底层实现是HashMap（HashSet的值存放于HashMap的key上，HashMap的value是一个统一的值）。
• 2、HashSet中的元素无序且不能重复（从插入HashSet元素的顺序和遍历HashSet的顺序对比可以看出：遍历顺序和存入到Set的顺序并不一致）。
• 3、HashSet是线程不安全的。如果要保证线程安全，其中一种方法是将其改造成线程安全的类，示例：

	Set set = Collections.synchronizedSet(new HashSet(...));
1

• 4、HashSet允许存入null。

• HashSet如何检查重复
    当你把对象加入HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与Set中其他元素的hashcode值作比较，如果没有相同的hashcode，HashSet会假设对象没有重复出现。
    如果发现有相同hashcode值的对象，这时会调用equals方法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不再存储该元素。
    hashCode()与 equals()的相关规定：

  1）如果两个对象相等，则hashcode一定也是相同的；
  2）两个对象相等，对两个equals方法返回true；
  3）两个对象有相同的hashcode值，它们也不一定是相等的；
  4）如果equals方法被覆盖过，则hashCode方法也必须被覆盖；
  5）hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该 class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

1.2 HashSet常的使用

• 1、构造方法

	//默认初始容量为16，负载因子为0.75
	public HashSet()
	//指定初始容量，负载因子为0.75
	public HashSet(int initialCapacity)
	//指定初始容量和负载因子
	public HashSet(int initialCapacity, float loadFactor)
1
2
3
4
5
6

• 2、添加元素

	public boolean add(E e)
1

• 3、删除元素

	public boolean remove(Object o)
1

• 4、判断是否包含某元素

	public boolean contains(Object o)
1

• 5、其他方法

	//清空集合
	public void clear()
	//判断Set是否为空
	public boolean isEmpty()	
	//获取迭代器
	public Iterator<E> iterator()	
	//返回此集合中的元素数
	public int size()	
1
2
3
4
5
6
7
8

二、从源码理解HashSet

  由于HashSet的底层实现HashMap，所以其方法的实现基本都是对HashMap的操作。
  变量：

    //HashSet集合中的内容是通过HashMap数据结构来存储的
    private transient HashMap<E,Object> map;
    //向HashSet中添加数据，数据在上面的map结构是作为key存在的，而value统一都是
    //PRESENT，这样做是因为Set只使用到了HashMap的key，所以此处定义一个静态的常
    //量Object类，来充当HashMap的value
    private static final Object PRESENT = new Object();
1
2
3
4
5
6

2.1 创建HashSet对象

    //直接 new 一个HashMap对象出来，采用无参的 HashMap 构造函数，
    //HashMap对象具有默认初始容量（16）和加载因子（0.75）
    public HashSet() {
        map = new HashMap<>();
    }

	//指定初始容量和加载因子，创建HashMap实例
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

	//指定初始容量，创建HashMap
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 特殊的构造方法

	//以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。 
    //此构造函数为包访问权限，不对外公开，实际只是对LinkedHashSet的支持。 
    //底层会以指定的参数构造一个空LinkedHashMap实例来实现。 
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
1
2
3
4
5
6

  加载因子指的是能存储的元素占总的容量的比例。在HashMap中，能够存储元素的数量就是：总的容量*加载因子 。每当向HashSet新增元素时，如果HashMap集合中的元素大于总的容量*加载因子 ，就必须要进行扩容操作。

3.2 添加元素

  当把对象加入HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调用equals方法来检查hashcode相等的对象是否真的相同。如果两者相同，则覆盖旧元素。

	//将 e 作为 key，PRESENT 作为 value 插入到 map 集合中，如果 e 
	//不存在，则插入成功返回 true;如果存在，则返回false
	//本质上是调用HashMap的put方法来实现的
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
1
2
3
4
5
6

2.3 删除元素

	//删除成功返回 true，删除的元素不存在会返回 false
	//本质上是调用HashMap的remove方法来实现的
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
1
2
3
4
5

2.4 查找元素

	//调用 HashMap 的 containsKey(Object o) 方法，找到了返回 true，找不到返回 false
	//因为HashSet的本质上是用HashMap来存储元素的，HashSet的值是HashMap中的key，所以
	//此处调用了HashMap的containsKey方法来判断
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
1
2
3
4
5
6

2.5 常规方法

  这几个方法都是直接调用其底层实现HashMap的方法的：

	//清空集合
    public void clear() {
        map.clear();
    }
	//判断是否为空
    public boolean isEmpty() {
        return map.isEmpty();
    }
	//获取集合元素个数
    public int size() {
        return map.size();
    }
1
2
3
4
5
6
7
8
9
10
11
12

2.6 迭代器

  因为HashSet的本质上是用HashMap来存储元素的，HashSet的值是HashMap中的key，所以此处调用了HashMap的keySet方法来遍历HashSet中的元素。

    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }
1
2
3

【LinkedHashSet】

一、LinkedHashSet介绍

  LinkedHashSet是有序集合，其底层是通过LinkedHashMap来实现的，LinkedHashMap其实也就是value是固定值的LinkedHashMap。因此LinkedHashSet中的元素顺序是可以保证的，也就是说遍历序和插入序是一致的。
  LinkedHashSet继承了HashSet。

1.1 LinkedHashSet的特点*

  1）底层是用LinkedHashMap来实现的。
  2）线程不安全 。
  3）元素有序，是按照插入的顺序排序的。
  4）最多只能存一个null。

• LinkedHashSet支持按元素访问顺序排序吗
    LinkedHashSet所有的构造方法都是调用HashSet的同一个构造方法：

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }
1
2
3
4
5
6
7
8

  可以看出：这里把accessOrder写死为false。所以，LinkedHashSet是不支持按访问顺序对元素排序的，只能按插入顺序排序。

1.2 LinkedHashSet的使用

  由于LinkedHashSet继承了HashSet，自身没什么特殊的实现方法。构造方法：

	//初始容量（16）和负载因子（0.75）
	public LinkedHashSet()
	//指定初始容量和默认负载因子（0.75）
	public HashSet(int initialCapacity)
	//指定初始容量和负载因子
	public HashSet(int initialCapacity, float loadFactor)
1
2
3
4
5
6

二、从源码理解LinkedHashSet

  LinkedHashSet源码很简单，功能基本都来自其父类HashSet的实现，其构造方法：

    public LinkedHashSet(int initialCapacity, float loadFactor) {
    	//调用其父类HashSet的构造器，指定初始容量和增长因子，构造一个LinkedHashMap
        super(initialCapacity, loadFactor, true);
    }

    public LinkedHashSet(int initialCapacity) {
    	//调用其父类HashSet的构造器，指定初始容量，增长因子为0.75，构造一个LinkedHashMap
        super(initialCapacity, .75f, true);
    }

    public LinkedHashSet() {
    	//调用其父类HashSet的构造器，初始容量为16，增长因子为0.75，构造一个LinkedHashMap
        super(16, .75f, true);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

【TreeSet】

一、TreeSet介绍

  TreeSet是一个有序集合，基于TreeMap实现。

1.1 TreeSet特点*

• 1、TreeSet支持元素的自然排序和按照在创建时指定的Comparator比较器进行排序
    TreeSet是使用二叉树的原理对新增的对象按照指定的顺序排序，每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。
    TreeSet中要存储自定义类的对象时， 自己定义的类必须实现Comparable接口，并且覆写相应的compareTo()函数，才可以正常使用。
    Integer和String对象都可以进行默认的TreeSet排序，而自定义类的对象是不可以的。自己定义的类必须实现Comparable接口，并且覆写相应的compareTo()函数，才可以正常使用。
    在重写compare()函数时，要返回相应的值才能使 TreeSet 按照一定的规则来排序。比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。示例：

@Data
public class student  implements Comparable<student>{
    private String name;
    private int age;

    @Override
    public int compareTo(student s) {
        // 主要条件：按照年龄从小到大
        int num = this.age - s.age;
        //次要条件：年龄相同时，按照姓名的字母顺序排序
        int num2 = num == 0 ? this.name.compareTo(s.name) : num;
        return num2;
    }
}

public class Comparabledemo {
    public static void main(String[] args) {
        TreeSet<student> tree = new TreeSet<student>();
        student s1 = new student("wuer",27);
        student s2 = new student("weuers",250);
        tree.add(s1);
        tree.add(s2);
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 2、TreeSet的基本操作（add、remove 和 contains）的时间复杂度是log(n) 。
• 3、TreeSet是非线程安全的。
• 4、TreeSet的迭代器是fail-fast策略的。
• 5、TreeSet中元素不允许为null，不允许重复值。

1.2 TreeSet的使用

• 1、构造方法

	//创建一个空的 TreeSet，使用自然排序
	public TreeSet()
	//指定比较器，如果比较器是 null 将使用自然排序
	public TreeSet(Comparator<? super E> comparator)
1
2
3
4

• 2、添加元素

	//添加一个元素
	public boolean add(E e)
	//添加集合中的元素
	public  boolean addAll(Collection<? extends E> c)
1
2
3
4

• 3、删除元素

    public boolean remove(Object o)
1

• 4、判断是否包含某元素

	public boolean contains(Object o)
1

• 5、获取特殊元素

	//返回此TreeSet中存在的最大元素
    public E last() 
	//返回此TreeSet中存在的最小元素
    public E first()
	//返回在这个集合中小于或者等于给定元素的最大元素
    public E floor(E e)
	//返回在这个集合中大于或者等于给定元素的最小元素
    public E ceiling(E e)
   	//返回此集合中大于某个元素的最小的元素
    public E higher(E e) 
	//返回此集合中小于某个元素的最大的元素
    public E lower(E e)    
1
2
3
4
5
6
7
8
9
10
11
12

• 6、删除

	//检索和删除最小（第一个）元素
    public E pollFirst()
	//检索和删除最大（最后）元素
    public E pollLast()
1
2
3
4

• 7、其他方法

	//获取TreeSet元素个数
    public int size()
	//判断TreeSet是否为空
    public boolean isEmpty()
	//清空TreeSet
    public void clear()
1
2
3
4
5
6

二、从源码理解TreeSet

  NavigableMap是一个扩展的SortedMap，在继承SortedMap接口的基础之上，扩展了一些返回了给定搜索目标的最接近匹配项的方法。

	//存储数据的底层数据结构
    private transient NavigableMap<E,Object> m;
    //由于 TreeSet 只需要使用 Key 进行存储，因此 Value 存储的是一个虚拟值
    private static final Object PRESENT = new Object();
1
2
3
4

2.1 创建TreeSet对象

    //使用 TreeMap 创建一个空的 TreeSet，使用自然排序，
    //添加的元素需要实现 Comparable 接口，即是可比较的
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

    //指定比较器，如果比较器是 null 将使用自然排序
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }

    //构建一个treeSet，包含参数c中的元素，排序是基于元素的自然顺序
    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.2 添加元素

  调用TreeMap中的put()方法进行添加元素。

    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
1
2
3

2.3 删除元素

  调用TreeMap中的remove()方法来删除TreeSet中的元素，若set中存在要删除的元素，删除，返回true，不存在，返回false。内部调用navigableMap的remove方法，因为treeMap是其实现类，所以实际执行的时候，调用的是TreeMap的remove方法。

    public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }
1
2
3

  删除特定位置的元素。

	//检索和删除最小（第一个）元素
    public E pollFirst() {
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();
    }
    
	//检索和删除最大（最后）元素
    public E pollLast() {
        Map.Entry<E,?> e = m.pollLastEntry();
        return (e == null) ? null : e.getKey();
    }
1
2
3
4
5
6
7
8
9
10
11

2.4 判断是否包含某元素

   若TreeSet中存在该元素，返回true，不存在，返回false。

    public boolean contains(Object o) {
        return m.containsKey(o);
    }
1
2
3

2.5 获取特定元素

	//返回此TreeSet中存在的最大元素
    public E last() {
        return m.lastKey();
    }
	//返回此TreeSet中存在的最小元素
    public E first() {
        return m.firstKey();
    } 
1
2
3
4
5
6
7
8

• 1、返回此集合中小于某个元素的最大的元素
    返回此集合中最大的元素，该元素严格小于给定的元素。如果此TreeSet集合中不存在这样的元素，则此方法返回Null。

    public E lower(E e) {
        return m.lowerKey(e);
    }
1
2
3

• 2、返回此集合中大于某个元素的最小的元素
    从集合中返回指定元素中最接近的最大元素，如果没有，则返回Null。

    public E higher(E e) {
        return m.higherKey(e);
    }
1
2
3

• 3、floor/ceiling
    floor(E e)方法返回在这个集合中小于或者等于给定元素的最大元素，如果不存在这样的元素，返回null。
    ceiling(E e)方法返回在这个集合中大于或者等于给定元素的最小元素，如果不存在这样的元素，返回null。

    public E floor(E e) {
        return m.floorKey(e);
    }

    public E ceiling(E e) {
        return m.ceilingKey(e);
    }
1
2
3
4
5
6
7