Perché non consentire a un'interfaccia esterna di fornire hashCode / uguale a un HashMap?

Question

Con un TreeMap è banale fornire un Comparator personalizzato, sovrascrivendo così la semantica fornita dagli oggetti Comparable aggiunti alla mappa. HashMap tuttavia non può essere controllato in questo modo; le funzioni che forniscono valori hash e controlli di uguaglianza non possono essere "caricate lateralmente".

Sospetto che sarebbe sia facile che utile progettare un'interfaccia e adattarla in HashMap (o in una nuova classe)? Qualcosa del genere, tranne con nomi migliori:

  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) { ... }
  }

Il il problema insensibile alle maiuscole Mappa ottiene una soluzione banale:

 new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY);

Sarebbe fattibile o potresti vedere dei problemi fondamentali con questo approccio?

L'approccio è usato nelle librerie esistenti (non JRE)? (Ho provato google, senza fortuna.)

EDIT: bella soluzione presentata da hazzen, ma temo che questa sia la soluzione che sto cercando di evitare ...;)

EDIT: titolo modificato per non menzionare più " Comparator " ;; Sospetto che questo sia stato un po 'confuso.

EDIT: risposta accettata in relazione alla performance; mi piacerebbe una risposta più specifica!

EDIT: c'è un'implementazione; vedere la risposta accettata di seguito.

EDIT: ha riformulato la prima frase per indicare più chiaramente che è il caricamento laterale che sto cercando (e non l'ordinamento; l'ordinamento non appartiene a HashMap).

Answer 1

Trove4j ha la funzione che sto cercando e la chiamano strategie di hashing.

La loro mappa ha un'implementazione con diverse limitazioni e quindi diversi prerequisiti, quindi questo non significa implicitamente che un'implementazione per "nativo" di Java HashMap sarebbe fattibile.

Answer 2

Un po 'in ritardo per te, ma per i futuri visitatori, potrebbe valere la pena sapere che le collezioni comuni hanno un AbstractHashedMap (in 3.2.2 e con generici in 4.0 ) . Puoi ignorare questi metodi protetti per ottenere il comportamento desiderato:

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'implementazione di esempio di tale HashedMap è il IdentityMap proprio delle raccolte comuni (solo fino a 3.2.2 come Java ha proprio dall'1.4).

Non è potente quanto fornire un " Hasharator " a un'istanza Map . Devi implementare una nuova classe di mappe per ogni strategia di hashing (composizione contro ereditarietà che colpisce ...). Ma è ancora bello saperlo.

Answer 3

.NET ha questo tramite IEqualityComparer (per un tipo che può confrontare due oggetti) e IEquatable (per un tipo che può confrontarsi con un'altra istanza).

In effetti, credo che sia stato un errore definire l'uguaglianza e gli hashcode in java.lang.Object o System.Object. L'uguaglianza in particolare è difficile da definire in un modo che abbia senso con l'eredità. Continuo a significare blog su questo ...

Ma sì, fondamentalmente l'idea è valida.

Answer 4

HashingStrategy è il concetto che stai cercando. È un'interfaccia strategica che ti consente di definire implementazioni personalizzate di uguali e hashcode.

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

Non puoi usare un HashingStrategy con HashSet o HashMap integrati. Collezioni GS include un java.util.Set chiamato UnifiedSetWithHashingStrategy e un java .util.Map chiamato UnifiedMapWithHashingStrategy .

Diamo un'occhiata a un esempio.

public class Data
{
    private final int id;

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

    public int getId()
    {
        return id;
    }

    // No equals or hashcode
}

Ecco come è possibile impostare un UnifiedSetWithHashingStrategy e utilizzarlo.

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)));

Perché non usare semplicemente una Mappa ? UnifiedSetWithHashingStrategy utilizza metà della memoria di un UnifiedMap e un quarto della memoria di un HashMap . E a volte non hai una chiave conveniente e devi crearne una sintetica, come una tupla. Ciò può sprecare più memoria.

Come eseguiamo le ricerche? Ricorda che i set hanno contiene () , ma non get () . UnifiedSetWithHashingStrategy implementa Pool oltre a Set , quindi implementa anche una forma di get () .

Ecco un semplice approccio per gestire le stringhe senza distinzione tra maiuscole e minuscole.

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"));

Questo mostra l'API, ma non è appropriato per la produzione. Il problema è che HashingStrategy delega costantemente a String.toLowerCase () che crea un sacco di stringhe di immondizia. Ecco come è possibile creare una strategia di hashing efficiente per le stringhe senza distinzione tra maiuscole e minuscole.

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: sono uno sviluppatore delle raccolte GS.

Answer 5

Nota: come indicato in tutte le altre risposte, HashMaps non ha un ordine esplicito. Riconoscono solo "uguaglianza". Ottenere un ordine da una struttura di dati basata su hash non ha senso, poiché ogni oggetto viene trasformato in un hash, essenzialmente un numero casuale.

Puoi sempre scrivere una funzione hash per una classe (e spesso i tempi devono), purché lo fai con attenzione. Questa è una cosa difficile da fare correttamente perché le strutture dati basate su hash si basano su una distribuzione casuale e uniforme di valori hash. In Effective Java, c'è una grande quantità di testo dedicato all'implementazione corretta di un metodo hash con un buon comportamento.

Detto questo, se vuoi solo che il tuo hashing ignori il caso di una String , puoi scrivere una classe wrapper attorno a String per questo scopo e inserire quelli nella tua struttura dati invece.

Una semplice implementazione:

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

bella domanda, chiedi a Josh Bloch. ho presentato questo concetto come RFE in Java 7, ma è stato abbandonato, credo che il motivo fosse legato alle prestazioni. sono d'accordo, tuttavia, avrebbe dovuto essere fatto.

Answer 7

Sospetto che non sia stato fatto perché impedirebbe la memorizzazione nella cache di hashCode?

Ho tentato di creare una soluzione Map generica in cui tutte le chiavi sono inserite in silenzio. Si è scoperto che il wrapper avrebbe dovuto contenere l'oggetto spostato, l'hashCode memorizzato nella cache e un riferimento all'interfaccia di callback responsabile dei controlli di uguaglianza. Questo ovviamente non è efficiente come usare una classe wrapper, dove dovresti solo memorizzare nella cache la chiave originale più un altro oggetto (vedi risposta hazzens).

(Mi sono anche imbattuto in un problema relativo ai generici; il metodo get accetta Object come input, quindi l'interfaccia di callback responsabile dell'hash dovrebbe eseguire un ulteriore test di istanza. O quello, o la classe della mappa dovrebbe conoscere la classe delle sue chiavi.)

Answer 8

Questa è un'idea interessante, ma è assolutamente orribile per le prestazioni. La ragione di ciò è abbastanza fondamentale per l ' idea di un hashtable : non si può fare affidamento sull'ordinamento . Gli hashtable sono molto veloci ( tempo costante ) a causa del modo in cui indicizzano gli elementi nella tabella : calcolando un hash intero pseudo-unico per quell'elemento e accedendo a quella posizione in un array. Sta letteralmente calcolando una posizione in memoria e memorizzando direttamente l'elemento.

Ciò contrasta con un albero di ricerca binario bilanciato ( TreeMap ) che deve iniziare dalla radice e scendere fino al nodo desiderato ogni volta che è richiesta una ricerca. Wikipedia ha alcune analisi più approfondite . Riassumendo, l'efficienza di una mappa ad albero dipende da un ordinamento coerente, quindi l'ordine degli elementi è prevedibile e sano. Tuttavia, a causa del colpo di prestazione imposto dalla "traversata verso la destinazione" approccio, i BST sono solo in grado di fornire prestazioni O (log (n)) . Per le mappe di grandi dimensioni, questo può essere un notevole successo prestazionale.

È possibile imporre un ordinamento coerente su una tabella hash, ma per farlo è necessario utilizzare tecniche simili a LinkedHashMap e mantenere manualmente l'ordinamento. In alternativa, due strutture dati separate possono essere gestite internamente: una tabella hash e una struttura ad albero. La tabella può essere utilizzata per le ricerche, mentre l'albero può essere utilizzato per l'iterazione. Il problema ovviamente è che questo utilizza più del doppio della memoria richiesta. Inoltre, gli inserimenti sono veloci quanto l'albero: O (log (n)). I trucchi simultanei possono ridurre un po 'questo, ma non è un'ottimizzazione delle prestazioni affidabile.

In breve, la tua idea suona davvero buona, ma se davvero provassi a implementarla, vedresti che farlo importerebbe enormi limiti di prestazioni. Il verdetto finale è (ed è stato per decenni): se hai bisogno di prestazioni, usa una tabella hash; se hai bisogno di ordinare e puoi vivere con prestazioni degradate, usa un albero di ricerca binario bilanciato. Temo che non ci sia davvero una combinazione efficace delle due strutture senza perdere alcune garanzie dell'una o dell'altra.

Answer 9

C'è una tale funzione in com.google.common.collect.CustomConcurrentHashMap , sfortunatamente, al momento non esiste un modo pubblico come impostare Equivalence (il loro Hasharator ). Forse non hanno ancora finito, forse non considerano la funzione abbastanza utile. Chiedi alla mailing list guava .

Mi chiedo perché non sia ancora successo, come è stato menzionato in questo talk oltre due anni fa.