Karte, die es ermöglicht, den equals-Komparator und die Hashing-Funktion getrennt zu liefern

Question

Beim Versuch, Polynome zu modellieren, insbesondere deren Multiplikation, stoße ich auf das folgende Problem. Bei der Multiplikation werden die einzelnen Monome der beiden Polynome multipliziert und es kann natürlich passieren, dass ich (3x^2y + 5xy^2) * (x + y) habe. Das Ergebnis enthält 3x^2 y^2 und 5 x^2 y^2, die ich sofort durch Addition kombinieren möchte.

Natürlich würde ich gerne den Teil x^2 y^2 des Monomials als Schlüssel in einer (Hash) Map verwenden, um die verschiedenen Koeffizienten (3 und 5 im Beispiel) zu addieren. Aber das Monom-Objekt, wie ich es mir vorstelle, sollte natürlich auch den Koeffizienten enthalten, der nicht Teil des Kartenschlüssels sein sollte.

Natürlich könnte ich equals/hashcode des monomial object schreiben, so dass sie den Koeffizienten ignorieren. Aber das fühlt sich einfach so falsch an, denn mathematisch ist ein Monom eindeutig nur gleich einem anderen, wenn auch die Koeffizienten gleich sind.

Die Einführung eines koeffizientenfreien monomalen Objekts für Zwischenoperationen sieht auch nicht richtig aus.

Anstatt die Karte zu verwenden, könnte ich eine Liste verwenden und eine binäre Suche mit einem dedizierten Komparator verwenden, der den Koeffizienten ignoriert.

Kurz, um eine Karte zu implementieren, die nicht den gleichen/hashcode der Schlüssel verwendet, sondern einen dedizierten, gibt es bessere Ideen, wie man die Monome zusammenfließen kann?

Answer 1

Da die JDK-Implementierung von [Linked]HashMap Sie nicht erlaubt die equals/hashCode Implementierung außer Kraft zu setzen, die einzigen anderen Möglichkeiten sind:

• ein Wickel Objekt wie folgt:

  class A { 
      private final String fieldA; // equals/hashCode based on that field. 
      private final String fieldB; // equals/hashCode based on that field. 
  } 
  
  class B { 
      private A a; 
      public int hashCode() {return a.fieldA.hashCode();} 
      public boolean equals(Object o) {... the same ... } 
  } 
  
  Map<B, Value> map = new HashMap<B, Value>(); 
  map.put(new B(new A("fieldA", "fieldB")), new Value(0)); 
  

  Nun, mit mehr Getter/Konstruktoren.

  Dies kann ärgerlich sein, und vielleicht gibt es eine Bibliothek (wie Guava), die eine equals/hashCode-Methode ermöglicht, wie Sie eine ComparatorTreeMap geben können.

  Unten finden Sie eine Beispielimplementierung, die zeigt, was zu tun ist, um eine vorhandene Karte zu dekorieren.

• Verwenden Sie eine TreeMap mit einer spezifischen Comparator. Die andere Antwort zeigt es, aber ich würde sagen, Sie müssen eine Comparator richtig definieren, weil dies zu Problemen mag: Wenn Sie compareTo Methode gibt 0 zurück, wenn die Gleichheit erreicht ist, und 1 in anderen Fall, bedeutet dies, dass es keine natürliche Bestellung. Sie sollten versuchen, einen zu finden oder das Wrapper-Objekt zu verwenden.

---

Wenn Sie die Herausforderung annehmen wollen, können Sie eine einfache Implementierung mit Delegation/Dekoration über einen anderen HashMap (dies könnte eine andere Art von Karte sein, wie LinkedHashMap) erstellen:

public class DelegatingHashMap<K,V> implements Map<K,V> { 
    private final BiPredicate<K,Object> equalsHandler; 
    private final IntFunction<K> hashCodeHandler; 
    private final Map<Wrapper<K>,V> impl = new HashMap<>(); 

    public DelegatingHashMap(
    BiPredicate<K,Object> equalsHandler, 
    IntFunction<K> hashCodeHandler 
) { 
    this.equalsHandler = requireNonNull(equalsHandler, "equalsHandler"); 
    this.hashCodeHandler= requireNonNull(hashCodeHandler, "hashCodeHandler"); 
    } 

    public Object get(K key) { 
    Wrapper<K> wrap = new Wrapper<>(key); 
    return impl.get(wrap); 
    } 

    ... 

    static class Wrapper<K2> { 
    private final K2 key; 
    private final BiPredicate<K> equalsHandler; 
    private final IntFunction<K> hashCodeHandler; 
    public int hashCode() {return hashCodeHandler.apply(key);} 
    public boolean equals(Object o) { 
     return equalsHandler.test(key, o); 
    } 
    } 
} 

Und der Code mit Hilfe der Karte:

Aber vielleicht die beste (fo r der Speicher) wäre, die HashMap um den Handler direkt anstelle eines Wrappers zu schreiben.

Answer 2

Sie könnten ein TreeMap mit einem benutzerdefinierten Komparator verwenden:

TreeMap(Comparator<? super K> comparator) 

Konstruieren eine neue, leere Treemap ordnete den gegebenen Komparator nach.

(Source)

Answer 3

denke ich, es besser sein kann, das Monom in zwei Teile zu trennen: die Koeffizienten und die Variable. Auf diese Weise können Sie den variablen Teil in Ihrer Karte als Schlüssel und den Koeffizienten als Wert verwenden (der dann aktualisiert werden kann).

All Code sollte Implementierungsdetails in einem Polynomial Objekt

Ich bin nicht sicher, warum Sie ein Koeffizient frei monomial denken nicht gut aussieht. Sie müssen das Objekt nicht nach außen freilegen, wenn Sie es nicht möchten. Aber es könnte eine gute Möglichkeit sein, Getter auf Ihre Polynomial zu bekommen, um die Koeffizienten für jedes Monom zu erhalten.

Answer 4

Betrachten Sie eine TreeMap, die eine SortedMap und somit auch eine Map ist. Sie können seinem Konstruktor einen Comparator bereitstellen. Die sortierte Karte verwendet das Comparator zum Sortieren der Kartenschlüssel. Aber wichtig, für Ihren Fall wird es konsuder Schlüssel gleich sein, wenn die Comparator 0 zurückgibt. In Ihrem Fall wird das eine Comparator erfordern, die nicht mit Gleichgestellten konsistent ist, die Ihnen Probleme verursachen könnten wenn Sie nicht vorsichtig sind.

Eine weitere Option ist die Einführung einer anderen Klasse, die als Adapter für eine Mononomial dient und als Kartenschlüssel mit den Eigenschaften verwendet werden kann, die Sie verdienen.

Answer 5

+1 zu allen Antworten, weil jeder half mir ein bisschen, um dies zu sortieren, indem Sie das Problem aus einem etwas anderen Blickwinkel betrachten. Während ich sie las, erkannte ich, dass die Antwort einfacher ist als ich dachte. Vielleicht hätte ich schon in meiner Frage betont, dass jedes Monom natürlich eine Liste von Potenzen von Variablen enthält, zum Beispiel [x^5, y^7, z]. Dies ist genau der Teil des Monoms, den ich als Schlüssel in der Karte verwenden muss. Ich habe es leicht verfügbar, keine Notwendigkeit für einen Wrapper um das Monom, keine Notwendigkeit, gleich oder hashCode des Monomial zwicken. Ich muss nur sicherstellen, dass

a) diese Listen normalisiert sind, zum Beispiel, indem sie sortiert und b), dass die "Potenzen der Variablen" Objekt hat einen richtigen HashCode und equals.

Vor diesem Hintergrund nehme ich an, dass jede solche Liste (ich halte sie unveränderlich) für einen richtigen Kartenschlüssel sorgt. Dann ist es einfach, Monome zu addieren, die sich aus der Multiplikation mit Polynomen ergeben.