java - metodo - para que es el hashcode

¿Por qué no permitir que una interfaz externa proporcione hashCode/equals para un HashMap?

Question

Con TreeMap es trivial proporcionar un Comparator personalizado, anulando así la semántica provista por los objetos Comparable agregados al mapa. Sin embargo, HashMap s no se puede controlar de esta manera; las funciones que proporcionan valores de hash y verificaciones de igualdad no se pueden ''cargar por los lados''.

Sospecho que sería fácil y útil diseñar una interfaz y adaptarla a HashMap (¿o una nueva clase)? Algo como esto, excepto con mejores nombres:

  interface Hasharator<T> {
    int alternativeHashCode(T t);
    boolean alternativeEquals(T t1, T t2);
  }

  class HasharatorMap<K, V> {
    HasharatorMap(Hasharator<? super K> hasharator) { ... }
  }

  class HasharatorSet<T> {
    HasharatorSet(Hasharator<? super T> hasharator) { ... }
  }

El problema de Map insensible a mayúsculas y minúsculas obtiene una solución trivial:

 new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY);

¿Sería factible, o puede ver algún problema fundamental con este enfoque?

¿Se usa el enfoque en cualquier libs existente (que no sea JRE)? (Probé google, sin suerte.)

EDITAR: buena solución presentada por Hazzen, pero me temo que esta es la solución que estoy tratando de evitar ...;)

EDITAR: Título modificado para dejar de mencionar "Comparador"; Sospecho que esto fue un poco confuso.

EDITAR: respuesta aceptada en relación con el rendimiento; me encantaría una respuesta más específica!

EDITAR: hay una implementación; ver la respuesta aceptada a continuación.

EDITAR: reformulé la primera oración para indicar más claramente que es la carga lateral que estoy buscando (y no ordenar; el orden no pertenece a HashMap).

Answer 1

.NET tiene esto a través de IEqualityComparer (para un tipo que puede comparar dos objetos) e IEquatable (para un tipo que puede compararse con otra instancia).

De hecho, creo que fue un error definir igualdad y hashcodes en java.lang.Object o System.Object en absoluto. La igualdad en particular es difícil de definir de manera que tenga sentido con la herencia. Sigo pensando en blog sobre esto ...

Pero sí, básicamente, la idea es sólida.

Answer 2

Buena pregunta, pregúntale a Josh Bloch. Envié ese concepto como un RFE en Java 7, pero fue descartado, creo que la razón fue algo relacionado con el rendimiento. estoy de acuerdo, sin embargo, debería haber sido hecho.

Answer 3

Esta es una idea interesante, pero es absolutamente horrenda para el rendimiento. La razón de esto es bastante fundamental para la idea de una tabla hash : no se puede confiar en el orden. Las tablas hash son muy rápidas ( tiempo constante ) debido a la forma en que indexan los elementos en la tabla: al calcular un hash entero pseudo único para ese elemento y acceder a esa ubicación en una matriz. Está literalmente computando una ubicación en la memoria y almacenando directamente el elemento.

Esto contrasta con un árbol de búsqueda binaria equilibrada ( TreeMap ) que debe comenzar en la raíz y avanzar hasta el nodo deseado cada vez que se requiera una búsqueda. Wikipedia tiene un análisis más profundo . Para resumir, la eficiencia de un mapa de árbol depende de un orden consistente, por lo tanto, el orden de los elementos es predecible y sensato. Sin embargo, debido al golpe de rendimiento impuesto por el enfoque "atravesar a su destino", las BST solo pueden proporcionar el rendimiento O (log (n)) . Para mapas grandes, esto puede ser un golpe de rendimiento significativo.

Es posible imponer un orden consistente en una tabla hash, pero hacerlo implica utilizar técnicas similares a LinkedHashMap y mantener manualmente la ordenación. Alternativamente, se pueden mantener dos estructuras de datos separadas internamente: una tabla hash y un árbol. La tabla se puede usar para búsquedas, mientras que el árbol se puede usar para iteración. El problema, por supuesto, es que utiliza más del doble de la memoria requerida. Además, las inserciones son tan rápidas como el árbol: O (log (n)). Los trucos concurrentes pueden reducir esto un poco, pero esa no es una optimización de rendimiento confiable.

En resumen, tu idea suena realmente bien, pero si realmente intentas implementarla, verás que hacerlo impondría enormes limitaciones de rendimiento. El veredicto final es (y ha sido durante décadas): si necesita rendimiento, use una tabla hash; si necesita ordenar y puede vivir con un rendimiento degradado, use un árbol de búsqueda binaria equilibrado. Me temo que realmente no hay una combinación eficiente de las dos estructuras sin perder algunas de las garantías de una u otra.

Answer 4

Nota: Como se menciona en todas las otras respuestas, los HashMaps no tienen un orden explícito. Solo reconocen "igualdad". Obtener una orden de una estructura de datos basada en hash no tiene sentido, ya que cada objeto se convierte en hash, esencialmente un número aleatorio.

Siempre puede escribir una función hash para una clase (y muchas veces debe hacerlo), siempre que lo haga con cuidado. Esto es algo difícil de hacer correctamente porque las estructuras de datos basadas en hash dependen de una distribución aleatoria y uniforme de los valores hash. En Java efectivo, hay una gran cantidad de texto dedicado a implementar correctamente un método hash con buen comportamiento.

Con todo lo que se dice, si solo quiere que su hashing ignore el caso de un String , puede escribir una clase contenedora alrededor de String para este fin e insertarlos en su estructura de datos.

Una implementación simple:

public class LowerStringWrapper {
    public LowerStringWrapper(String s) {
        this.s = s;
        this.lowerString = s.toLowerString();
    }

    // getter methods omitted

    // Rely on the hashing of String, as we know it to be good.
    public int hashCode() { return lowerString.hashCode(); }

    // We overrode hashCode, so we MUST also override equals. It is required
    // that if a.equals(b), then a.hashCode() == b.hashCode(), so we must
    // restore that invariant.
    public boolean equals(Object obj) {
        if (obj instanceof LowerStringWrapper) {
            return lowerString.equals(((LowerStringWrapper)obj).lowerString;
        } else {
            return lowerString.equals(obj);
        }
    }

    private String s;
    private String lowerString;
}

Answer 5

Sospecho que esto no se ha hecho porque evitaría el almacenamiento en caché de hashCode?

Intenté crear una solución de Mapa genérica donde todas las claves se envuelven silenciosamente. Resultó que la envoltura tendría que contener el objeto envuelto, el hashCode en caché y una referencia a la interfaz de devolución de llamada responsable de las verificaciones de igualdad. Esto obviamente no es tan eficiente como usar una clase contenedora, donde solo tendrías que almacenar en caché la clave original más un objeto más (ver la respuesta de hazzens).

(También me encontré con un problema relacionado con los genéricos, el método get acepta Object como entrada, por lo que la interfaz de devolución de llamada responsable de hash tendría que realizar una instancia adicional de verificación. O eso, o la clase de mapa debería conocer la clase de sus llaves.)

Answer 6

Trove4j tiene la característica que estoy buscando y lo llaman estrategias de hash.

Su mapa tiene una implementación con diferentes limitaciones y por lo tanto diferentes requisitos previos, por lo que esto no significa implícitamente que una implementación para HashMap "nativo" de Java sería factible.

Answer 7

Hay una función de este tipo en com.google.common.collect.CustomConcurrentHashMap , lamentablemente, actualmente no hay forma pública de configurar Equivalence (su Hasharator ). Tal vez todavía no hayan terminado, tal vez no consideren que la función sea lo suficientemente útil. Pregunte en la lista de correo de guayaba .

Me pregunto por qué aún no ha sucedido, como se mencionó en esta charla hace más de dos años.

Answer 8

Un poco tarde para usted, pero para futuros visitantes, podría valer la pena saber que Commons-collections tiene un AbstractHashedMap (en 3.2.1 y con genéricos en 4.0 ). Puede anular estos métodos protegidos para lograr su comportamiento deseado:

protected int hash(Object key) { ... }
protected boolean isEqualKey(Object key1, Object key2) { ... }
protected boolean isEqualValue(Object value1, Object value2) { ... }
protected HashEntry createEntry(
    HashEntry next, int hashCode, Object key, Object value) { ... }

Una implementación de ejemplo de dicha alternativa es HashedMap commons-collections '' IdentityMap (solo hasta 3.2.1 ya que Java tiene su propio desde 1.4).

Esto no es tan poderoso como proporcionar un " Hasharator " externo a una instancia de Map . Tienes que implementar una nueva clase de mapa para cada estrategia de hash (la composición frente a la herencia regresa ...). Pero aún es bueno saberlo.

Answer 9

HashingStrategy es el concepto que estás buscando. Es una interfaz de estrategia que le permite definir implementaciones personalizadas de iguales y hashcode.

public interface HashingStrategy<E>
{
    int computeHashCode(E object);
    boolean equals(E object1, E object2);
}

No puede usar una HashingStrategy con HashSet o HashMap HashSet . GS Collections incluye un java.util.Set llamado UnifiedSetWithHashingStrategy y un java.util.Map llamado UnifiedMapWithHashingStrategy .

Veamos un ejemplo.

public class Data
{
    private final int id;

    public Data(int id)
    {
        this.id = id;
    }

    public int getId()
    {
        return id;
    }

    // No equals or hashcode
}

A continuación, le mostramos cómo puede configurar un UnifiedSetWithHashingStrategy y usarlo.

java.util.Set<Data> set =
  new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(Data::getId));
Assert.assertTrue(set.add(new Data(1)));

// contains returns true even without hashcode and equals
Assert.assertTrue(set.contains(new Data(1)));

// Second call to add() doesn''t do anything and returns false
Assert.assertFalse(set.add(new Data(1)));

¿Por qué no usar un Map ? UnifiedSetWithHashingStrategy utiliza la mitad de la memoria de UnifiedMap y la cuarta parte de la memoria de un HashMap . Y a veces no tienes una clave conveniente y tienes que crear una sintética, como una tupla. Eso puede desperdiciar más memoria.

¿Cómo realizamos búsquedas? Recuerde que Sets tiene contains() , pero no get() . UnifiedSetWithHashingStrategy implementa Pool además de Set , por lo que también implementa una forma de get() .

Aquí hay un enfoque simple para manejar Cadenas insensibles a mayúsculas y minúsculas.

UnifiedSetWithHashingStrategy<String> set = 
  new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(String::toLowerCase));
set.add("ABC");
Assert.assertTrue(set.contains("ABC"));
Assert.assertTrue(set.contains("abc"));
Assert.assertFalse(set.contains("def"));
Assert.assertEquals("ABC", set.get("aBc"));

Esto muestra la API, pero no es apropiado para la producción. El problema es que HashingStrategy delega constantemente en String.toLowerCase() que crea un montón de cadenas de basura. A continuación, le mostramos cómo puede crear una estrategia de hashing eficiente para Cadenas insensibles a mayúsculas y minúsculas.

public static final HashingStrategy<String> CASE_INSENSITIVE =
  new HashingStrategy<String>()
  {
    @Override
    public int computeHashCode(String string)
    {
      int hashCode = 0;
      for (int i = 0; i < string.length(); i++)
      {
        hashCode = 31 * hashCode + Character.toLowerCase(string.charAt(i));
      }
      return hashCode;
    }

    @Override
    public boolean equals(String string1, String string2)
    {
      return string1.equalsIgnoreCase(string2);
    }
  };

Nota: soy un desarrollador de colecciones GS.