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

Question

Con un TreeMap es trivial proporcionar un Comparator personalizado, anulando así la semántica provista por los objetos Comparable añadidos al mapa. HashMap s sin embargo 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 case insensitive Map consigue un solución trivial:

new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY); 

Sería esto factible, o hay algún problemas fundamentales de este enfoque?

¿El enfoque utilizado en cualquier biblioteca existente (que no sea JRE)? (. Probado Google, sin suerte)

EDIT: Niza solución presentada por hazzen, pero me temo que esta es la solución que estoy tratando de evitar ...;)

EDIT: Se cambió el título a ningún mencionar más tiempo "Comparador"; Sospecho que esto fue un poco confuso.

EDIT: 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

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 2

Nota: Como se menciona en todas las demás 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.

Dicho todo esto, si solo quiere que su hashing ignore el caso de un String, puede escribir una clase contenedora alrededor de String para este propósito e insertarlas en su estructura de datos.

Una aplicación sencilla:

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 3

.NET tiene esta vía IEqualityComparer (para un tipo que se puede comparar dos objetos) y IEquatable (para un tipo que puede compararse a 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 sonido.

Answer 4

buena pregunta, pregunte 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 5

Sospecho que esto no se ha hecho porque podría evitar 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 tendría para conocer la Clase de sus llaves.)

Answer 6

Esta es una idea interesante, pero es absolutamente horrenda para el rendimiento. El motivo es fundamental para el idea of a hashtable: no se puede confiar en el pedido. Las tablas hash son muy rápidas (constant time) debido a la forma en que indexan los elementos en la tabla: calculando un hash entero pseudo-único para ese elemento y accediendo 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 algunos more in-depth analysis. En resumen, la eficiencia de un mapa de árbol depende de un ordenamiento consistente, por lo tanto, el orden de los elementos es predecible y sensato. Sin embargo, debido al golpe de rendimiento impuesto por el enfoque de "atravesar a su destino", las BST solo pueden proporcionar O (log (n)) rendimiento. Para mapas grandes, esto puede ser un golpe de rendimiento significativo.

Es posible imponer un ordenamiento coherente en una tabla hash, pero hacerlo implica utilizar técnicas similares a LinkedHashMap y mantener manualmente el orden. 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, su idea suena realmente buena, pero si realmente intenta implementarla, verá 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 7

Existe una característica en com.google.common.collect.CustomConcurrentHashMap, lamentablemente, actualmente no hay manera pública de configurar el Equivalence (su Hasharator).Tal vez todavía no hayan terminado, tal vez no consideren que la función sea lo suficientemente útil. Pregunte en el guava mailing list.

Me pregunto por qué no ha sucedido todavía, como se mencionó en este talk hace más de dos años.

Answer 8

Un poco tarde para ti, pero para los visitantes futuros, podría valer la pena sabiendo que Commons-colecciones tiene un AbstractHashedMap (en 3.2.1 y con los genéricos en 4.0). Puede anular estos métodos protegidas 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) { ... } 

Un ejemplo de dicha aplicación alternativa es HashedMap Commons-colecciones propia IdentityMap (sólo hasta 3.2.1 como Java tiene its own desde 1.4).

Esto no es tan poderoso como proporcionar un "Hasharator" externo a una instancia 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á 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 se puede utilizar un HashingStrategy con el construido en HashSet o HashMap. 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 
} 

He aquí cómo se puede configurar un UnifiedSetWithHashingStrategy y utilizarlo.

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 simplemente un Map? UnifiedSetWithHashingStrategy usa la mitad de la memoria de UnifiedMap, y un cuarto de la memoria de 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 , 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(), lo 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.