3 Conjuntos¶

Introducción¶

Un conjunto es una lista formada por elementos que no se repiten. Para ello, la JVM usará los métodos equals y hashCode heredados la clase clase Object para comprobar si dos elementos son iguales.

Son métodos heredados de la clase Object. Normalmente, hay que sobrescribirlos para adaptarlo de forma adecuada a la clase correspondiente.

Sin embargo, debemos tener en cuenta que al sobrescribir todos estos métodos debemos seguir cumpliendo con el comportamiento que se espera de ellos, ya que son usados internamente por muchas clases del propio lenguaje. De lo contario, las clases que dependen de ello, como HashMapy HashSet dejarían de funcionar correctamente.

Escribir a mano los métodos equals() y hashCode() es bastante tedioso. Para facilitarnos esta tarea tenemos librerías como la librería AutoValue de Google que lo genera automáticamente para nosotros con tan sólo usar una determinada anotación. Otra opción es dejar que el IDE nos genere dichos métodos, aunque esto tiene el inconveniente de que no se generan automáticamente de nuevo conforme añadimos atributos a nuestro clase, por lo que debemos tener cuidado, algo que sí hace AutoValue. En todo caso, es mejor usar el IDE que hacerlo nosotros a mano, ya que el humano es más propenso a los errores. En el Eclipse se encuentra en Menú Source → Generate hashCode() and equals().

Método equals¶

El método equals() comprueba si dos objetos son iguales.

En caso de que no se sobrescriba dicho método, sólo será igual a sí misma, es decir, si está situada en la misma posición de memoria.

Debemos tener en cuenta que cuando un programador usa el método equals() sobre un objeto pasándole como argumento otro objeto lo que pretende es descubrir si ambos objetos son equivalentes lógicamente(representa el mismo "valor"), no si están almacenados en la misma posición de memoria (tienen la misma identidad).

No sobrescribir el método equals() en una determinada clase es la opción recomendada en los siguientes casos:

• Cuando cada instancia de la clase es intrínsecamente única, lo cual es cierto para clases como Scanner que representan entidades activas en lugar de valores.
• Cuando se considera que no hay necesidad de que la clase provea una prueba de equivalencia lógica.
• Cuando una superclase de la clase ya lo ha sobrescrito y el comportamiento de la superclase es apropiado para las subclase.
• Cuando la clase es privada o friendly, y estamos completamente seguros de que su método equals() nunca será invocado, ni explícita ni implícitamente.

Si nuestra clase no se encuentra en ninguno de los casos anteriores es muy recomendable que sobrescribamos el método equals(). Un ejemplo muy característico es cuando la clase corresponda a una entidad que represente un valor.

Como hemos comentado, cuando sobrescribamos el método equals() debemos seguir cumpliendo el comportamiento que el sistema espera de él, que incluye las siguientes propiedades:

• Reflexiva: Para todo objeto x distinto de null se debe cumplir que x.equals(x) sea true.
• Simétrica: Para todo par de objetos x e y y distintos de null se debe cumplir que x.equals(y) sólo debe retornar true si y.equals(x) retorna true.
• Transitiva: Para todo trío de objetos x, y, z distintos de null se debe cumplir que si x.equals(y) retorne true y y.equals(z) retorna true entonces x.equals(z) debe retornar true.
• Consistente: Para todo par de objetos x e y distintos de null se debe cumplir que x.equals(y)siempre retorne el mismo valor si no hemos cambiado los atributos que se usan para comparar en alguno de los objetos.
• Para todo objeto x distinto de null se debe cumplir que x.equals(null)debe retornar false.

Así para sobrescribir el método equals() cumpliendo con las propiedades anteriores se recomienda seguir los siguientes pasos:

1. Usar el operador == para comprobar si el argumento corresponde a otra referencia al mismo objeto, en cuyo caso retornar true.
2. Usar el operador instanceof para comprobar si el objeto recibido como argumento no es de la misma clase, en cuyo caso retornar false. También nos sirve para comprobar si dichos argumento es null, ya que en este caso instanceof retornaría false.
3. Hacer cast del objeto recibido como argumento convirtiéndolo a la clase correspondiente. Dado que hemos hecho antes instanceof, el cast siempre tendrá éxito.
4. Para cada atributo significativo de la clase, comprobar que dicho atributo en el objeto argumento es equivalente al atributo en el objeto this. Si no tenemos éxito en alguno de ellos, retornar false. Si todas las comprobaciones se han hecho con éxito, retornar true. Para realizar las comprobaciones de cada atributo usar:
   • El operador == para valores primitivos que no sean float ni double.
   • Para los valores float usar Float.compare(value1, value2) y para valores double usar Double.compare(value1, value2).
   • Para valores correspondientes a objetos llamar a equals() recursivamente. Si es válido que dichos objetos contengan null, entonces debemos usar Objects.equals(object1, object2) para que no se produzca la excepción NullPointerException.
   • Para los valores correspondientes a arrays, compara uno a uno los elementos significativos del array. Si todos los elementos son significativos, usa alguno de las versiones del método estático Arrays.equals().

Veamos un ejemplo:

public final class PhoneNumber{
    private final short areaCode, prefix, lineNum;

    @Override
    public boolean equals(Object o){
        if(o == this) return true;
        if(!(o instanceof PhoneNumber)) return false;
        PhoneNumber pn = (PhoneNumber) o;
        return pn.lineNum == lineNum && pn.prefix == prefix && pn.areaCode == areaCode;
    }
//...
}

public boolean equals(MyClass o){
    //...
}

Método hashCode¶

El método hashCode() devuelve un número entero que identifica al objeto cuando se guarda en algunas estructuras de datos.

Un detalla muy importante que no debemos olvidar es que **si en una clase sobrescribimos el método equals() debemos obligatoriamente sobrescribir también el método hashCode() o de lo contrario no se estará cumpliendo con el comportamiento esperado de este último, lo que impedirá que los objetos de dichas clase funcionen correctamente en colecciones como HashMap y HashSet.

El comportamiento que se espera de hashCode() es el siguiente:

• Debe ser consistente, es decir, que repetidas llamadas al método hashCode() deben retornar el mismo valor, siempre y cuando no se haya modificado ninguno de los atributos usados para las comparaciones.
• Si dos objetos son equivalentes, es decir, si x.equals(y) retorna true, entonces x.hashCode() e y.hashCode() deben retornar el mismo valor entero. Éste ees el motivo por el que siempre que sobrescribamos equals() debemos sobrescribir hashCode(), ya que la implementación por defecto de hashCode() de la clase Object devuelve una representación numérica de la dirección de memoria en la que se encuentra ubicado el objeto.
• Si dos objetos no son equivalentes, es decir si x.equals(y) retorna false, no es estrictamente necesario, aunque si recomendable, que x.hashCode() e y.hashCode() retornen valores diferentes, de manera que se mejore el rendimiento de las tablas hash. Idealmente el algoritmo de la función hash debe distribuir una colección de instancias de un tamaño considerable de forma uniforme entre todos los valores enteros.

La implementación característica al sobrescribir el método hashCode() en la clase PhoneNumber es la siguiente, usando los atributos areaCode, prefix, lineNum.

public final class PhoneNumber{
    private final short areaCode, prefix, lineNum;

    @Override
    public boolean equals(Object o){
        if(o == this) return true;
        if(!(o instanceof PhoneNumber)) return false;
        PhoneNumber pn = (PhoneNumber) o;
        return pn.lineNum == lineNum && pn.prefix == prefix && pn.areaCode == areaCode;
    }

    @Override
    public int hashCode(){
        int result = Short.hashCode(areaCode);

        result = 31 * result + Short.hashCode(prefix);
        result = 31 * result + Short.hashCode(lineNum);
        return result;
    }
//...
}

Además de escribir nosotros a mano el código del método hashCode(), podemos usar la implementación proporcionada por algunas librerías, como Guava o AutoValue, o usar la implementación de los IDEs.

Por otra parte, podemos usar Objects.hashCode(object...) para sobrescribir el método con una sola línea. Desafortunadamente, este método es bastante menos eficiente de lo esperado, debido a que recibe un array de atributos y de que realiza boxing y unboxing de los atributos que sean de un tipo primitivo. Por ejemplo:

public final class PhoneNumber{
    private final short areaCode, prefix, lineNum;

    @Override
    public boolean equals(Object o){
        if(o == this) return true;
        if(!(o instanceof PhoneNumber)) return false;
        PhoneNumber pn = (PhoneNumber) o;
        return pn.lineNum == lineNum && pn.prefix == prefix && pn.areaCode == areaCode;
    }

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

Si una clase es inmutable y el coste de calcular el valor hash es significativo, podría considerar almacenar cacheado el código hash en el propio objecto, en lugar de recalcularlo cada vez que se solicite. Si cree que la mayoría de los objetos de esta clase se usarán como claves hash, entonces debería calcular el código hash cuando se cree la instancia. De lo contario, podría elegir calcular perezosamente el código hash la primera vez que se invoque el método hash().

Dos consideraciones finales:en primer lugar no excluya atributos significativos del cálculo de valor hash, así logrará un mejor rendimiento, al no repetir tanto los valores. En segundo lugar, no proporcione a los clientes de la clase demasiada información acerca de cómo se calcula el valor hash de esta manera el código no podrá depender de cómo se calcula, permitiéndonos modificar la implementación del método en el futuro sin afectar a los clientes.

Colecciones sin duplicados¶

La interfaz Set, que hereda de Collection, permite implementar listas de elementos sin duplicados, es decir, modela la abstracción matemática de los conjuntos.

Existen varios tipos de implementaciones realizadas dentro de la plataforma Java:

• HashSet: esta implementación almacena los elementos de una tabla hash. Es la implementación con mejor rendimiento de todas pero no garantiza ningún orden a la hora de realizar iteraciones.
• LinkedHashSet: está implementación almacena los elementos en función del orden de inserción. Es un poco más costosa que HashSet.
• TreeSet: está implementación utiliza una estructura de árbol para ordenar los elementos. Es bastante más lenta que HashSet.

Clase HashSet¶

Implementa la interfaz Set. Es la clase más utilizada para implementar listas sin duplicados. Esta clase permite el elemento nulo. No garantiza ningún orden a la hora de realizar iteraciones.

Utiliza internamente una tabla de tipos hash:

Al querer guardar un objeto en esta estructura, se llama al método hashCode() el cual devuelve un número entero que la estructura usará para decidir en qué cajón debe recuperar el objeto. El objetivo de guardar los datos de esta forma y de llamar al método es lograr almacenar y recuperar la información en tiempo constante (lo cual no ocurre siempre, pero se acerca). El que no suceda esto depende, casi siempre, del valor que devuelva el método hashCode() para cada objeto.

Supongamos que guardamos 3 objetos en esta estructura y el método hashCode() de los 3 devuelve 0, esto quiere decir que los 3 objetos se guardarán en el cajón 0. Cuando se necesite recuperar un objeto, hay que recorrer los objetos del cajón 0 para determinar cuál es el que se quiere recuperar. Por lo tanto, este método hashCode() no es útil ya que lo que se pretende al guardar los elementos es que éstos queden dispersos de forma uniforme en toda la estructura quedando la menor cantidad de cajones vacíos y que no haya cajones donde se guarden muchos más elementos que en otros.

Si dos objetos tiene el mismo hashCode(), ambos objetos se guardarán en el mismo cajón. La estructura usa entonces el método equals() dentro de ese cajón para determinar cuál corresponde con el solicitado y para eso depende de que el programador haya sobrescrito el método, de lo contrario no garantiza un resultado correcto.

Los objetos HashSet se construyen con un tamaño inicial de tabla (el tamaño del array) y un factor de carga que indica cuándo se debe redimensionar el array. Es decir, si se creó un array de 100 elementos y la carga se estableció al 80%, cuando se hayan rellanado 80 valores, se redimensiona el array. Por defecto, el tamaño del array se toma con 16 y el factor de carga con 0,75 (75%). No obstante, se puede construir una lista HashSet indicando ambos parámetros.

Esta implementación proporciona tiempos constantes en las operaciones básicas siempre y cuando la función hash disperse de forma correcta los elementos dentro de la tabla hash. Es importante definir el tamaño inicial de la tabla ya que este tamaño marcará el rendimiento de esta implementación.

Veamos un ejemplo de HashSet con la clase Vehicle. Los atributos significativos a tener en cuenta para el equals() y el hashCode() son wheelCount y colour. La velocidad (speed) no se incluye ya que si comparamos el mismo coche pero con velocidades distintas, en realidad, no deja de ser el mismo coche.

public class Vehicle {
    private int wheelCount;
    private double speed;
    private String colour;

    public Vehicle(int wheelCount, String colour) {
        this.wheelCount = wheelCount;
        this.colour = colour;
        speed = 0;
    }

    public int getWheelCount() {
        return wheelCount;
    }

    public double getSpeed() {
        return speed;
    }

    public String getColour() {
        return colour;
    }

    public void setColour(String colour) {
        this.colour = colour;
    }

    public void accelerate(double amount) {
        speed += amount;
    }

    public void brake(double amount) {
        speed -= amount;
    }

    @Override
    public String toString() {
        return "Vehicle [wheelCount=" + wheelCount + ", speed=" + speed + ",colour=" + colour + "]";
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((colour == null) ? 0 : colour.hashCode());
        result = prime * result + wheelCount;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (!(obj instanceof Vehicle other))
            return false;

        if (colour == null) {
            if (other.colour != null)
                return false;
        } else if (!colour.equals(other.colour))
            return false;

        return wheelCount == other.wheelCount;
    }
}

import java.util.HashSet;
import java.util.Set;
public class ShowHashSet {
    public void show() {
        Set<Vehicle> set = new HashSet<>();

        set.add(new Vehicle(4, "azul"));
        set.add(new Vehicle(2, "rojo"));
        set.add(new Vehicle(4, "azul"));
        set.add(new Vehicle(2, "rojo"));
        set.add(new Vehicle(4, "verde"));

        for (Vehicle v : set) {
            System.out.println(v);//Se llama al toString del objeto
        }
    }

    public static void main(String[] args) {
        new ShowHashSet().show();
    }
}

Vehicle [wheelCount=4, speed=0.0, colour=verde]
Vehicle [wheelCount=4, speed=0.0, colour=azul]
Vehicle [wheelCount=2, speed=0.0, colour=rojo]

Clase LinkedHashSet¶

Almacena los elementos en función del orden de inserción. Es un poco más costosa que HashSet.

import java.util.LinkedHashSet;
import java.util.Set;

public class ShowLinkedHashSet {
    public void show() {
        Set<Vehicle> set = new LinkedHashSet<>();

        set.add(new Vehicle(4, "azul"));
        set.add(new Vehicle(2, "rojo"));
        set.add(new Vehicle(4, "azul"));
        set.add(new Vehicle(2, "rojo"));
        set.add(new Vehicle(4, "verde"));

        for (Vehicle v : set) {
            System.out.println(v);//Se llama al toString del objeto
        }
    }

    public static void main(String[] args) {
        new ShowLinkedHashSet().show();
    }
}

Vehicle [wheelCount=4, speed=0.0, colour=azul]
Vehicle [wheelCount=2, speed=0.0, colour=rojo]
Vehicle [wheelCount=4, speed=0.0, colour=verde]

Clase EnumSet¶

Es una implementación de conjuntos de alto rendimiento de tipos enumerados. Require que las constantes de enumeración colocadas en él pertenezcan al mismo tipo de enumeración. Veamos algunos de sus métodos:

• static <E extends Enum<E>> EnumSet<E> allOf(Class<E> elementType): crea un conjunto de enumeraciones que contiene todos los valores del tipo de enumeración especificado.
• static <E extends Enum<E>> EnumSet<E> complementOf(EnumSet<E> s): crea un conjunto de numeraciones con el mismo tipo que el conjunto de enumeraciones especificado, conteniendo inicialmente todos los elementos de este tipo que no están contenidos en el conjunto especificado.
• static <E extends Enum<E>> EnumSet<E> copyOf(EnumSet<E> s): crea un conjunto de enumeraciones a partir de otro.
• static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType): crea un conjunto de enumeraciones vacío con el tipo de elemento especificado.
• static <E extends Enum<E>> EnumSet<E> of(E e): crea un conjunto de enumeraciones que contiene el elemento especificado. Este método tiene varias sobrecargas para admitir más elementos.
• static <E extends Enum<E>> EnumSet<E> range(E from, E to): crea un conjunto de enumeraciones que contiene inicialmente todos los elementos del rango definido por los dos elementos especificados.

public enum Operation {
    PLUS("+"), MINUS("-"), TIMES("*"), DIVIDE("/");

    private final String symbol;

    private Operation(String symbol) {
        this.symbol = symbol;
    }

    public String getSymbol() {
        return symbol;
    }
}

public class ShowEnumSet {
    public void show() {
        EnumSet<Operation> allOperations1, allOperations2, operations1, operations2, operations3, operations4;

        allOperations1 = EnumSet.allOf(Operation.class);
        System.out.printf("allOf: %s", allOperations1);//allOf: [PLUS, MINUS,TIMES, DIVIDE]

        allOperations2 = EnumSet.copyOf(allOperations1);
        System.out.printf("\ncopyOf: %s", allOperations2);//copyOf: [PLUS,MINUS, TIMES, DIVIDE]

        operations1 = EnumSet.noneOf(Operation.class);
        operations1.add(Operation.PLUS);
        operations1.add(Operation.MINUS);
        System.out.printf("\nnoneOf y add: %s", operations1);//noneOf y add: [PLUS, MINUS]

        operations2 = EnumSet.complementOf(operations1);
        System.out.printf("\ncomplementOf: %s", operations2);//complementOf:[TIMES, DIVIDE]

        operations3 = EnumSet.of(Operation.DIVIDE, Operation.MINUS);
        System.out.printf("\nof: %s", operations3);//of: [MINUS, DIVIDE]

        operations4 = EnumSet.range(Operation.MINUS, Operation.DIVIDE);
        System.out.printf("\nrange: %s\n", operations4);//range: [MINUS,TIMES, DIVIDE]

        System.out.println(operations4.contains(Operation.PLUS));//false
        System.out.println(operations4.contains(Operation.MINUS));//true
    }

    public static void main(String[] args) {
        new ShowEnumSet().show();
    }
}