HashSet frente a TreeSet frente a LinkedHashSet

Un conjunto no contiene elementos duplicados. Esa es una de las principales razones para utilizar un conjunto. Hay 3 implementaciones de Set de uso común: HashSet, TreeSet y LinkedHashSet. Cuándo y cuál usar es una pregunta importante. En resumen, si necesita un conjunto rápido, debe usar HashSet; si necesita un conjunto ordenado, entonces se debe utilizar TreeSet; Si necesita un conjunto que pueda almacenar la orden de inserción, debe usar LinkedHashSet.

1. Configurar interfaz

Colocar la interfaz se extiende Colección interfaz. En un conjunto, no se permiten duplicados. Cada elemento de un conjunto debe ser único. Simplemente puede agregar elementos a un conjunto y los duplicados se eliminarán automáticamente.

2. HashSet frente a TreeSet frente a LinkedHashSet

HashSet se implementa mediante una tabla hash. Los elementos no están ordenados. La agregar, retirar, y contiene Los métodos tienen una complejidad de tiempo constante O (1).

TreeSet se implementa utilizando una estructura de árbol (árbol rojo-negro en el libro de algoritmos). Los elementos de un conjunto están ordenados, pero el agregar, retirar, y contiene métodos tiene una complejidad de tiempo de O (log (n)). Ofrece varios métodos para lidiar con el conjunto ordenado como first (), last (), headSet (), tailSet (), etc.

LinkedHashSet está entre HashSet y TreeSet. Se implementa como una tabla hash con una lista vinculada que la atraviesa, por lo que proporciona el orden de inserción. La complejidad temporal de los métodos básicos es O (1).

3. Ejemplo de conjunto de árbol

TreeSet<Integer> tree = new TreeSet<Integer>();
tree.add(12);
tree.add(63);
tree.add(34);
tree.add(45);
 
Iterator<Integer> iterator = tree.iterator();
System.out.print("Tree set data: ");
while (iterator.hasNext()) {
    System.out.print(iterator.next() + " ");
}

La salida se ordena de la siguiente manera:

Tree set data: 12 34 45 63 

Ahora definamos una clase de perro de la siguiente manera:

class Dog {
	int size;
 
	public Dog(int s) {
		size = s;
	}
 
	public String toString() {
		return size + "";
	}
}

Agreguemos algunos perros a TreeSet como los siguientes:

import java.util.Iterator;
import java.util.TreeSet;
 
public class TestTreeSet {
	public static void main(String[] args) {
		TreeSet<Dog> dset = new TreeSet<Dog>();
		dset.add(new Dog(2));
		dset.add(new Dog(1));
		dset.add(new Dog(3));
 
		Iterator<Dog> iterator = dset.iterator();
 
		while (iterator.hasNext()) {
			System.out.print(iterator.next() + " ");
		}
	}
}

Compile bien, pero se produce un error en tiempo de ejecución:

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)

Debido a que TreeSet está ordenado, el objeto Dog debe implementarse java.lang.Comparable‘s comparar con() método como el siguiente:

class Dog implements Comparable<Dog>{
	int size;
 
	public Dog(int s) {
		size = s;
	}
 
	public String toString() {
		return size + "";
	}
 
	@Override
	public int compareTo(Dog o) {
	        return size - o.size;
	}
}

La salida es:

1 2 3 

4. Ejemplo de HashSet

HashSet<Dog> dset = new HashSet<Dog>();
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<Dog> iterator = dset.iterator();
while (iterator.hasNext()) {
	System.out.print(iterator.next() + " ");
}

Producción:

5 3 2 1 4 

Tenga en cuenta que el orden no es seguro.

5. Ejemplo de LinkedHashSet

LinkedHashSet<Dog> dset = new LinkedHashSet<Dog>();
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<Dog> iterator = dset.iterator();
while (iterator.hasNext()) {
	System.out.print(iterator.next() + " ");
}

El orden de la salida es seguro y es el orden de inserción:

2 1 3 5 4 

6. Prueba de desempeño

El siguiente método prueba el desempeño de las tres clases en agregar() método.

public static void main(String[] args) {
 
	Random r = new Random();
 
	HashSet<Dog> hashSet = new HashSet<Dog>();
	TreeSet<Dog> treeSet = new TreeSet<Dog>();
	LinkedHashSet<Dog> linkedSet = new LinkedHashSet<Dog>();
 
	// start time
	long startTime = System.nanoTime();
 
	for (int i = 0; i < 1000; i++) {
		int x = r.nextInt(1000 - 10) + 10;
		hashSet.add(new Dog(x));
	}
	// end time
	long endTime = System.nanoTime();
	long duration = endTime - startTime;
	System.out.println("HashSet: " + duration);
 
	// start time
	startTime = System.nanoTime();
	for (int i = 0; i < 1000; i++) {
		int x = r.nextInt(1000 - 10) + 10;
		treeSet.add(new Dog(x));
	}
	// end time
	endTime = System.nanoTime();
	duration = endTime - startTime;
	System.out.println("TreeSet: " + duration);
 
	// start time
	startTime = System.nanoTime();
	for (int i = 0; i < 1000; i++) {
		int x = r.nextInt(1000 - 10) + 10;
		linkedSet.add(new Dog(x));
	}
	// end time
	endTime = System.nanoTime();
	duration = endTime - startTime;
	System.out.println("LinkedHashSet: " + duration);
 
}

De la salida a continuación, podemos decir claramente que HashSet es el más rápido.

HashSet: 2244768
TreeSet: 3549314
LinkedHashSet: 2263320

* La prueba no es precisa, pero puede reflejar la idea básica de que TreeSet es mucho más lento porque está ordenado.

Leer: ArrayList vs.LinkList vs.Vector