HashSet vs LinkedHashSet

153

¿Cuál es la diferencia entre ellos? Yo sé eso

LinkedHashSet es una versión ordenada de HashSet que mantiene una lista doblemente vinculada en todos los elementos. Use esta clase en lugar de HashSet cuando le importe el orden de iteración. Cuando itera a través de un HashSet, el orden es impredecible, mientras que LinkedHashSet le permite iterar a través de los elementos en el orden en que se insertaron.

Pero en el código fuente de LinkedHashSet solo hay constructores de llamadas de HashSet. Entonces, ¿dónde está la lista de doble enlace y el orden de inserción?

Shikarn-O
fuente
2
use la opción Intellij (Ctrl + B) para rastrear la respuesta. :)
Delta
por supuesto, necesita adjuntar el código fuente. :)
Delta

Respuestas:

65

Las mentiras de respuesta en que los constructores los LinkedHashSetusos para la construcción de la clase base:

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);      // <-- boolean dummy argument
}

...

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);            // <-- boolean dummy argument
}

...

public LinkedHashSet() {
    super(16, .75f, true);                         // <-- boolean dummy argument
}

...

public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);   // <-- boolean dummy argument
    addAll(c);
}

Y (un ejemplo de) HashSetse describe un constructor que toma un argumento booleano, y se ve así:

/**
 * Constructs a new, empty linked hash set.  (This package private
 * constructor is only used by LinkedHashSet.) The backing
 * HashMap instance is a LinkedHashMap with the specified initial
 * capacity and the specified load factor.
 *
 * @param      initialCapacity   the initial capacity of the hash map
 * @param      loadFactor        the load factor of the hash map
 * @param      dummy             ignored (distinguishes this
 *             constructor from other int, float constructor.)
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero, or if the load factor is nonpositive
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}
aioobe
fuente
2
Una clase padre con funcionalidad explícita para una clase hija, un argumento ignorado para distinguir
Traubenfuchs
55
No es exactamente un diseño limpio que utiliza un parámetro ficticio para la desambiguación del constructor.
Eric J.
8
Es un diseño razonablemente limpio, porque la API está limpia (este constructor HashSet es un paquete privado). Los detalles de implementación no son importantes para los usuarios de la clase. Mantener este código podría ser más difícil, pero en el caso de las clases java.util, incluso las mejoras de rendimiento muy pequeñas pueden justificar eso.
lbalazscs el
25

LinkedHashSetLos constructores invocan el siguiente constructor de clase base:

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
  map = new LinkedHashMap<E, Object>(initialCapacity, loadFactor);
}

Como puede ver, el mapa interno es a LinkedHashMap. Si miras dentro LinkedHashMap, descubrirás el siguiente campo:

private transient Entry<K, V> header;

Esta es la lista vinculada en cuestión.

NPE
fuente
24

HashSet es un conjunto desordenado y sin ordenar .
LinkedHashSet es la versión ordenada de HashSet.

La única diferencia entre HashSet y LinkedHashSet es que:
LinkedHashSet mantiene el orden de inserción.

Cuando iteramos a través de un HashSet , el orden es impredecible mientras que es predecible en el caso de LinkedHashSet .

La razón de cómo LinkedHashSet mantiene el orden de inserción es que:
La estructura de datos utilizada subyacente es la Lista doblemente vinculada .

Hema Ganapathy
fuente
9

Debería mirar la fuente del HashSetconstructor al que llama ... es un constructor especial que hace que el respaldo sea Mapen LinkedHashMaplugar de solo a HashMap.

ColinD
fuente
Gracias, en HashSet hay un constructor para crear LinkedHashMap, que se llama en LinkedHashSet y toda la lógica está en LinkedHashMap
Shikarn-O
5

Le sugiero que use la LinkedHashSetmayor parte del tiempo, porque tiene un mejor rendimiento general ):

  1. Orden de iteración predecible LinkedHashSet (Oracle)
  2. LinkedHashSet es más costoso para las inserciones que HashSet;
  3. En general, un rendimiento ligeramente mejor que HashMap, porque la mayoría de las veces usamos estructuras Set para iterar.

Pruebas de rendimiento:

------------- TreeSet -------------
 size       add  contains   iterate
   10       746       173        89
  100       501       264        68
 1000       714       410        69
10000      1975       552        69
------------- HashSet -------------
 size       add  contains   iterate
   10       308        91        94
  100       178        75        73
 1000       216       110        72
10000       711       215       100
---------- LinkedHashSet ----------
 size       add  contains   iterate
   10       350        65        83
  100       270        74        55
 1000       303       111        54
10000      1615       256        58

Puede ver la página de prueba de origen aquí: El ejemplo de prueba de rendimiento final

Dmytro Melnychuk
fuente
2
No veo ningún calentamiento de la JVM antes de esos "puntos de referencia", por lo que no tomaría en serio ninguno de esos datos. Leer más
Felix S
3

HashSet: Desordenado en realidad. si pasa el parámetro significa

Set<Integer> set=new HashSet<Integer>();
for(int i=0;i<set.length;i++)
{
  SOP(set)`enter code here`
}

Out Out: Puede 2,1,3no ser predecible. La próxima vez otra orden.

LinkedHashSet() que producen la orden FIFO.

Justin
fuente
3

HashSet no mantener el orden del elemento de inserción
LinkedHashSet mantener el orden del elemento de inserción

Ejemplo

Set<String> set = ...;// using new HashSet<>() OR new LinkedHashSet<>()
set.add("2");
set.add("1");
set.add("ab");
for(String value : set){
   System.out.println(value);
}  

HashSet salida

1
ab
2

LinkedHashSet salida

2
1
ab
Phan Van Linh
fuente
2

HashSet:

La estructura de datos subrayada es Hashtable. No se permiten objetos duplicados. El orden de inserción no se conserva y se basa en el código hash de los objetos. La inserción nula es posible (solo una vez). Implementa la interfaz Serializable, Clonable pero no RandomAccess. HashSet es la mejor opción si la operación frecuente es la operación de búsqueda.

En HashSet, los duplicados no están permitidos. Si los usuarios intentan insertar duplicados cuando no obtendremos ninguna excepción de compilación o tiempo de ejecución. El método add devuelve simplemente false.

Constructores:

HashSet h = nuevo HashSet (); crea un objeto HashSet vacío con capacidad inicial predeterminada 16 y la relación de llenado predeterminada (factor de carga) es 0,75.

HashSet h = nuevo HashSet (int initialCapacity); crea un objeto HashSet vacío con la capacidad inicial especificada y la proporción de relleno predeterminada es 0.75

HashSet h = nuevo HashSet (int initialCapacity, float fillRatio);

HashSet h = nuevo HashSet (Colección c); crea un objeto HashSet equivalente para la colección dada. Este constructor está destinado a la conversión entre objetos de colección.

LinkedHashSet:

Es una clase secundaria de HashSet. es exactamente lo mismo que HashSet incluyendo (Constructores y Métodos) excepto las siguientes diferencias.

Diferencias HashSet:

  1. La estructura de datos subrayada es Hashtable.
  2. El orden de inserción no se conserva.
  3. introdujo la versión 1.2.

LinkedHashSet:

  1. La estructura de datos subrayada es una combinación de LinkedList y Hashtable.
  2. Se conserva el orden de inserción.
  3. Indroducido en la versión 1.4.
Umapathi
fuente
1

Si echas un vistazo a los constructores llamados desde la LinkedHashSetclase, verás que internamente se LinkedHashMapusa para fines de respaldo.

arrecife
fuente
0

Todos los métodos y constructores son iguales, pero solo una diferencia es que LinkedHashset mantendrá el orden de inserción, pero no permitirá duplicados.

Hashset no mantendrá ningún orden de inserción. Es una combinación de Lista y Conjunto simple :)

Anand Mohan
fuente