¿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 proporcionada por los objetos Comparable agregados al mapa. Sin embargo, HashMap s no se puede controlar de esta manera; las funciones que proporcionan valores hash y comprobaciones de igualdad no se pueden 'cargar lateralmente'.

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 El problema Mapa insensible a las mayúsculas recibe una solución trivial:

 new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY);

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

¿Se utiliza el enfoque en alguna biblioteca existente (no JRE)? (Intenté 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: Se cambió el título para que ya no se mencione " Comparator " ;; 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; vea la respuesta aceptada a continuación.

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

Answer 1

Trove4j tiene la función que estoy buscando y lo llaman estrategias de hashing.

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

Answer 2

Un poco tarde para usted, pero para futuros visitantes, podría valer la pena saber que commons-collections tiene un AbstractHashedMap (en 3.2.2 y con genéricos en 4.0 ) . Puede anular estos métodos protegidos para lograr el 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 un HashedMap alternativo es el propio IdentityMap de commons-collections (solo hasta 3.2.2 como Java tiene propio desde 1.4).

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

Answer 3

.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 la igualdad y los hashcodes en java.lang.Object o System.Object. La igualdad en particular es difícil de definir de una manera que tenga sentido con la herencia. Sigo queriendo bloguear sobre esto ...

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

Answer 4

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

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

No puede usar un HashingStrategy con el HashSet integrado 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
}

Así es como 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 solo usar un Mapa ? UnifiedSetWithHashingStrategy usa la mitad de la memoria de un UnifiedMap y un cuarto de la memoria de un HashMap . Y a veces no tienes una clave conveniente y tienes que crear una clave sintética, como una tupla. Eso puede desperdiciar más memoria.

¿Cómo realizamos búsquedas? Recuerde que los Conjuntos tienen contiene () , 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 que no distinguen entre 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 apropiada para la producción. El problema es que HashingStrategy delega constantemente a String.toLowerCase () que crea un montón de cadenas de basura. Aquí le mostramos cómo puede crear una estrategia de hash eficiente para cadenas que no distinguen entre 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 desarrollador de colecciones GS.

Answer 5

Nota: Como se señaló en todas las demás respuestas, HashMaps no tiene un orden explícito. Sólo reconocen "igualdad". Obtener un pedido de una estructura de datos basada en hash no tiene sentido, ya que cada objeto se convierte en un hash, esencialmente un número aleatorio.

Siempre puedes escribir una función hash para una clase (y muchas veces debe), siempre y cuando lo hagas con cuidado. Esto es algo difícil de hacer correctamente porque las estructuras de datos basadas en hash se basan en una distribución aleatoria y uniforme de los valores de hash. En Effective Java, 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 hash ignore el caso de una String , puede escribir una clase de envoltorio alrededor de String para este propósito e insertar aquellos en su estructura de datos en su lugar.

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 6

buena pregunta, pregúntale a Josh Bloch. Presenté ese concepto como RFE en Java 7, pero se eliminó, creo que la razón estaba relacionada con el rendimiento. Estoy de acuerdo, sin embargo, debería haberse hecho.

Answer 7

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 están envueltas en silencio. Resultó que la envoltura tendría que contener el objeto envuelto, el código hash almacenado en caché y una referencia a la interfaz de devolución de llamada responsable de los controles de igualdad. Obviamente, esto no es tan eficiente como usar una clase de contenedor, donde solo tendría que almacenar en caché la clave original más un objeto más (vea la respuesta a peligros).

(También me topé 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 del hashing tendría que realizar una instancia adicional de verificación. O eso, o la clase de mapa tendría que Conozca la clase de sus claves.)

Answer 8

Esta es una idea interesante, pero es absolutamente terrible 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 : mediante la computación de un hash entero pseudo-único para ese elemento y el acceso a esa ubicación en una matriz. Es, literalmente, calcular una ubicación en la memoria y almacenar directamente el elemento.

Esto contrasta con un árbol de búsqueda binario equilibrado ( TreeMap ) que debe comenzar en la raíz y avanzar hacia el nodo deseado cada vez que se requiere una búsqueda. Wikipedia tiene un análisis más detallado . 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 impacto en el rendimiento impuesto por el " atravesar a su destino " Enfoque, las BST solo pueden proporcionar el rendimiento de O (log (n)) . Para mapas grandes, esto puede ser un gran éxito de rendimiento.

Es posible imponer un orden consistente en una tabla hash, pero hacerlo implica usar técnicas similares a LinkedHashMap y mantener manualmente el orden. Alternativamente, dos estructuras de datos separadas se pueden mantener internamente: una tabla hash y un árbol. La tabla se puede usar para búsquedas, mientras que el árbol se puede usar para la 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 simultáneos pueden reducir esto un poco, pero eso no es una optimización de rendimiento confiable.

En resumen, su idea suena realmente bien, pero si realmente intentara implementarla, vería que hacerlo impondría limitaciones de rendimiento masivas. El veredicto final es (y ha sido durante décadas): si necesita rendimiento, use una tabla hash; Si necesita realizar un pedido y puede vivir con un rendimiento degradado, utilice un árbol de búsqueda binario 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 9

Hay una característica de este tipo en com.google.common.collect.CustomConcurrentHashMap , desafortunadamente, actualmente no hay una forma pública de configurar el Equivalence (su Hasharator ). Tal vez aún no hayan terminado con esto, tal vez no consideren que la característica sea lo suficientemente útil. Pregunte en la lista de correo de guayas .

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