En este post veremos cómo funciona internamente el HashSet en Java, que también es una pregunta de entrevista de favouriteJava Collections, pero antes de entrar en la implementación interna del HashSet en Java es importante conocer dos puntos sobre el HashSet.
- El HashSet en Java solo almacena valores únicos, es decir, no se permiten duplicados.
- HashSet funciona en el concepto de hashing al igual que HashMap en Java, pero su funcionamiento difiere del HashMap de la siguiente manera:
- En HashMap se agrega un par (Clave, Valor) y la función hash se calcula utilizando key.
- Donde como en la función hash de HashSet se calcula utilizando el valor en sí. Tenga en cuenta que en el HashSet tenemos el método add(E e) que toma solo el elemento a agregar como parámetro.
También puede que ya lo haya adivinado, ya que la función hash se calcula utilizando value, por eso solo se almacenan valores únicos en el conjunto de hash. Si intenta almacenar el mismo elemento de nuevo, la función hash calculada será la misma, por lo que el elemento se sobrescribirá.
HashSet utiliza internamente HashMap
Ahora volviendo a la implementación interna de HashSet en Java, el punto más importante es la implementación de clase de HashSet utiliza internamente HashMap para almacenar sus elementos.
Dentro de la HashSet hay muchos constructores sin ningún parámetro y varios más con capacidad inicial o factor de carga, pero cada uno de estos constructor crea un HashMap.Dado que el HashSet utiliza internamente HashMap, conocer cómo funciona internamente HashMap en Java le ayudará a comprender cómo funciona internamente el HashSet en Java.
Fragmentos de código del constructor de HashSet
En la clase de HashSet en Java, puede ver que los constructores de la clase crean un mapa de hashes.
/*** Constructs a new, empty set; the backing <tt>HashMap</tt> instance has* default initial capacity (16) and load factor (0.75).*/public HashSet() { map = new HashMap<>();}
public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor);}
Y el mapa, que se utiliza para almacenar valores, se define como
private transient HashMap<E,Object> map;
En el constructor, si ha notado, hay parámetros llamados capacidad inicial y factor de carga.Para el HashSet, la capacidad inicial predeterminada es 16, es decir, se crearía un array (o cubo) de longitud 16 y el factor de carga predeterminado es 0.75. Donde el factor de carga es una medida de hasta qué punto se permite que la tabla hash se llene antes de que su capacidad aumente automáticamente.
¿Cómo se agregan los elementos – HashSet implementación interna
he dicho en el punto 2 anterior que HashSet calcula el hash de la función con valor en sí mismo y thereis no (Clave, Valor) de par en HashSet y luego vino la declaración de que HashSet utiliza internamente HashMap para almacenar objetos.Estas dos sentencias pueden sonar contradictorias, ya que los almacenes de HashMap (clave, valor) se emparejan, así que veamos cómo estas dos sentencias contradictorias se mantienen verdaderas.
En realidad desde el método add de la clase HashSet se llama al método put () de HashMap donde el valor, que tiene que ser añadido en el Conjunto, se convierte en Clave y se usa un objeto constante «PRESENTE» como valor.
Así es como se define PRESENTE en la implementación de HashSet-
// Dummy value to associate with an Object in the backing Mapprivate static final Object PRESENT = new Object();
Y así es como se implementa el método add en la clase HashSet-
public boolean add(E e) { return map.put(e, PRESENT)==null;}
Para que pueda ver que en la implementación interna del HashSet es un par (clave, valor) que en realidad está obteniendo added.It es solo que el valor real (que se agrega al HashSet) se convierte en la clave y un valor ficticio «PRESENTE» se agrega como valor al almacenarlo en el HashMap de respaldo.
Por ejemplo, una instrucción para agregar un elemento a HashSet-set.add («Mumbai»); internamente se traduce en mapa.put («Mumbai», PRESENTE); y luego se agrega a la instancia de HashMap de respaldo.
Una cosa a tener en cuenta aquí es que en el mapa de hash el valor puede ser duplicado, pero la clave debe ser única. Así es como HashSet se asegura de que solo se almacenen valores únicos, ya que el valor que se va a almacenar en el HashSet se convierte en la clave mientras se almacena en HashMap.
Cómo se elimina el elemento-Implementación interna del HashSet
Cuando necesitamos eliminar un elemento del HashSet, internamente de nuevo el método remove del método HashSetcalls remove (Clave de objeto) del HashMap.
Así es como se implementa en la clase HashSet.
public boolean remove(Object o) { return map.remove(o)==PRESENT;}
Tenga en cuenta que el método remove(Object key) del HashMap devuelve el Valor asociado a la clave.Mientras que el método remove (Object o) del HashSet devuelve un valor booleano. También sabemos que para cada valor añadido en el HashSet, internamente cuando se agrega al HashMap asociado, el valor se convierte en Clave y el valor siempre es un objeto llamado PRESENTE. Por lo tanto, el valor que se devuelve del método remove(Clave de objeto) del HashMap siempre está PRESENTE, por lo tanto, el mapa de condiciones.remove (o) = = PRESENTE.
Cómo se recuperan los elementos del HashSet en Java
En el HashSet no hay ningún método get como se proporciona en Mapa o Lista. En el iterador de hashes está el que iterará a través de los valores del Conjunto. Internamente llamará al conjunto de claves del HashMap, ya que los valores se almacenan como claves en el HashMap, por lo que lo que obtendremos son los valores almacenados en el conjunto de claves.
Así es como iterator se implementa internamente en el HashSet en Java.
/*** Returns an iterator over the elements in this set. The elements* are returned in no particular order.** @return an Iterator over the elements in this set* @see ConcurrentModificationException*/public Iterator<E> iterator() { return map.keySet().iterator();}
Puntos a tener en cuenta
- A diferencia de HashMap, donde la función hash se calcula utilizando el conjunto de claves, utiliza el valor en sí para calcular la función hash.
- Dado que la función hash se calcula utilizando valor, es por eso que solo se almacenan valores únicos en el conjunto de hash.
- HashSet utiliza internamente HashMap para almacenar sus elementos.
- Cuando se agrega un elemento al HashSet usando el método add(E e) internamente, el HashSet llama al método put() del mapa de hashes, donde el valor pasado en el método add se convierte en clave en el método put (). Un valor ficticio «PRESENT» se pasa como valor en el método put ().
Recomendaciones para el aprendizaje (Cursos Udemy)
- Curso de Masterclass de Programación Java
- Java En Profundidad: ¡Conviértete en un Completo Ingeniero de Java!
- Curso de Clase Maestra de Spring Framework
- Curso completo de Bootcamp de Python
- Python para Ciencia de Datos y Aprendizaje automático
Eso es todo para este tema Cómo funciona el HashSet internamente en Java. Si tiene alguna duda o sugerencia que hacer, por favor deje un comentario. ¡Gracias!
Temas relacionados
- Cómo Funciona ArrayList Internamente en Java
- Cómo funciona HashMap Internamente en Java
- Cómo Funciona la Clase LinkedList Internamente en Java
- LinkedHashSet en Java Con Ejemplos
- TreeSet en Java Con Ejemplos
También te puede gustar-