HashSet en Java

La clase HashSetimplementa la interfaz Set, se basa en una tabla hash y también está respaldada por una instancia HashMap. Dado que HashSetlos elementos no están ordenados, no hay garantía de que estén en el mismo orden después de un tiempo. Las operaciones de agregar, eliminar y buscar se realizarán en tiempo constante, siempre que la función hash distribuya correctamente los elementos en “cubos”, lo cual se discutirá más adelante. Algunos puntos importantes sobre HashSet:

• Porque la clase implementa la interfaz Set, solo puede almacenar valores únicos;
• Puede almacenar valores NULL;
• El orden en que se agregan los elementos se calcula mediante un código hash;
• HashSettambién implementa el Serializabley Cloneable.

Para mantener un tiempo de ejecución constante de las operaciones, el tiempo dedicado a las acciones con HashSet, debe ser directamente proporcional al número de elementos en HashSet+ la "capacidad" de la instancia integrada HashMap(el número de "cestas"). Por lo tanto, para mantener el rendimiento, es importante no establecer la capacidad inicial demasiado alta (o el factor de carga demasiado bajo). Capacidad inicial: el número inicial de celdas ("contenedores") en la tabla hash. Si todas las celdas están llenas, su número aumentará automáticamente. El factor de carga es una medida de qué tan lleno puede estar HashSetantes de que su capacidad aumente automáticamente. Cuando el número de elementos es HashSetmayor que el producto de la capacidad inicial y el factor de carga, la tabla hash se vuelve a aplicar hash (los códigos hash de los elementos se recalculan y la tabla se reconstruye de acuerdo con los valores obtenidos) y el número El número de células que contiene se duplica. Factor de carga = Número de elementos almacenados en la tabla / tamaño de la tabla hash. Por ejemplo, si el número inicial de celdas en la tabla es 16 y el factor de carga es 0,75, se deduce que cuando el número de celdas llenas llega a 12, el El número de celdas aumentará automáticamente. El factor de carga y la capacidad inicial son los dos factores principales que afectan el rendimiento de HashSet. Un factor de carga de 0,75 proporciona un buen rendimiento en promedio. Si se aumenta este parámetro, la carga de memoria se reducirá (ya que reducirá el número de repeticiones hashes y reconstrucciones), pero afectará las operaciones de adición y búsqueda. Para minimizar el tiempo dedicado a repetir el hash, debe elegir el parámetro de capacidad inicial correcto. Si la capacidad inicial es mayor que el número máximo de elementos dividido por el factor de carga, no se producirá ninguna operación de repetición. Importante: HashSetno es una estructura de datos con sincronización incorporada, por lo que si varios subprocesos trabajan en ella al mismo tiempo y al menos uno de ellos intenta realizar cambios, es necesario proporcionar acceso sincronizado desde el exterior. Esto a menudo se hace a expensas de otro objeto sincronizado que encapsule el archivo HashSet. Si no existe tal objeto, entonces el Collections.synchronizedSet(). Actualmente, esta es la mejor manera de evitar operaciones desincronizadas con HashSet.

Set s = Collections.synchronizedSet(new HashSet(...));

Constructores de HashSet:

1. HashSet h = new HashSet(); - Constructor predeterminado. La capacidad inicial predeterminada es 16, el factor de carga es 0,75.
2. HashSet h = new HashSet(int initialCapacity)– un constructor con una capacidad inicial determinada. Factor de carga – 0,75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);— un constructor con una capacidad inicial y un factor de carga determinados.
4. HashSet h = new HashSet(Collection C)– un constructor que agrega elementos de otra colección.

El siguiente código demuestra algunos métodos HashSet:

import java.util.*;

class Test
{
    public static void main(String[]args)
    {
        HashSet<String> h = new HashSet<String>();

        // Agrega elementos al HashSet usando el método add()
        h.add("India");
        h.add("Australia");
        h.add("South Africa");
        h.add("India");// intenta agregar otro mismo elemento

        // Imprime los elementos del HashSet a la consola
        System.out.println(h);
        System.out.println("List contains India or not:" +
                           h.contains("India"));

        // Elimina elementos del conjunto usando el método remove()
        h.remove("Australia");
        System.out.println("List after removing Australia:"+h);

        // Recorre los elementos del HashSet usando un iterador:
        System.out.println("Iterating over list:");
        Iterator<String> i = h.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}

Conclusión:

[South Africa, Australia, India]
List contains India or not:true
List after removing Australia:[South Africa, India]
Iterating over list:
South Africa
India

Todas las clases que implementan una interfaz Setestán soportadas internamente por implementaciones Map. HashSetalmacena elementos usando HashMap. Aunque HashMapun elemento debe representarse como un par clave-valor para agregarle un elemento, HashSetsolo se agrega el valor. De hecho, el valor que pasamos HashSetes la clave del objeto HashMapy se utiliza una constante como valor HashMap. De esta forma, en cada par clave-valor, todas las claves tendrán el mismo valor. Implementación HashSeten java doc:

private transient HashMap map;

// Constructor - 1
// Todos los constructores crean implícitamente un objeto HashMap.
public HashSet()
{
    // Crear un objeto HashMap implícito
    map = new HashMap();
}

// Constructor- 2
public HashSet(int initialCapacity)
{
    // Crear un objeto HashMap implícito
    map = new HashMap(initialCapacity);
}

// Un objeto de la clase Object, actuando cada vez como un valor en HashMap
private static final Object PRESENT = new Object();

Si nos fijamos en el método add()y HashSet:

public boolean add(E e)
{
   return map.put(e, PRESENT) == null;
}

Puede notar que el método add()y HashSetllama al método put()en el objeto interno HashMap, pasándole el elemento que se agregará como clave y la constante PRESENTE como valor. El método funciona de manera similar remove(). Llama al método remove()del objeto interno HashMap:

public boolean remove(Object o)
{
  return map.remove(o) == PRESENT;
}

HashSetse basa en una tabla hash y las operaciones de agregar, eliminar o buscar se completarán, en promedio, en un tiempo constante (O(1)) . Métodos HashSet:

1. boolean add(E e): agrega un elemento a HashSet, si no hay ninguno, pero si dicho elemento ya está presente, el método devuelve false .
2. void clear():elimina todos los elementos de un conjunto.
3. boolean contains(Object o): Devuelve verdadero si el elemento dado está presente en el conjunto.
4. boolean remove(Object o): Elimina el elemento dado del conjunto, si está presente.
5. Iterator iterator(): Devuelve un iterador para los elementos del conjunto.
6. boolean isEmpty(): Devuelve verdadero si no hay elementos en el conjunto.
7. Object clone(): Realiza clonación de superficies HashSet.

Javadoc: https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html