Mappa che consente di fornire separatamente il comparatore di uguali e la funzione di hashing

Question

Durante il tentativo di modellare i polinomi, in particolare la loro moltiplicazione, mi imbatto nel seguente problema. Durante la moltiplicazione, i singoli monomi dei due polinomi sono moltiplicati e, naturalmente, può accadere che io abbia (3x^2 y + 5x y^2) * (x + y). Il risultato contiene 3x^2 y^2 e 5 x^2 y^2, che voglio combinare per addizione subito.

Naturalmente mi piacerebbe utilizzare la parte x^2 y^2 del monomio come chiave in una mappa (cancelletto) per sommare i diversi coefficienti (3 e 5 nell'esempio). Ma l'oggetto monomio come lo immagino dovrebbe naturalmente contenere anche il coefficiente, che dovrebbe essere non parte della chiave mappa.

Ovviamente potrei scrivere equals/hashcode dell'oggetto monomiale in modo tale che ignorino il coefficiente. Ma questo sembra proprio sbagliato, perché matematicamente un monomio chiaramente è uguale a un altro se anche i coefficienti sono uguali.

Anche l'introduzione di un oggetto monomio privo di coefficiente per le operazioni intermedie non sembra corretta.

Invece di utilizzare la mappa, è possibile utilizzare un elenco e utilizzare una ricerca binaria con un comparatore dedicato che ignora il coefficiente.

A corto di implementazione di una mappa che non utilizza i tasti 'equals/hashcode, ma uno dedicato, ci sono idee migliori su come fondere i monomiali?

Answer 1

Dal momento che l'attuazione JDK di [Linked]HashMap non ti permette di ignorare l'attuazione equals/hashCode, gli unici altri modi sono:

• un oggetto involucro come questo:

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

  Beh, con più getter/costruttori.

  Questo può essere fastidioso e forse esiste qualche libreria (come Guava) che consente di fornire un metodo equals/hashCode come se fosse possibile fornire uno Comparator a TreeMap.

  Troverete di seguito un'implementazione di esempio che indica cosa fare per decorare una mappa esistente.

• utilizzare uno TreeMap con uno specifico Comparator. L'altra risposta la punto, ma direi che dovrai definire correttamente uno Comparator perché questo potrebbe piacere a problemi: se il metodo compareTo restituisce 0 quando viene raggiunta l'uguaglianza, e 1 nell'altro caso, ciò significa che non c'è ordinazione. Dovresti provare a trovarne uno, o usare l'oggetto wrapper.

---

Se si vuole accettare la sfida, è possibile creare un'implementazione di base utilizzando la delega/decorazione su un altro HashMap (questo potrebbe essere un altro tipo di carta, come LinkedHashMap):

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

E il codice utilizzando la mappa:

Ma forse il migliore (fo r la memoria) sarebbe quello di riscrivere il HashMap per utilizzare direttamente il gestore invece di un wrapper.

Answer 2

È possibile utilizzare un TreeMap con un comparatore personalizzato:

TreeMap(Comparator<? super K> comparator) 

Costruisce una nuova, carta albero vuoto, ordinate in base alla data di confronto.

(Source)

Answer 3

ritengo può essere meglio separare il monomiale in 2 parti: il coefficiente e la variabile. In questo modo è possibile utilizzare la parte variabile nella mappa come chiave e il coefficiente come valore (che può quindi essere aggiornato).

Tutto questo codice dovrebbe essere dettagli di implementazione all'interno di un oggetto Polynomial

io non sono sicuro perché si pensa che un monomia senza coefficiente di non guardare a destra. Non devi esporre l'oggetto all'esterno se non vuoi. Ma potrebbe essere un buon modo di avere getter sul tuo Polynomial per ottenere i coefficienti per ogni monomio.

Answer 4

Considerare l'utilizzo di TreeMap, che è un SortedMap e quindi anche un Map. È possibile fornire un Comparator al suo costruttore. La mappa ordinata utilizzerà quello Comparator per ordinare le chiavi della mappa. Ma soprattutto, per il tuo caso, le chiavi del computer saranno uguali se lo Comparator restituisce 0. Nel tuo caso sarà necessario un Comparator che non è consuetudine con uguale, che potrebbe causare problemi se non stai attento.

Un'altra opzione è quella di introdurre un'altra classe, che funge da adattatore per un Mononomial e può essere utilizzata come una chiave di mappa con le proprietà che si meritano.

Answer 5

+1 anche tutte le risposte, perché ognuna mi ha aiutato un po 'a risolvere questo problema osservando il problema da un'angolazione leggermente diversa. Mentre li leggevo ho capito che la risposta è più semplice di quanto pensassi. Forse avrei dovuto enfatizzare già nella mia domanda, che ogni monomio contiene naturalmente un elenco di poteri di variabili, ad esempio [x^5, y^7, z]. Questa è esattamente la parte del monomio che devo usare come chiave nella mappa. Ce l'ho prontamente disponibile, non c'è bisogno di un involucro attorno al monomio, non c'è bisogno di modificare equals o hashCode del monomio. Devo solo assicurarmi che

a) questi elenchi siano normalizzati, ad esempio mantenendoli ordinati e b) che l'oggetto "Poteri delle variabili" abbia un hashCode corretto e uguale a.

Dato questo, presumo che ciascuna di queste liste (le tengo immutabili) crei una chiave di mappa corretta. Quindi è facile aggiungere come monomi derivanti dalla moltiplicazione dei polinomi.