Java Collection | Set 2 (Set)

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

谢谢你请我吃糖果:)