Java Collection | Set 2 (Set)

Posted on | | Visitors

Set 接口继承于 Collection 接口，它类似于数学中集合的概念，元素是无序的且不允许重复。除了最基础的添加，删除，修改元素等操作以外，Set 还可以求 Union, Intersection, Difference.
Set
Image Source

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;
public class SetDemo{
    public static void main(String[] args){
	Set<String> set1 = new HashSet<String>();
	set1.add("Future");
	set1.add("Googler");
	set1.add("Microsoft");
	set1.add("Future");
	// Notice that we add "Future" twice, but the result only contains one
	System.out.println(set1);   // [Googler, Future, Microsoft]
	// TreeSet will sort the input
	Set<String> set2 = new TreeSet<String>(set1);
	System.out.println(set2);   // [Future, Googler, Microsoft]
	// Java code for union, intersection and difference on Set
	Set<Integer> a = new HashSet<Integer>();
	a.addAll(Arrays.asList(new Integer[] {1, 3, 2, 4, 8, 9, 0}));
	Set<Integer> b = new HashSet<Integer>();
        b.addAll(Arrays.asList(new Integer[] {1, 3, 7, 5, 4, 0, 7, 5}));
        // Union
        Set<Integer> union = new HashSet<Integer>(a);
        union.addAll(b);
        System.out.println("The union of two sets: " + union);  // [0, 1, 2, 3, 4, 5, 7, 8, 9]
        // Intersection
        Set<Integer> intersection = new HashSet<Integer>(a);
        intersection.retainAll(b);
        System.out.println("Thhe intersection of two sets: " + intersection);  // [0, 1, 3, 4]
        // Difference
        Set<Integer> difference = new HashSet<Integer>(a);
        difference.removeAll(b);
        System.out.println("The difference of two sets: " + difference);   // [2, 8, 9]
    }
}

Set 接口主要有这些实现类：HashSet, LinkedSet, TreeSet (sorted), EnumSet 下面我们来一一分析

HashSet

HashSet 有如下几个特点：

  1. 不允许重复元素
  2. 插入元素时并不按照插入的先后顺序排列，而按照 hash code 排
  3. null 允许存在于 HashSet 中
  4. 底层运用的是 Hashtable 算法

HashSet 中有这么几个构造器

1
2
3
4
5
6
7
8
9
10
11
HashSet()
/*Constructs a new, empty set; the backing HashMap instance has default initial capacity (16) and load factor (0.75).*/
HashSet(Collection<? extends E> c)
/*Constructs a new set containing the elements in the specified collection.*/
HashSet(int initialCapacity)
/*Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and default load factor (0.75).*/
HashSet(int initialCapacity, float loadFactor)
/*Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and the specified load factor.*/

Source: Oracle 官方文档

如果不传参数，default 容量为16，load factor 为0.75. 即当 HashSet 中有 16 * 0.75 ＝ 12 个元素时，底层的算法会使容量翻倍。当然，HashSet 也提供了一个构造器让用户自定义 default capacity 和 load factor.

HashSet 常用方法有 add(), remove(), contains(), clear(), iterator()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.*;
public class HashSetDemo{
    public static void main(String[] args){
	HashSet<String> h = new HashSet<String>();
	h.add("Nirvana");
	h.add("David Bowei");
	h.add("Radiohead");
	h.add("R.E.M");
	System.out.println(h);   // [R.E.M, Nirvana, David Bowei, Radiohead]
	System.out.println(h.contains("Nirvana"));  // true
	h.remove("Radiohead");
	System.out.println(h.contains("Radiohead"));   // false
	System.out.println("Interating over list: ");
	Iterator<String> i = h.iterator();    // R.E.M
	while (i.hasNext()){                  // Nirvana
	    System.out.println(i.next());     // David Bowei
	}
	h.clear();
	System.out.println(h);  // []
    }
}

LinkedHashSet

LinkedHashSet 是 HashSet 的 ordered 版本，向其中添加的元素都是有先后顺序的。它底层使用 Doubly Linked List 来组织 HashSet。它实现了 Set 接口且继承于 HashSet 类。

代码示例如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;
public class LinkedHashSetDemo{
    public static void main(String[] args){
	LinkedHashSet<String> l = new LinkedHashSet<String>();
	l.add("Guns N' Roses");
	l.add("Placebo");
	l.add("Oasis");
	l.add("Blur");
	l.add("Blur");   // will not add this one cause it's already exist
	System.out.println("Size of list: " + l.size());   // 4
	System.out.println(l);   // [Guns N' Roses, Placebo, Oasis, Blur]
	System.out.println("Removing Blur from list: " + l.remove("Blur"));  // true
	System.out.println("Removing element that is not exist: " + l.remove("Pulp")); // false
	System.out.println("If the list contains Oasis: " + l.contains("Oasis"));  // true
	System.out.println(l);   //[Guns N' Roses, Placebo, Oasis]
    }
}

TreeSet

TreeSet 有如下特点：

  1. TreeSet 实现了 NavigableSet，NavigableSet 又继承了 SortedSet
  2. 不允许重复元素
  3. 元素不以添加先后顺序排列，而是按照 key 排序
  4. TreeSet 不允许添加不同 class 的对象

  5. TreeSet 允许添加 null， 但有且仅有一次

    构造器有这么几种

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    TreeSet()
    /*Constructs a new, empty tree set, sorted according to the natural ordering of its elements.*/
    TreeSet(Collection<? extends E> c)
    /*Constructs a new tree set containing the elements in the specified collection, sorted according to the natural ordering of its elements.*/
    TreeSet(Comparator<? super E> comparator)
    /*Constructs a new, empty tree set, sorted according to the specified comparator.*/
    TreeSet(SortedSet<E> s)
    /*Constructs a new tree set containing the same elements and using the same ordering as the specified sorted set.*/

Source：Oracle 官方文档

针对 TreeSet 有如下操作

向其中添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
public class TreeSetDemo{
    public static void main(String[] args){
	TreeSet t = new TreeSet();
	t.add("Alice in Chains");
	t.add("New Order");
	t.add("The Cure");
	t.add("Suede");
	t.add("The Cure");  // Duplicates will not get insert
	System.out.println(t);
	// [Alice in Chains, New Order, Suede, The Cure]
    }
}

向其中添加 null

1
2
3
4
5
6
7
8
9
10
11
import java.util.*;
public class TreeSetDemo{
    public static void main(String[] args){
	TreeSet t = new TreeSet();
	t.add("Alice in Chains");
	t.add("New Order");
	t.add("The Cure");
	t.add(null);   // Throw NullPointerException
    }
}

如果 TreeSet 中已经有了元素，再试图向其中添加 null 时，编译器会报错 Throw NullPointerException

1
2
3
4
Exception in thread "main" java.lang.NullPointerException
	at java.util.TreeMap.put(TreeMap.java:563)
	at java.util.TreeSet.add(TreeSet.java:255)
	at TreeSetDemo.main(TreeSetDemo.java:9)

因为每次向 TreeSet 中添加元素，它都会与已经存在的元素比较，看它们是否是一类 class，如果向其中添加 null, 而 null 不属于任何一个 class，所以会报错

正确的做法是第一个就添加 null, 但此后就不能添加任何其他元素了

1
2
3
4
5
6
7
8
9
import java.util.*;
public class TreeSetDemo{
    public static void main(String[] args){
	TreeSet t = new TreeSet();
	t.add(null);
	t.add("Alice in Chains");  // Throw NullPointerException
    }
}

TreeSet 常用操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;
public class TreeSetDemo{
    public static void main(String[] args){
	ArrayList list = new ArrayList();
	list.add("New Order");
	list.add("Alice in Chains");
	list.add("The Cure");
	list.add("Suede");
	// Creating a TreeSet object from ArrayList
	TreeSet t = new TreeSet(list);  
	System.out.println(t);  // [Alice in Chains, New Order, Suede, The Cure]
	System.out.println(t.first());   // Alice in Chains
	System.out.println(t.last());   // The Cure
	// Elements less than O
	System.out.println(t.headSet("O"));   // [Alice in Chains, New Order]
	// Elements greater than or equal to G.
	System.out.println(t.tailSet("G"));  // [New Order, Suede, The Cure]
	// Elements ranging from C to P
	System.out.println(t.subSet("C", "P"));  // [New Order]
	t.clear();
	System.out.println(t);   //  []
    }
}

关于 Set 接口及其实现类的讨论就到这里
以上内容如有疏漏或不足之处，欢迎与我讨论
邮箱：entropy714@gmail.com
微信：cobain0714

谢谢你请我吃糖果：）