Warum darf eine externe Schnittstelle nicht HashCode/Equals für eine HashMap bereitstellen?

Question

Mit einem TreeMap ist es trivial, eine benutzerdefinierte Comparator bereitzustellen, wodurch die Semantik von Comparable Objekten, die der Karte hinzugefügt werden, überschrieben wird. HashMap s kann jedoch nicht auf diese Weise gesteuert werden; Die Funktionen, die Hash-Werte und Gleichheitsprüfungen bereitstellen, können nicht "seitengeladen" werden.

Ich vermute, es wäre sowohl einfach als auch nützlich, eine Schnittstelle zu entwerfen und diese in HashMap (oder eine neue Klasse) nachzurüsten? So etwas wie dies, außer mit besseren Namen:

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

Das case insensitive Map Problem bekommt eine triviale Lösung:

new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY); 

Wäre dies machbar, oder können Sie sehen, alle grundlegenden Probleme mit diesem Ansatz?

Wird der Ansatz in vorhandenen (nicht JRE) Bibliotheken verwendet? (. Versuchte google, kein Glück)

EDIT: Nice Abhilfe durch hazzen vorgestellt, aber ich fürchte, das ist das Problem zu umgehen Ich versuche, ... zu vermeiden;)

EDIT: Changed Titel nicht längere Erwähnung "Komparator"; Ich vermute, das war ein bisschen verwirrend.

EDIT: Akzeptierte Antwort in Bezug auf die Leistung; würde eine spezifischere Antwort lieben!

EDIT: Es gibt eine Implementierung; Sehen Sie die akzeptierte Antwort unten.

EDIT: Umformuliert den ersten Satz, um deutlicher zu zeigen, dass es die Seitenladung ist, nach der ich bin (und nicht bestellen; Bestellung gehört nicht in HashMap).

Answer 1

Trove4j hat die Funktion, nach der ich bin, und sie nennen es Hashing-Strategien.

Ihre Map hat eine Implementierung mit unterschiedlichen Einschränkungen und damit unterschiedlichen Voraussetzungen, was nicht unbedingt bedeutet, dass eine Implementierung für die "native" HashMap von Java möglich wäre.

Answer 2

Hinweis: Wie in allen anderen Antworten erwähnt, haben HashMaps keine explizite Reihenfolge. Sie erkennen nur "Gleichheit" an. Es ist bedeutungslos, eine Bestellung aus einer Hash-basierten Datenstruktur zu erhalten, da jedes Objekt in einen Hash umgewandelt wird - im Wesentlichen eine Zufallszahl.

Sie können immer eine Hash-Funktion für eine Klasse schreiben (und oft müssen), solange Sie es sorgfältig tun. Dies ist eine schwierige Sache, da Hash-basierte Datenstrukturen auf einer zufälligen, einheitlichen Verteilung von Hash-Werten beruhen. In Effektivem Java gibt es eine große Menge an Text, der für die ordnungsgemäße Implementierung einer Hash-Methode mit gutem Verhalten verwendet wird.

Mit allem, was gesagt wird, wenn Sie den Fall eines String zu ignorieren, nur Ihre Hashing wollen, können Sie eine Wrapper-Klasse um String zu diesem Zweck schreiben und stattdessen die in Ihrer Datenstruktur einzufügen.

Eine einfache Implementierung:

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 hat dies über IEqualityComparer (für eine Art, die zwei Objekte vergleichen) und IEquatable (für einen Typ, der sich auf eine andere Instanz vergleichen).

In der Tat, ich glaube, es war ein Fehler, Gleichheit und Hashcodes in java.lang.Object oder System.Object überhaupt zu definieren. Gerade die Gleichheit ist schwer zu definieren, wie es bei der Vererbung Sinn macht. Ich habe den Sinn, darüber zu bloggen ...

Aber ja, im Prinzip ist die Idee gut.

Answer 4

gute frage, frage josh bloch. Ich habe dieses Konzept als ein RFE in Java 7 eingereicht, aber es wurde fallengelassen, ich glaube, der Grund war etwas Leistungsbezogenes. Ich stimme zu, hätte aber getan werden sollen.

Answer 5

Ich vermute, dies wurde nicht getan, weil es hashCode-Caching verhindern würde?

Ich habe versucht, eine generische Map-Lösung zu erstellen, in der alle Schlüssel stillgelegt sind. Es stellte sich heraus, dass der Wrapper das Wrapped-Objekt, den zwischengespeicherten Hash-Code und einen Verweis auf die Callback-Schnittstelle, die für die Überprüfung der Gleichheit zuständig ist, enthalten musste. Dies ist offensichtlich nicht so effizient wie die Verwendung einer Wrapperklasse, bei der Sie nur den ursprünglichen Schlüssel plus ein weiteres Objekt zwischenspeichern müssten (siehe Hazzens-Antwort).

(Ich stieß auch auf ein Problem in Bezug auf Generics, die Get-Methode akzeptiert Object als Eingabe, so dass die Callback-Schnittstelle für Hashing eine zusätzliche instanceof-Prüfung durchführen müsste. Entweder das, oder die Kartenklasse würde die Klasse seiner Schlüssel zu kennen.)

Answer 6

Dies ist eine interessante Idee, aber es ist absolut für die Leistung horrend. Der Grund dafür ist ziemlich grundlegend für die idea of a hashtable: die Bestellung kann nicht verlassen werden. Hashtables sind sehr schnell (constant time), da sie Elemente in der Tabelle indexieren: indem sie einen pseudo-eindeutigen Ganzzahl-Hash für dieses Element berechnen und auf diesen Ort in einem Array zugreifen. Es berechnet buchstäblich einen Speicherplatz im Speicher und speichert das Element direkt.

Dies steht im Gegensatz zu einem ausgewogenen binären Suchbaum (TreeMap), der bei der Wurzel beginnen und jedes Mal nach dem gewünschten Knoten arbeiten muss, wenn eine Suche erforderlich ist. Wikipedia hat einige more in-depth analysis. Zusammenfassend ist die Effizienz einer Baumkarte abhängig von einer konsistenten Ordnung, daher ist die Reihenfolge der Elemente vorhersehbar und vernünftig. Aufgrund des Leistungseinbruchs, der durch den "traverse to your destination" -Ansatz verursacht wird, können BSTs jedoch nur O (log (n)) Leistung bereitstellen. Bei großen Karten kann dies ein erheblicher Leistungseinbruch sein.

Es ist möglich, eine konsistente Reihenfolge auf einer Hashtabelle zu erzwingen, aber dazu müssen ähnliche Techniken wie verwendet und die Reihenfolge manuell verwaltet werden. Alternativ können zwei separate Datenstrukturen intern gepflegt werden: eine Hashtabelle und ein Baum. Die Tabelle kann für Suchvorgänge verwendet werden, während der Baum für die Iteration verwendet werden kann. Das Problem besteht natürlich darin, dass mehr als doppelt so viel Speicher benötigt wird. Außerdem sind Einfügungen nur so schnell wie der Baum: O (log (n)). Concurrent-Tricks können dies ein wenig nach unten bringen, aber das ist keine zuverlässige Leistungsoptimierung.

Kurz gesagt, Ihre Idee klingt wirklich gut, aber wenn Sie tatsächlich versuchten, es zu implementieren, würden Sie sehen, dass dies massive Leistungseinschränkungen auferlegen würde. Das endgültige Urteil lautet (und war seit Jahrzehnten): Wenn Sie Leistung benötigen, verwenden Sie eine Hashtabelle; Wenn Sie eine Bestellung aufgeben müssen und mit eingeschränkter Leistung leben können, verwenden Sie einen ausgewogenen binären Suchbaum. Ich fürchte, es gibt wirklich keine effiziente Kombination der beiden Strukturen, ohne einige der Garantien des einen oder anderen zu verlieren.

Answer 7

Es gibt eine solche Funktion in com.google.common.collect.CustomConcurrentHashMap, leider gibt es derzeit keine öffentliche Möglichkeit, wie Sie die Equivalence (ihre Hasharator) einstellen.Vielleicht sind sie noch nicht damit fertig, vielleicht halten sie das Feature nicht für ausreichend nützlich. Fragen Sie nach der guava mailing list.

Ich frage mich, warum es noch nicht passiert ist, wie es in dieser talk vor über zwei Jahren erwähnt wurde.

Answer 8

Ein bisschen spät für Sie, aber für zukünftige Besucher, könnte es wissenswert sein, dass Commons-Sammlungen eine AbstractHashedMap (in 3.2.1 und mit Generika in 4.0) hat. Sie können diese geschützten Methoden überschreiben, um das gewünschte Verhalten zu erreichen:

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

Eine beispielhafte Implementierung einer solchen alternativen HashedMap ist commons-Sammlungen eigenen IdentityMap (nur bis 3.2.1 als Java hat its own seit 1.4).

Dies ist nicht so leistungsstark wie die Bereitstellung einer externen "Hasharator" an eine Map Instanz. Sie müssen für jede Hashing-Strategie eine neue Map-Klasse implementieren (Composition/Vererbung schlägt zurück ...). Aber es ist immer noch gut zu wissen.

Answer 9

HashingStrategy ist das Konzept, das Sie suchen. Es ist eine Strategie-Schnittstelle, mit der Sie benutzerdefinierte Implementierungen von Equals und Hashcode definieren können.

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

Sie können keine HashingStrategy mit dem in HashSet oder HashMap gebaut verwenden. GS Collections enthält ein java.util.Set namens UnifiedSetWithHashingStrategy und eine java.util.Map namens UnifiedMapWithHashingStrategy.

Schauen wir uns ein Beispiel an.

public class Data 
{ 
    private final int id; 

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

    public int getId() 
    { 
     return id; 
    } 

    // No equals or hashcode 
} 

Hier ist, wie Sie ein UnifiedSetWithHashingStrategy einrichten könnten und es verwenden.

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

Warum nicht einfach eine Map verwenden? UnifiedSetWithHashingStrategy verwendet die Hälfte des Speichers eines UnifiedMap, und ein Viertel der Speicher eines HashMap. Und manchmal haben Sie keinen bequemen Schlüssel und müssen einen synthetischen Schlüssel erstellen, wie ein Tupel. Das kann mehr Speicher verschwenden.

Wie führen wir Nachschlagevorgänge durch? Denken Sie daran, dass Sätze , aber nicht get() haben. UnifiedSetWithHashingStrategy implementiert Pool zusätzlich zu Set, so implementiert es auch eine Form von get().

Hier ist ein einfacher Ansatz zur Behandlung von Groß- und Kleinbuchstaben.

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

Dies zeigt die API, aber es ist nicht für die Produktion geeignet. Das Problem ist, dass die HashingStrategy ständig an String.toLowerCase() delegiert, was eine Reihe von Garbage Strings erzeugt. So können Sie eine effiziente Hashing-Strategie für Zeichenfolgen ohne Beachtung der Groß- und Kleinschreibung erstellen.

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

Hinweis: Ich bin ein Entwickler auf GS-Kollektionen.