Java HashSet vs. TreeSet vs. LinkedHashSet

Set là một cấu trúc dữ liệu lưu trữ các phần tử không bị trùng lặp, Java đã cài đặt một số class cho cấu trúc dữ liệu này. Mỗi cách implementation đều có những đặc điểm riêng dùng cho các mục đích phù hợp khác nhau: HashSet, TreeSet và LinkedHashSet do vậy việc nắm bắt được khi nào thì sử dụng chúng một cách hiệu quả là điều cực kỳ quan trọng.

Tóm tắt một cách ngắn gọn, nếu ưu tiên về tốc độ sử dụng HashSet, nếu cần một Set được sắp xếp chọn TreeSet, còn nếu muốn đọc một Set theo thứ tự mà các phần tử được insert vào thì dùng LinkedHashSet.

• HashSet được implement bằng cách sử dụng một hash table. Các thành phần không được sắp xếp theo thứ tự. Các thao tác add, remove và contains có độ phức tạp là O(1)
• TreeSet được implement bằng cách sử dụng cấu trúc dữ liệu tree, các thành phần trong Set được sắp xếp theo thứ tự. Tuy nhiên với các thao tác add, remove và contains độ phức tạp của chúng là O(log(n)).
• LinkedHashSet được implement như một hash table với mỗi phần tử trong bảng băm này sẽ trỏ đến phần tử đầu tiên của một Linked List. Vì vậy mà các phần tử có thể được sắp xếp, và thời gian thao tác với các method cơ bản add, remove và contains là O(1).

TreeSet tree = new TreeSet();
tree.add(12);
tree.add(63);
tree.add(34);
tree.add(45);

Iterator iterator = tree.iterator();
System.out.print("Tree set data: ");
while (iterator.hasNext()) {
    System.out.print(iterator.next() + " ");
}

Output:

 Tree set data: 12 34 45 63

Bây giờ hãy define một class Dog như dưới đây:

class Dog {
int size;

public Dog(int s) {
size = s;
}

public String toString() {
return size + "";
}
}

Sau đó add vào vài phần tử:

import java.util.Iterator;
import java.util.TreeSet;

public class TestTreeSet {
public static void main(String[] args) {
TreeSet dset = new TreeSet();
dset.add(new Dog(2));
dset.add(new Dog(1));
dset.add(new Dog(3));

Iterator iterator = dset.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
}
}

Compile ok, but run-time error xảy ra.

Exception in thread "main" java.lang.ClassCastException:
collection.Dog cannot be cast to java.lang.Comparable
at java.util.TreeMap.put(Unknown Source)
at java.util.TreeSet.add(Unknown Source)
at collection.TestTreeSet.main(TestTreeSet.java:22)

Bởi vì TreeSet được sắp xếp, do đó Dog object cần phải implement interface Comparable như dưới đây:

class Dog implements Comparable{
int size;

public Dog(int s) {
size = s;
}

public String toString() {
return size + "";
}

@Override
public int compareTo(Dog o) {
        return size - o.size;
}
}

The output là:

1 2 3

HashSet Example:

HashSet dset = new HashSet();
dset.add(new Dog(2));
dset.add(new Dog(1));
dset.add(new Dog(3));
dset.add(new Dog(5));
dset.add(new Dog(4));
Iterator iterator = dset.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}

Output:

5 3 2 1 4

Note: Các phần tử ko được sắp xếp theo bất kỳ thứ tự nào

LinkedHashSet Example

LinkedHashSet dset = new LinkedHashSet();
dset.add(new Dog(2));
dset.add(new Dog(1));
dset.add(new Dog(3));
dset.add(new Dog(5));
dset.add(new Dog(4));
Iterator iterator = dset.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}

Các phần tử sẽ có thứ tự là thứ được được insert vào set

2 1 3 5 4

• Performance testing Thử test hiệu năng của 3 cách implement bằng cách sử dụn add() method.

public static void main(String[] args) {
Random r = new Random();
HashSet hashSet = new HashSet();
TreeSet treeSet = new TreeSet();
LinkedHashSet linkedSet = new LinkedHashSet();

long startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
hashSet.add(new Dog(x));
}

long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("HashSet: " + duration);

startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
treeSet.add(new Dog(x));
}

endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("TreeSet: " + duration);

startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int x = r.nextInt(1000 - 10) + 10;
linkedSet.add(new Dog(x));
}

endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("LinkedHashSet: " + duration);\
}

Kết quả cho thấy HashSet thao tác nhanh nhất với method add():

HashSet: 2244768
TreeSet: 3549314
LinkedHashSet: 2263320