Java HashSet

HashSet<E> es la implementación a la que recurres primero cuando quieres un conjunto. Está respaldada por una tabla hash — internamente es un HashMap con un valor ficticio — por lo que add, remove y contains son O(1) esperado: el costo es un hash del elemento más una o dos comprobaciones de igualdad, independientemente de cuántos elementos haya ya en el conjunto. Esa es la propiedad que hace que los hash sets sean la respuesta correcta para preguntas del tipo "¿he visto esto antes?", pasadas de deduplicación y cualquier comprobación de pertenencia que sería cuadrática contra una List.

Qué significa realmente "tiempo casi constante"

El tiempo constante no es gratuito; está amortizado. Cada operación hace aproximadamente esto:

1. Calcular e.hashCode(). Mezclar los bits altos y bajos para que un hash como 0x...0000 no colapse en el bucket 0.
2. Buscar el bucket en bucketIndex = hash & (table.length - 1).
3. Recorrer la cadena enlazada del bucket (o, desde Java 8, un pequeño árbol balanceado si la cadena se hizo larga) llamando a equals hasta encontrar el elemento o llegar al final.

El paso 3 es donde el costo se dispara si tu hashCode es malo. Con un hash razonable, la cadena tiene uno o dos elementos; con un hash constante, tiene todos los elementos que hayas insertado. Esa es la diferencia entre O(1) y O(n) por operación.

Capacidad, factor de carga y el rehash

Un HashSet tiene un array de buckets de respaldo. Dos parámetros del constructor lo controlan:

• Capacidad inicial — el número inicial de buckets. Por defecto es 16. Se redondea al siguiente potencia de dos.
• Factor de carga — la proporción de elementos a buckets en la que la tabla duplica su tamaño. Por defecto es 0.75.

Cuando size / capacity supera el factor de carga, el conjunto realiza un rehash: asigna un nuevo array del doble de tamaño y redistribuye cada elemento. Un rehash es O(n) — ese es el costo que se amortiza entre las inserciones O(1) previas. Pre-dimensionar un conjunto que sabes que contendrá ~1 000 000 elementos te ahorra veinte duplicaciones:

Set<Long> ids = new HashSet<>(1_500_000); // skip the doublings up to ~1M

Los factores de carga más pequeños (p. ej. 0.5) desperdician memoria pero reducen colisiones; los más grandes (p. ej. 0.9) empaquetan más pero hacen las cadenas más largas. El valor predeterminado 0.75 es un equilibrio que Sun calibró hace décadas y sigue siendo válido — no lo modifiques sin un benchmark.

Null, ordenamiento y seguridad de hilos

Tres reglas:

1. Se permite un elemento null. HashSet lo almacena en el bucket 0 con un hash especial de 0. Es una conveniencia deliberada — Map.of/Set.of y TreeSet prohíben null.
2. No se garantiza ningún orden de iteración. El orden cambia cuando la tabla hace rehash y ni siquiera es consistente entre JVMs. Si necesitas orden de inserción, usa LinkedHashSet; si necesitas orden ordenado, usa TreeSet.
3. No es seguro para hilos. La mutación concurrente corromperá la estructura. Para código multihilo usa ConcurrentHashMap.newKeySet() (una vista Set de un mapa concurrente) o envuélvelo en Collections.synchronizedSet.

hashCode es tu responsabilidad

Insertar tu propia clase en un HashSet solo funciona si sobrescribes hashCode y equals de forma consistente. El contrato de Object:

• Si a.equals(b) entonces a.hashCode() == b.hashCode().
• Si a.hashCode() == b.hashCode(), a.equals(b) puede seguir siendo falso (una colisión).

Romper la primera parte del contrato es la fuente más común de bugs del tipo "lo agregué, pero contains devuelve false". Los IDEs modernos y la palabra clave record generan ambos métodos por ti — úsalos.

record Tag(String name) {}            // hashCode/equals auto-generated
Set<Tag> tags = new HashSet<>();
tags.add(new Tag("java"));
System.out.println(tags.contains(new Tag("java"))); // true

La trampa del elemento mutable

Un bug más sutil: almacenar un objeto cuyo hashCode depende de campos mutables y luego mutarlo después de la inserción. El hash que decidió en qué bucket vive el elemento se calculó en el momento de la inserción; una vez que cambias un campo del que depende el hash, el objeto queda en el bucket "equivocado" y contains recorre una cadena que no lo incluye — aunque sea exactamente la misma referencia.

class Box {
    int n;
    Box(int n) { this.n = n; }
    @Override public boolean equals(Object o) {
        return o instanceof Box b && b.n == n;
    }
    @Override public int hashCode() { return Integer.hashCode(n); }
}

Box box = new Box(1);
Set<Box> set = new HashSet<>();
set.add(box);
box.n = 2;                  // mutate a field hashCode depends on
System.out.println(set.contains(box)); // false — element is now in the wrong bucket

Ten en cuenta que esto solo ocurre cuando hashCode lee estado mutable. StringBuilder, por ejemplo, usa hashing de identidad, por lo que mutarlo nunca lo mueve entre buckets — pero depender de eso es frágil. La solución no es ser ingenioso; es poner elementos inmutables en los hash sets. String, Integer, tus propios records, DTOs recién capturados. Si necesitas un conjunto con clave en algún estado mutable, usa una proyección inmutable de él como clave.

Un ejemplo práctico: deduplicación, pertenencia y capacidad

El programa a continuación demuestra las cuatro razones por las que recurres a un HashSet: deduplicación, pruebas de pertenencia rápidas, álgebra de conjuntos y el costo de un hashCode malo.

Conclusiones clave:

• El bucle de deduplicación es O(n) — cada add es de tiempo constante, y el unique.size() final es el número de entradas distintas.
• Un contains en un conjunto de 1 000 000 de elementos respondió en microsegundos. Esa es la propiedad que hace de HashSet la herramienta de comprobación de pertenencia del JDK.
• El record Tag obtiene equals/hashCode de forma gratuita, por lo que dos objetos Tag("java") se colapsan en un único elemento.
• El ejemplo Box es la trampa: el mismo objeto, mutado después de la inserción de modo que su hashCode cambió, ahora devuelve contains(box) == false. Pon elementos inmutables en los hash sets.

Qué sigue

HashSet no promete ningún orden de iteración. Si necesitas recordar el orden en que insertaste los elementos — por ejemplo, estás construyendo una lista de etiquetas y el usuario espera verlas en el orden en que fueron agregadas — la herramienta correcta es LinkedHashSet. Ese es el próximo capítulo.

Práctica