Conjuntos (Sets)

Aspectos a tener en cuenta

Un conjunto (set) es una colección de objetos que no puede contener duplicados. Añadir un elemento ya presente en la colección no tendrá ningún efecto. Conjuntos

El interfaz Set define los mismos métodos que el interfaz Collection. Hay muchos tipos de colecciones que implementan la interfaz Set: HashSet, EnumSet, AbstractSet, LinkedHashSet, TreeSet, CopyOnWriteArraySet,…

Elegir una u otra dependerá del rendimiento en estos factores: búsqueda, lectura, ordenación etc…

Clases que implementan Set

Implementación HashSet

Es la implementación más usada de Set. Como su nombre indica, se implementa mediante un tabla hash. Una tabla hash básicamente es un array donde cada uno de sus elementos se asocia a una posición calculada a partir del propio contenido que se almacenará en dicha posición. En el caso concreto de Java, se emplea el valor hash devuelto por cada objeto (método hashCode( ) de Object) y se aplica una máscara sobre los bits menos significativos de dicho valor.

Importante: Dado que la posición que ocupa un elemento en la tabla hash depende de su propio contenido, y no del orden o instante en que se añadió a la tabla, no podemos garantizar el orden en que un iterador sobre la tabla nos devolverá su contenido (como veremos en el próximo ejemplo).

Ventaja:

  • Velocidad de acceso de lectura/escritura constante y rápido.

Desventaja:

  • No recomendable para recorrer todos los objetos de la colección.

Método HasCode()

Método de Object que podemos sobrescribir para cambiar el “id” de nuestros objetos. Es decir crear un hash único. Para una correcta sobrescritura de este método, hay que tener en cuenta estos aspectos:

  • Debe devolver un int. Si es necesario crear cast y/o parsear.
  • Debe tener la suficiente complejidad para que no se produzcan colisiones.
  • Es conveniente implementar el método equals: Este método viene a complementar al método hashCode y sirve para comparar objetos de una forma más rápida en estructuras Hash ya que únicamente nos devuelve un número entero. Cuando Java compara dos objetos en estructuras de tipo hash (HashMap, HashSet etc) primero invoca al método hashcode y luego el equals. Si los métodos hashcode de cada objeto devuelven diferente hash no seguirá comparando y considerará a los objetos distintos. En el caso en el que ambos objetos compartan el mismo hashcode Java invocará al método equals() y revisará a detalle si se cumple la igualdad. De esta forma las búsquedas quedan simplificadas en estructuras hash.
  • Se debe usar los mismos atributos para hashCode() como para equals().
  • Si hay algún cambio de valor en los atributos de equals(), el hashCode debe cambiar.
  • Al sobrescribir este método, dos objetos con el mismo contenido (iguales para nosotros) tiene que devolver el mismo hash: Probarlo!

Por tanto a partir de ahora si sobreescribimos el equals() debemos sobreescribir el hashCode() y viceversa.

Ejemplo:

class Money {
    
    private int amount;
    private String currencyCode;
    
    public Money(int dinero, String code) {
        this.amount = dinero;
        this.currencyCode = code;
    }
    
    public int getAmount() {
        return amount;
    }
    
    public String getCurrencyCode() {
        return currencyCode;
    }
    
    
    @Override
    public boolean equals(Object o) {
        
        if (o == this)
            return true;
        if (!(o instanceof Money))
            return false;
        Money other = (Money)o;
        boolean currencyCodeEquals = (this.currencyCode == null && other.currencyCode == null)
          || (this.currencyCode != null && this.currencyCode.equals(other.currencyCode));
        return this.amount == other.amount && currencyCodeEquals;
    }
    
    @Override
    public int hashCode() {
        //Todos los strings tienen este método
        if (currencyCode != null)
            return currencyCode.hashCode() + amount;
        return amount + 3;
    }

Implementar este método en cada clase de una aplicación es tedioso, repetitivo y propenso a errores, para hacer más sencilla su implementación existe el método Objects.hash desde la versión 7 de Java. Un ejemplo para una clase que representa un número de teléfono quedaría así:

public class PhoneNumber {

    ...

    @Override
    public int hashCode() {
        return Objects.hash(areaCode, prefix, lineNumber);
    }
}

Creación, agregar y recuperar

Ejemplo básico de declararlo y agregar objetos:

 // HashSet declaracion
      HashSet<String> hset = 
               new HashSet<String>();

      // Agregar elementos al HashSet
      hset.add("Apple");
      hset.add("Mango");
      hset.add("Grapes");
      hset.add("Orange");
      hset.add("Fig");

      //Agregar (intentar) objetos duplicados
      hset.add("Apple");
      hset.add("Mango");

      //Esta permitido agregar valores nulos
      hset.add(null);

      System.out.println(hset);

Los demás métodos típicos de Collection se usan igual con esta colección, cabe destacar algún método de la teoría de conjuntos como el retainAll(): ¿Que hace?

HashSet<Integer> numbersValues = new HashSet<Integer>();
  
            numbersValues.add(4);
            numbersValues.add(6);
            numbersValues.add(8);
            numbersValues.add(10);
            numbersValues.add(12);
  
            System.out.println("Initial hashSet " + numbersValues);
  
            HashSet<Integer> numbersValuesToRetain = new HashSet<Integer>();
            arrset2.add(4);
            arrset2.add(6);
            arrset2.add(8);
  
            System.out.println("Values to retain" + numbersValuesToRetain);
            numbersValues.retainAll(numbersValuesToRetain);
  
            System.out.println("HashSet after retainAll " + numbersValues);

Hay más…

Ejercicio 1

Escribe un método denominado maxLength que acepte un HashSet de cadenas de caracteres y devuelva la longitud de la cadena más larga. Si el Set está vacío, devolverá 0

Escribe un método denominado hasOdd que acepte un Set de enteros y devuelva true o false dependiendo de si el Set contiene algún número impar o no.

Escribe un método denominado removeEvenLength que acepte un Set de cadenas de caracteres y elimine del Set todas las cadenas de longitud par.

Ejercicio 2

Modifica el ejercicio de agenda de arrayList, y usa ahora HashSet. Debes evitar que en la agenda se pueda agregar dos personas con el mismo número. Crea tu propio calculo de hash para los objetos Persona. ¿Cómo lo harías?

Implementación TreeSet

Almacenamiento basado en un árbol. Un árbol normalmente se implementa como una variante de lista enlazada en la que cada nodo puede contener 1 o más hijos. A medida que se van insertando elementos en la colección, estos se irán “colocando” de forma ordenada sobre el árbol. La estructura normal es de un arbol binario. Por defecto en orden ascendente. El TreeSet no mantiene el orden de inserción, los elementos se ordenan por orden natural. Y tampoco tiene objetos duplicados. Implementa estas dos interfaces NavigableSet y SortedSet, esto provoca métodos adicionales para odenación y recorrer la coleccción:

Metodos principales

Ejemplo:

import java.util.*;
public class SetDemo3 {
 
 public static void main(String[] args) {
    TreeSet<Integer> ts = new TreeSet<>();
    ts.add(4); ts.add(-1); ts.add(0);
    ts.add(2); ts.add(7); ts.add(5);
    ts.add(3); ts.add(3); ts.add(3); // Sólo almacenará uno
    System.out.println("ts: " + ts); // Estarán ordenados de menor a mayor
    System.out.println("Mayor: " + ts.last() + ", Menor: " + ts.first());
    System.out.println("Primer elemento mayor que 0: " + ts.higher(0));
    System.out.println("Primer elemento menor o igual que 6: " + ts.floor(6));
    NavigableSet<Integer> range = ts.subSet(-5, true, 3, false);
    System.out.println("Elementos en el rango [-5, 3): " + range);
 }
}

Recorrer un TreeSet

Para este tipo de colección podemos usar los “mecanismos” ya vistos (for, iterator, forEach), pero también podemos usar otra forma más de lambda stream() y Map:

 TreeSet<Integer> ts = new TreeSet<Integer>();

     ts.addAll(Arrays.asList(10, 61, 87, 39));

     System.out.print("TreeSet:");

     // Usando forEach
     ts.forEach(i -> System.out.print(i + " "));
     System.out.println();

     System.out.print("TreeSet:");

     // Usando stream con map (mapear cada elemento), el Collectors lo transforma en una lista
     System.out.print(
         ts.stream()
             .map(i -> String.valueOf(i)) .collect(Collectors.toList())
             );

Aclaración final

Hemos visto en TreeSet se hace una inserción y se ordena de manera ascendente, ¿que ocurre si son objetos complejos? –> Será necesario comparar y ordenar Prueba a agregar al TreeSet objetos complejos ¿qué ocurre?

Ejercicio 3

Las operaciones típicas de conjuntos son: union, diferencia e intersección. Haz un programa que prueba con los datos de los conjuntos A y B las tres operaciones indicadas. El resultado del programa debe ser el siguiente. Consulta el API para saber los métodos que debes usar para hacer las operaciones deseadas. A:[5, 7, 9, 19] B:[10, 20, 5, 7] A union B: [19, 20, 5, 7, 9, 10] A diferencia B: [19, 9] A intersección B: [5, 7]

Ejercicio 4

Crea un pequeño programa donde se inserten números aleatorios del 1 al 100 en una estructura de datos. Debemos insertar 50 elementos y que no se repitan.

Ejercicio 5

Crea un método que muestre el ultimo elemento de un TreeSet de enteros y lo elimine.