C # Come selezionare un codice hash per una classe che viola il contratto Equals?

Question

Ho più classi che, per determinati motivi, non seguono il contratto ufficiale Equals . Nel sovrascritto GetHashCode () queste classi restituiscono semplicemente 0 in modo da poter essere utilizzate in una hashmap.

Alcune di queste classi implementano la stessa interfaccia e ci sono hashmap che usano questa interfaccia come chiave. Quindi ho pensato che ogni classe dovrebbe almeno restituire un valore diverso (ma ancora costante) in GetHashCode () .

La domanda è come selezionare questo valore. Devo semplicemente lasciare che la prima classe restituisca 1, la successiva classe 2 e così via? O dovrei provare qualcosa del genere

class SomeClass : SomeInterface {
    public overwrite int GetHashCode() {
        return "SomeClass".GetHashCode();
    }
}

quindi l'hash è distribuito in modo più uniforme? (Devo memorizzare nella cache il valore restituito o il compilatore di Microsoft è in grado di ottimizzarlo?)

Aggiornamento: non è possibile restituire un singolo hashcode per ogni oggetto, poiché Equals viola il contratto. In particolare, mi riferisco a questo problema .

Answer 1

Ho riscontrato questo esatto problema durante la scrittura di una classe vettoriale. Volevo confrontare i vettori per l'uguaglianza, ma le operazioni float danno errori di arrotondamento, quindi volevo un'uguaglianza approssimativa. Per farla breve, l'override è uguale a una cattiva idea a meno che l'implementazione non sia simmetrica, riflessiva e transitiva.

Altre classi supporranno che uguali abbia quelle proprietà, così come le classi che usano quelle classi, e così puoi finire in strani casi. Ad esempio, un elenco potrebbe imporre l'univocità, ma finire con due elementi che valutano come uguali a qualche elemento B.

Una tabella hash è l'esempio perfetto di comportamento imprevedibile quando si infrange l'uguaglianza. Ad esempio:

//Assume a == b, b == c, but a != c
var T = new Dictionary<YourType, int>()
T[a] = 0
T[c] = 1
return T[b] //0 or 1? who knows!

Un altro esempio potrebbe essere un Set:

//Assume a == b, b == c, but a != c
var T = new HashSet<YourType>()
T.Add(a)
T.Add(c)
if (T.contains(b)) then T.remove(b)
//surely T can't contain b anymore! I sure hope no one breaks the properties of equality!
if (T.contains(b)) then throw new Exception()

Suggerisco di usare un altro metodo, con un nome come ApproxEquals. Potresti anche considerare di sovrascrivere l'operatore ==, perché non è virtuale e quindi non verrà utilizzato accidentalmente da altre classi come potrebbe essere Equals.

Se davvero non puoi usare l'uguaglianza di riferimento per la tabella hash, non rovinare le prestazioni dei casi in cui puoi. Aggiungi un'interfaccia IApproxEquals, implementala nella tua classe e aggiungi un metodo di estensione GetApprox al dizionario che enumera le chiavi cercando una approssimativamente uguale e restituisce il valore associato. Puoi anche scrivere un dizionario personalizzato in particolare per i vettori tridimensionali o per qualsiasi cosa ti serva.

Answer 2

Se "viola il contratto Equals", non sono sicuro che dovresti usarlo come chiave.

Qualcosa lo sta usando come chiave, devi davvero ottenere l'hashing giusto ... non è molto chiaro quale sia la logica Equals , ma due valori considerati uguali deve avere lo stesso codice hash. Non è necessario che due valori con lo stesso codice hash siano uguali.

L'uso di una stringa costante non sarà di grande aiuto: i valori verranno suddivisi equamente sui tipi, ma questo è tutto ...

Answer 3

Sono curioso di sapere quale sarebbe il ragionamento per sovrascrivere GetHashCode () e restituire un valore costante. Perché violare l'idea di un hash piuttosto che violare il "contratto"? e non sovrascrivere affatto la funzione GetHashCode () e lasciare l'implementazione predefinita da Object ?

Modifica

Se quello che hai fatto è che puoi far corrispondere i tuoi oggetti in base al loro contenuto piuttosto che al loro riferimento, allora ciò che proponi con classi diverse semplicemente usa costanti diverse può FUNZIONARE, ma è altamente inefficiente. Quello che vuoi fare è inventare un algoritmo di hashing che possa prendere i contenuti della tua classe e produrre un valore che equilibri la velocità con una distribuzione uniforme (ovvero hashing 101).

Suppongo di non essere sicuro di quello che stai cercando ... non esiste un "buono" schema per la scelta di numeri costanti per questo paradigma. Uno non è migliore dell'altro. Prova a migliorare i tuoi oggetti in modo da creare un vero hash.

Answer 4

Quando si verificano collisioni di hash, la HashTable / Dictionary chiama Equals per trovare la chiave che stai cercando. L'uso di un codice hash costante rimuove in primo luogo i vantaggi della velocità dell'utilizzo di un hash: diventa una ricerca lineare.

Stai dicendo che il metodo Equals non è stato implementato secondo il contratto. Cosa intendi esattamente con questo? A seconda del tipo di violazione, la HashTable o il Dizionario saranno semplicemente lenti (ricerca lineare) o non funzioneranno affatto.