2

Como dice la pregunta, ¿Cómo funciona HashSet internamente?

Viendo este código:

HashSet<String> a = new HashSet<>();
a.add("hola");
a.add("hola");
a.add("holaa");
a.add("hola");

Otra pregunta, ¿De qué forma verifica la colección que el elemento añadido a la colección no esté repetido?

2 respuestas 2

5

Como preguntas solo sobre HashSet<T>, pues es simple: esta clase delega casi todas sus funcionalidades a un HashMap<T, Object>, donde el objeto que insertas en el HashSet será la clave del mapa interno, y se registrará con el valor de un objeto por defecto dentro del mapa. Toda la lógica de verificación que el elemento no sea repetido la maneja el mapa interno utilizado en la instancia del set.

Puesto que un Set solo sirve como un wrapper para un Map, desde Java SE 6 puedes crear un Set a partir de cualquier instancia de Map vía Collections#newSetFromMap.

Para una respuesta más de fondo: ¿cómo se manejan las igualdades de elementos al realizar HashMap#put(llave, valor)? Primero se debe comprender la estructura que maneja HashMap. Primero se define un nodo Node<K,V> para almacenar los pares llave/valor y HashMap mantiene un arreglo de estos nodos. Estos nodos implementan una lista enlazada simple. Desde Java 8, se ha cambiado la implementación para que conforme el mapa vaya creciendo a lo largo del tiempo, al contener muchos valores más entonces los nodos cambian su estructura de lista enlazada a árbol rojo-negro, lo cual provee un mayor rendimiento.

Aquí va una explicación del algoritmo interno utilizado dentro de HashMap#put:

  1. Obtener un hash de la llave. Para obtener este hash, se hace uso del valor de Object#hashCode. HashMap no utilizará el valor de este hash directamente, sobre este valor aplicará otra fórmula para reducir el valor lo más que se pueda.
  2. Verifica si el arreglo interno puede almacenar el valor del nuevo par al verificar que la posición a insertar esté vacía (algo similar a arreglo[hashInterno] == null).
  3. Si la casilla está vacía, se agrega el nuevo par llave/valor.
  4. Si la casilla no está vacía debido a una colisión de hashes: dos o más objetos produjeron el mismo valor de hash (no significa que los dos objetos poseen el mismo resultado de Object#hashCode), se obtiene el nodo actual de la casilla. Llamaremos al nodo N:

    4.1. Si la llave en N es igual a la nueva llave vía llaveActual.equals(nuevaLlave), se reemplaza el valor actual almacenado en N con el nuevo valor.

    4.2. Si la llave en N no es igual a la nueva llave a insertar y N posee la estructura de árbol, entonces se navegará por los nodos del árbol para agregar el nuevo par llave/valor. Se sigue la misma premisa: si encuentra un nodo Nx en el árbol cuya llave sea igual la nueva llave vía llaveActual.equals(nuevaLlave), se reemplaza el valor en Nx. Si al finalizar la búsqueda no se encuentra un nodo con la misma llave, se agregará un nuevo nodo en el árbol.

    4.3. Si no la llave en N no es igual a la nueva llave y posee la estructura de lista enlazada, se navegará a través de todos los nodos de la lista enlazada buscando si alguna llave en los nodos es igual a la nueva llave. En caso de no encontrar dicho nodo, se agregará un nuevo nodo al final de la lista con el nuevo par llave/valor. Luego de la inserción, si la lista enlazada tiene un valor mayor a un umbral interno (en HotSpot, TREEIFY_THRESHOLD que es igual a 8) entonces la lista enlazada se convertirá en un árbol rojo-negro.

  5. Verifica si el arreglo de nodos debe incrementar su tamaño utilizando un umbral configurado internamente. De ser así, lo incrementa.

¿De que forma verifica la colección que el elemento añadido a la colección no esté repetido?

Según la explicación previa, HashMap navegará a través de los nodos necesarios (no significa que navegará por todos los elementos) para comprobar si existe un nodo con llave igual a la nueva llave vía Object#equals. En caso de no existir y haber agotado todas las búsquedas, agregará un nuevo nodo con la información llave/valor.

6
  • Que beneficio tiene que la clase hashSet tenga sus funcionalidad en la clase hashMap?
    – MatiEzelQ
    el 22 mar. 2016 a las 0:32
  • Al fin y al cabo, estaría trabajando con un Map? Estoy entendiendo mal me parece uhh
    – MatiEzelQ
    el 22 mar. 2016 a las 0:33
  • Pues no tienes que reescribir la lógica de uno en el otro. Eso se llama reuso. Además, el Map ya se asegura de mantener entradas únicas por llave.
    – user227
    el 22 mar. 2016 a las 0:33
  • Una gran diferencia es que Set implementa la interfaz Collection mientras que Map no lo hace. Usualmente utilizas Set cuando necesitas un conjunto (como el conjunto que se ve en matemáticas), para validar que no hayan elementos repetidos.
    – user227
    el 22 mar. 2016 a las 0:44
  • Mmm es mucha confusión esto de las colecciones. Me va a tomar tiempo entenderlas. Igual ya voy captando lo básico de cada una.
    – MatiEzelQ
    el 22 mar. 2016 a las 0:47
0

Tiene ciertas caracteristicas...

  1. No estan ordenados los objetos

  2. Este tipo no soporta valores duplicados

  3. En vez de put, usa add

  4. El hashset es usado como un conjunto, no es de tipo (key, value)

  5. Se suele usar cuando quieres una lista unica de objetos

Espero que te haya servido de ayuda!

2
  • Disculpa, pero HashSet no gestiona un arreglo y tampoco calcula el hash del objeto. HashSet solo es una máscara para HashMap.
    – user227
    el 21 mar. 2016 a las 22:18
  • Tienes razon! actualizado para no dar lugar a errores! Gracias! el 21 mar. 2016 a las 22:53

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.