Warum nicht eine externe Schnittstelle erlaubt hashCode zu schaffen / gleich für eine HashMap?

StackOverflow https://stackoverflow.com/questions/214136

Frage

Mit einem TreeMap ist es trivial, eine benutzerdefinierte Comparator zu schaffen, überschreiben damit die von Comparable erstellte Objekte Semantik der Karte hinzugefügt. HashMaps jedoch nicht auf diese Weise gesteuert werden; die Funktionen Hash-Werte und Gleichheit prüft die Bereitstellung nicht ‚Seite geladen‘ werden.

Ich vermute, dass es sowohl einfach sein würde, und nützlich, um eine Schnittstelle zu entwerfen und diese in HashMap nachzurüsten (oder eine neue Klasse)? 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) { ... }
  }

Die Groß- und Kleinschreibung Map Problem bekommt eine triviale Lösung: 

 new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY);

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

Ist der Ansatz in jedem vorhandenen (nicht JRE) Libs verwendet? (Versuchte google, kein Glück.)

EDIT: Nizza Abhilfe durch hazzen vorgestellt, aber ich fürchte, das ist die Abhilfe, die ich ... zu vermeiden, bin versucht;)

EDIT: Changed Titel nicht mehr "Komparator" nennen; Ich vermute, dass dies ein wenig verwirrend war.

EDIT: akzeptierte Antwort mit Bezug auf die Leistung; würde gerne eine konkretere Antwort!

EDIT: Es ist eine Implementierung; siehe akzeptierte Antwort unten.

EDIT: umformuliert der erste Satz, um anzuzeigen, deutlicher, dass es die Seitenbeladung ist ich bin nach (und nicht der Bestellung, Bestellung nicht in HashMap gehört)

.
War es hilfreich?

Lösung 4

Trove4j hat das Merkmal, ich bin nach und sie nennen es Strategien Hashing.

Die Karte hat eine Implementierung mit verschiedenen Einschränkungen und damit unterschiedlichen Voraussetzungen, so bedeutet dies nicht, implizit, dass eine Implementierung für Java „native“ HashMap machbar wäre.

Andere Tipps

Ein bisschen spät für Sie, aber für zukünftige Besucher, könnte es sich lohnen, zu wissen, dass commons-Sammlungen eine AbstractHashedMap hat (in 3.2.2 und mit Generika in 4.0 ). 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.2 als Java hat seine eigenen seit 1.4).

Das ist nicht so mächtig wie eine externe „Hasharator“ auf eine Map Instanz bereitstellt. Sie haben eine neue Map-Klasse für jede Hashing-Strategie umzusetzen (Komposition vs. Erbe zurückschlägt ...). Aber es ist immer noch gut zu wissen.

.NET hat dies über IEqualityComparer (für einen Typ, der zwei Objekte vergleichen) und IEquatable (für eine Art, die sich auf eine andere Instanz vergleichen).

In der Tat, ich glaube, es war ein Fehler, der Gleichheit und der Hashcodes in java.lang.Object oder System.Object überhaupt zu definieren. Gleichheit insbesondere ist schwer, in einer Art und Weise zu definieren, die Sinn mit Vererbung macht. Ich halte Sinn, darüber zu bloggen ...

Aber ja, im Grunde die Idee ist Klang.

HashingStrategy ist das Konzept Sie suchen. Es ist eine Strategie-Schnittstelle, die Sie benutzerdefinierte Implementierungen von equals und hashcode definieren. 

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

Sie können keine HashingStrategy mit dem eingebauten in HashSet oder HashMap verwenden. GS Sammlungen eine java.util.Set umfasst genannt UnifiedSetWithHashingStrategy und ein java.util.Map UnifiedMapWithHashingStrategy genannt.

Lassen Sie 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 eine UnifiedSetWithHashingStrategy einrichten könnten, und verwenden Sie es. 

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 ein Map benutzen? UnifiedSetWithHashingStrategy verwendet die Hälfte des Speichers eines UnifiedMap, und ein Viertel des Speichers eines HashMap. Und manchmal haben Sie nicht einen bequemen Schlüssel und haben ein synthetisches, eines erstellen, wie ein Tupel. Das kann mehr Speicher verschwenden.

Wie führen wir Lookups? Denken Sie daran, dass Sets haben contains(), aber nicht get(). UnifiedSetWithHashingStrategy implementiert Pool neben Set, so dass es implementiert auch eine Form von get().

Hier ist ein einfacher Ansatz Groß- und Kleinschreibung Strings zu handhaben. 

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, von der API, aber es ist für die Produktion nicht geeignet. Das Problem ist, dass der HashingStrategy ständig Delegierten String.toLowerCase(), die einen Haufen Müll Strings erzeugt. Hier ist, wie Sie eine effiziente Hashing-Strategie für die Groß- und Kleinschreibung Strings erstellen können. 

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 Sammlungen

Hinweis: Wie bei allen anderen Antworten erwähnt, HashMaps keine explizite Ordnung hat. Sie erkennen nur „Gleichheit“. Immer einen Auftrag aus einer Hash-basierten Datenstruktur ist bedeutungslos, da jedes Objekt in eine Hash gedreht wird -. Im wesentlichen eine Zufallszahl

Sie können jederzeit eine Hash-Funktion für eine Klasse schreiben (und oft muss), so lange wie Sie es vorsichtig tun. Das ist eine harte Sache richtig zu tun, weil Hash-basierte Datenstrukturen stützen sich auf eine zufällige, gleichmäßige Verteilung der Hash-Werte. In Effective Java gibt es eine große Menge an Text, um ein Hash-Verfahrens mit gutem Verhalten richtig gewidmet Umsetzung.

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

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

gute Frage, fragen Sie josh bloch. i vorgelegt dieses Konzept als RFE in Java 7, aber es wurde fallen gelassen, ich glaube, der Grund war etwas im Zusammenhang mit Leistung. Ich bin damit einverstanden, sollte aber getan worden ist.

Ich vermute, dass dies nicht geschehen ist, weil es hashCode Caching verhindern?

Ich habe versucht, eine generische Karte Lösung zu schaffen, in der alle Tasten stumm gewickelt sind. Es stellte sich heraus, dass die Umhüllung des umhüllten Objekt halten würde, die im Cache gespeicherte hashCode und einen Verweis auf die Callback-Schnittstelle für Gleichstellung Kontrollen. Dies ist offensichtlich nicht so effizient wie eine Wrapper-Klasse, wo Sie würden nur den Originalschlüssel cachen haben plus ein weiteren Objekt (siehe hazzens Antwort).

(I auch ein Problem im Zusammenhang mit Generika gestoßen, die get-Methode Objekt als Eingabe akzeptiert, so dass die Callback-Schnittstelle für Hashing verantwortlich wäre eine zusätzliche instanceof-Prüfung durchzuführen Entweder das, oder die Karte Klasse müßte. kennen die Klasse seiner Tasten.)

Dies ist eine interessante Idee, aber es ist absolut entsetzlich für die Leistung. Der Grund hierfür ist ganz wesentlich für die Idee einer Hash-Tabelle : die Bestellung nicht verlassen kann, auf . Hashtables sind sehr schnell ( konstante Zeit ) wegen der Art und Weise, in der sie Index Elemente in der Tabelle : durch eine pseudo-eindeutigen ganzzahligen Hash für dieses Element Rechen- und diese Position in einem Array zugreift. Es ist buchstäblich eine Stelle im Speicher Berechnung und das Element direkt zu speichern.

Dies steht im Gegensatz mit einem ausgeglichenen binären Suchbaum (TreeMap), die an der Wurzel beginnen muss und seine Art und Weise arbeiten, bis auf den gewünschten Knoten jedes Mal, wenn ein Lookup erforderlich ist. Wikipedia hat einige tiefer gehende Analyse . Um es zusammenzufassen, die Effizienz eines Treemap auf einer konsistenten Ordnung abhängig ist, damit die Reihenfolge der Elemente ist vorhersehbar und gesund. Doch wegen der Performance-Einbußen durch die auferlegte "Fahren auf Ihrem Ziel" -Ansatz, BSTs sind nur in der Lage zu liefern O (log (n)) Leistung. Für große Karten, kann dies ein erheblicher Performance-Hit.

Es ist möglich, eine einheitliche Ordnung auf einer Hash-Tabelle zu verhängen, aber so zu tun, beinhaltet Techniken ähnlich wie LinkedHashMap und manuell die Aufrechterhaltung der Ordnung verwenden. eine Hash-Tabelle und einen Baum: Alternativ können zwei separate Datenstrukturen können intern gehalten werden. Die Tabelle kann für Lookups verwendet werden, während kann der Baum für Iteration verwendet werden. Das Problem ist natürlich verwendet mehr als den erforderlichen Speicher zu verdoppeln. Auch Einfügungen sind nur so schnell wie der Baum: O (log (n)). Concurrent Tricks können dies ein wenig bringen, aber das ist keine zuverlässige Performance-Optimierung.

Kurz gesagt, Ihre Idee Sounds wirklich gut, aber wenn Sie es tatsächlich zu implementieren versucht, würden Sie das tun würde sehen so massive Leistungsbeschränkungen auferlegen. Das endgültige Urteil ist (und ist seit Jahrzehnten): Wenn Sie die Leistung benötigen, eine Hash-Tabelle verwenden; wenn Sie Bestellung benötigen und mit verminderter Leistung leben können, verwenden Sie einen ausgewogenen binären Suchbaum. Ich fürchte, es gibt wirklich keine effizient die beiden Strukturen kombiniert, ohne einige der Garantien von dem einen oder anderen zu verlieren.

Es ist ein solches Feature in com.google.common.collect.CustomConcurrentHashMap, leider gibt es derzeit keine öffentliche Art und Weise, wie die Equivalence einzustellen (ihre Hasharator). Vielleicht sind sie noch nicht damit getan, vielleicht betrachten sie die Funktion nicht nützlich genug zu sein. Fragen Sie an der Guave Mailingliste .

Ich frage mich, warum es noch nicht geschehen sein, da es in dieser Rede erwähnt wurde mehr als zwei Jahre.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top