This blog mainly explains the three implementation classes of the Set interface HashSet, LinkedHashSet, TreeSet and the differences between them.
Note: The code in this article uses JDK version 1.8.0_191
1. Use HashSet
HashSet is the most commonly used implementation class of the Set interface. The underlying data structure is a hash table.
private transient HashMap<E,Object> map;
Copy the codeThe code declaration for the HashSet class looks like this:
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable.java.io.Serializable
{... }Copy the code1.1 Adding Elements
Add elements using HashSet as follows:
HashSet<String> platformSet = new HashSet<>();
// Add elements
System.out.println(platformSet.add(Blog Park));
System.out.println(platformSet.add("Nuggets"));
System.out.println(platformSet.add("Wechat Official Account"));
// Add a duplicate element, it will not succeed, because Set does not allow duplicate elements
// Instead of reporting an error, the code returns false, that is, adding failed
System.out.println(platformSet.add(Blog Park));
System.out.println(platformSet.add("Nuggets"));
Copy the codeThe output from the above code run is:
true
true
true
false
false
Debugging code will also find that the platformSet has only three elements:
Of note, platformset.add (3, “Personal blog “); This code generates a compilation error because there is only one way to add elements to a Set, rather than two overloads like the List interface explained in the previous blog post.
1.2 Obtaining Elements
Unlike the List interface, the Set interface has no methods to get elements.
1.3 Obtaining the number of set elements
Get the number of HashSet elements as follows:
System.out.println("The number of platformSet elements is:" + platformSet.size());
Copy the code1.4 Deleting Elements
Note that there is also only 1 method to delete elements using HashSet, unlike ArrayList, which has 2 overloads:
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
Copy the codeThe usage method is as follows:
// Remove the nonexistent element "personal blog ", return false
System.out.println(platformSet.remove("Personal Blog"));
// Delete the existing element "wechat official number ", return true
System.out.println(platformSet.remove("Wechat Official Account"));
Copy the code1.5 Modifying Elements
Unlike the List interface, the Set interface has no methods to modify elements.
1.6 Check whether the set is empty
To determine whether a HashSet is empty, use the following method:
System.out.println("isEmpty:" + platformSet.isEmpty());
Copy the code1.7 Traverse elements (Often asked in interviews)
There are two main ways to traverse a HashSet element:
- Iterator traversal
- The foreach loop
The usage method is as follows:
System.out.println("Use Iterator to iterate:");
Iterator<String> platformIterator = platformSet.iterator();
while (platformIterator.hasNext()) {
System.out.println(platformIterator.next());
}
System.out.println();
System.out.println("Traversal with foreach:");
for (String platform : platformSet) {
System.out.println(platform);
}
Copy the code1.8 Clearing collections
Emptying all elements in a HashSet is as follows:
platformSet.clear();
Copy the code1.9 Complete sample code
The complete code for the points explained above is as follows:
package collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class SetTest {
public static void main(String[] args) {
Set<String> platformSet = new HashSet<>();
// Add elements
System.out.println(platformSet.add(Blog Park));
System.out.println(platformSet.add("Nuggets"));
System.out.println(platformSet.add("Wechat Official Account"));
// Add a duplicate element, it will not succeed, because Set does not allow duplicate elements
// Instead of reporting an error, the code returns false, that is, adding failed
System.out.println(platformSet.add(Blog Park));
System.out.println(platformSet.add("Nuggets"));
System.out.println("The number of platformSet elements is:" + platformSet.size());
// Remove the nonexistent element "personal blog ", return false
System.out.println(platformSet.remove("Personal Blog"));
// Delete the existing element "wechat official number ", return true
System.out.println(platformSet.remove("Wechat Official Account"));
System.out.println("The number of platformSet elements is:" + platformSet.size());
System.out.println("isEmpty:" + platformSet.isEmpty());
System.out.println("Use Iterator to iterate:");
Iterator<String> platformIterator = platformSet.iterator();
while (platformIterator.hasNext()) {
System.out.println(platformIterator.next());
}
System.out.println();
System.out.println("Traversal with foreach:");
for (String platform : platformSet) {
System.out.println(platform);
}
System.out.println();
platformSet.clear();
System.out.println("isEmpty:"+ platformSet.isEmpty()); }}Copy the codeThe output is:
true
true
true
false
false
The number of elements in a platformSet is 3
false
true
The number of elements in a platformSet is 2
isEmpty:false
Iterator Iterator:
Blog garden
The Denver nuggets
Using foreach to traverse:
Blog garden
The Denver nuggets
isEmpty:true
2. LinkedHashSet use
LinkedHashSet is also the implementation class of the Set interface. The underlying data structure is a linked list and a hash table. The hash table is used to ensure the uniqueness of elements, and the linked list is used to ensure the insertion order of elements, namely FIFO(First Input, First Output, First in, First out).
The code declaration for the LinkedHashSet class looks like this:
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable.java.io.Serializable {{}Copy the codeAs you can also see from the above code, the LinkedHashSet class inherits from the HashSet class.
The LinkedHashSet class is used in much the same way as HashSet, just by modifying the declaration code:
Set<String> platformSet = new LinkedHashSet<>();
Copy the code3. Use TreeSet
TreeSet is also the implementation class of Set interface. The underlying data structure is a red-black tree. TreeSet not only guarantees the uniqueness of elements, but also ensures the order of elements.
The code declaration for the TreeSet class looks like this:
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable.java.io.Serializable
{}Copy the codeThe TreeSet class is used in much the same way as a HashSet, just by modifying the code in the declaration:
Set<String> platformSet = new TreeSet<>();
Copy the code4. The difference between a HashSet, a LinkedHashSet, and a TreeSet
HashSet, LinkedHashSet, TreeSet are three implementation classes that implement the Set interface.
A HashSet is just a generic collection of stored data,
The main function of LinkedHashSet is to ensure that FIFO(first in, first out) is an ordered set,
TreeSet’s main functionality is sorting (natural or comparator sorting)
4.1 similarities
1)HashSet, LinkedHashSet, TreeSet all implement the Set interface
2) All three guarantee the uniqueness of elements, that is, elements are not allowed to repeat
3) None of them are thread-safe
You can use the Collections. SynchronizedSet () method to ensure the safety of the thread
4.2 the difference between
2 the sorting
A HashSet does not guarantee the order of elements
LinkHashSet guarantees that the FIFO is sorted by insertion order
TreeSet guarantees the order of elements and supports custom collations
Empty words without proof, on the code to see the effect:
HashSet<String> hashSet = new HashSet<>();
LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
TreeSet<String> treeSet = new TreeSet<>();
String[] letterArray = new String[]{"B"."A"."D"."C"."E"};
for (String letter : letterArray) {
hashSet.add(letter);
linkedHashSet.add(letter);
treeSet.add(letter);
}
System.out.println("HashSet(I don't guarantee order):" + hashSet);
System.out.println("LinkedHashSet(I guarantee the order in which elements are inserted):" + linkedHashSet);
System.out.println("TreeSet(I guarantee the order of elements by sorting rules):" + treeSet);
Copy the codeThe output of the above code is:
HashSet(I don’t guarantee order):[A, B, C, D, E]
LinkedHashSet(I guarantee the order in which elements are inserted):[B, A, D, C, E]
TreeSet(I guarantee the order of elements by sorting rules):[A, B, C, D, E]
4.2.2 null values
HashSet, LinkedHashSet allow null values, TreeSet doesn’t allow null values, add null thrown when the Java. Lang. NullPointerException.
Set<String> platformSet = new TreeSet<>();
platformSet.add(null);
Copy the codeRun the above code and the following error message is displayed:
Holdings performance
In theory, adding the same number of elements is the fastest for a HashSet, followed by a LinkedHashSet, and the slowest for a TreeSet (because of internal sorting).
Create a new Employee class and create a custom sorting rule:
package collection;
public class Employee implements Comparable<Employee> {
private Integer employeeNo;
public Employee(Integer employeeNo) {
this.employeeNo = employeeNo;
}
public Integer getEmployeeNo(a) {
return employeeNo;
}
public void setEmployeeNo(Integer employeeNo) {
this.employeeNo = employeeNo;
}
@Override
public int compareTo(Employee o) {
return this.employeeNo - o.employeeNo; }}Copy the codeThen add the following validation code to add 10000 elements to HashSet, LinkedHashSet, and TreeSet:
Random random = new Random();
HashSet<Employee> hashSet = new HashSet<>();
LinkedHashSet<Employee> linkedHashSet = new LinkedHashSet<>();
TreeSet<Employee> treeSet = new TreeSet<>();
int maxNo = 10000;
long startTime = System.nanoTime();
for (int i = 0; i < maxNo; i++) {
int randomNo = random.nextInt(maxNo - 10) + 10;
hashSet.add(new Employee(randomNo));
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("HashSet time:" + duration);
startTime = System.nanoTime();
for (int i = 0; i < maxNo; i++) {
int randomNo = random.nextInt(maxNo - 10) + 10;
linkedHashSet.add(new Employee(randomNo));
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedHashSet: take" + duration);
startTime = System.nanoTime();
for (int i = 0; i < maxNo; i++) {
int randomNo = random.nextInt(maxNo - 10) + 10;
treeSet.add(new Employee(randomNo));
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("TreeSet time:" + duration);
Copy the codeFirst run, output:
HashSet Duration: 6203357
LinkedHashSet: 5246129
TreeSet time: 7813460
Second run, output result:
HashSet Time: 9726115
LinkedHashSet: 5521640
TreeSet time: 6884474
For the third run, the output is as follows:
HashSet time: 7263940
LinkedHashSet: 6156487
TreeSet time: 8554666
Fourth run, output:
HashSet time: 6140263
LinkedHashSet: 4643429
TreeSet time: 7804146
For the fifth run, the output is as follows:
HashSet Time: 7913810
LinkedHashSet: 5847025
TreeSet time: 8511402
TreeSet takes the most time, as you can see from the five runs, but LinkedHashSet takes less time each time than HashSet,
This contradicts HashSet is the fastest, so here’s the question: which is faster, HashSet or LinkedHashSet?
What do you think of this problem, please leave a comment.
5. Two ways to sort TreeSet
Let’s review the code above using TreeSet sorting:
TreeSet<String> treeSet = new TreeSet<>();
String[] letterArray = new String[]{"B"."A"."D"."C"."E"};
for (String letter : letterArray) {
treeSet.add(letter);
}
System.out.println("TreeSet(I guarantee the order of elements by sorting rules):" + treeSet);
Copy the codeOur order insert element is “B”, “A”, “D”, “C”, “E”, but the order of the output element is “A”, “B”, “C”, “D”, “E”, proved the TreeSet’ve been according to the internal rules of order.
So what’s the sort of element we put into TreeSet if it’s our custom reference type?
With that in mind, create a new Student class like this:
package collection;
public class Student {
private String name;
private int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName(a) {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge(a) {
return age;
}
public void setAge(int age) {
this.age = age; }}Copy the codeThen add the following validation code:
TreeSet<Student> studentTreeSet = new TreeSet<>();
Student student1 = new Student("zhangsan".20);
Student student2 = new Student("lisi".22);
Student student3 = new Student("wangwu".24);
Student student4 = new Student("zhaoliu".26);
Student student5 = new Student("zhangsan".22);
studentTreeSet.add(student1);
studentTreeSet.add(student2);
studentTreeSet.add(student3);
studentTreeSet.add(student4);
studentTreeSet.add(student5);
for (Student student : studentTreeSet) {
System.out.println("name:" + student.getName() + ",age:" + student.getAge());
}
Copy the codeRun the code to see the effect, only to find the following error:
Why is that?
This is because we haven’t defined any sort rules for the Student class, and TreeSet said, “I don’t know how to sort this, so I’ll throw an exception.”
How do you solve it? There are two ways:
- Natural ordering
- Comparator sort
5.1 Natural Sorting
Natural sorting is implemented by having the Student class implement the interface Comparable and rewrite the interface’s method compareTo, which defines the sorting rules.
The default compareTo method generated using the IDEA shortcut keys looks like this:
@Override
public int compareTo(Student o) {
return 0;
}
Copy the codeThis method is executed when the add() method is used to add elements to determine their location.
If 0 is returned, the two elements are the same and only the first element is retained
If the return value is greater than 0, the element is placed after the specified element O in the argument
If the return value is less than 0, the element is placed before the specified element O in the argument
So if you run the validation code without making any changes to the compareTo() method, you’ll find only one element in the collection:
name:zhangsan,age:20
Then change the logic of the compareTo() method to:
@Override
public int compareTo(Student o) {
// The collation rules are described as follows
// The names are sorted by length, with short names in the front and long names in the back
// If the names are of the same length, compare strings in lexicographical order
// If the names are exactly the same, the younger ones go first and the older ones go second
int orderByNameLength = this.name.length() - o.name.length();
int orderByName = orderByNameLength == 0 ? this.name.compareTo(o.name) : orderByNameLength;
int orderByAge = orderByName == 0 ? this.age - o.age : orderByName;
return orderByAge;
}
Copy the codeRun the validation code again, and the output looks like this:
name:lisi,age:22
name:wangwu,age:24
name:zhaoliu,age:26
name:zhangsan,age:20
name:zhangsan,age:22
5.2 Comparator Sorting
Comparator sorting is implemented by creating a new Comparator class that inherits the interface Comparator and overrides the interface’s Compare() method.
Note: To use this approach, the Student class does not need to implement the interface Comparable, let alone override the interface’s method compareTo.
package collection;
import java.util.Comparator;
public class StudentComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
// The collation rules are described as follows
// The names are sorted by length, with short names in the front and long names in the back
// If the names are of the same length, compare strings in lexicographical order
// If the names are exactly the same, the younger ones go first and the older ones go second
int orderByNameLength = o1.getName().length() - o2.getName().length();
int orderByName = orderByNameLength == 0 ? o1.getName().compareTo(o2.getName()) : orderByNameLength;
int orderByAge = orderByName == 0 ? o1.getAge() - o2.getAge() : orderByName;
returnorderByAge; }}Copy the codeStudentTreeSet = studentTreeSet = studentTreeSet = studentTreeSet = studentTreeSet
TreeSet<Student> studentTreeSet = new TreeSet<>(new StudentComparator());
Copy the codeThe output is exactly the same as with natural sorting.
6. Source code and reference
List,Set, Map, etc.