Se non utilizzo mai HashSet, dovrei comunque implementare GetHashCode?

Question

Non ho mai bisogno di memorizzare oggetti in una tabella hash. Il motivo è duplice:

• venire con una buona funzione di hash è difficile e soggetto a errori.
• un albero AVL è quasi sempre abbastanza veloce, e richiede semplicemente un predicato di ordine rigoroso, che è molto più facile da implementare.

L'operazione Equals(), d'altra parte, è una funzione molto utilizzata.

Quindi mi chiedo se sia necessario implementare GetHashCode (che non ho mai bisogno) quando si implementa la funzione Equals (che spesso ho bisogno)?

Answer 1

il mio consiglio - se non si desidera utilizzarlo, eseguire l'override it e throw new NotImplementedException(); in modo che tu possa vedere dove ne hai avuto bisogno.

Answer 2

Non è necessario implementarlo. Se scrivi il tuo metodo Equals(), ti consiglio di utilizzare alcune implementazioni GetHashCode che non interrompano però HashSet. Ad esempio, è possibile restituire un valore statico (in genere 42). Le prestazioni di HashSet si ridurranno notevolmente, ma almeno funzionerà ancora - non saprai mai chi utilizzerà/modificherà/manterrà il tuo codice in futuro. (Edit: si consiglia di registrare un avviso se una classe viene utilizzata in una struttura di hash per i problemi di prestazioni primi spot)

EDIT: non solo usare XOR per combinare codici hash delle vostre proprietà

È già stato detto da altri che puoi semplicemente combinare i codici hash di tutte le tue proprietà. Invece di usare solo XOR, incoraggerei comunque a moltiplicare i risultati. XOR può generare un valore 0 se entrambi i valori sono uguali (ad esempio 0xA^0xA == 0x0). Questo può essere facilmente migliorato utilizzando 0xA * 0xA, 0xA * 31 + 0xA o 0xA^(0xA * 31).

Tuttavia, l'intento della mia risposta è che qualsiasi funzione di hash è migliore di quella che non è coerente con gli uguali - anche se restituisce solo un valore statico. Seleziona semplicemente un sottoinsieme di proprietà (da none a tutti) che usi per l'uguaglianza e genera i risultati insieme. Mentre si selezionano le proprietà per il codice hash, preferisco quei piccoli sottoinsiemi che combinazioni sono piuttosto unici (es. Nome, cognome, compleanno - non è necessario aggiungere l'intero indirizzo)

Answer 3

Se si utilizza Dictionary o SortedList e si sostituisce Equals, è necessario disporre di una funzione di hash, altrimenti si interromperanno. Equals viene anche utilizzato in tutto il luogo nel BCL e se qualcun altro utilizza i tuoi oggetti si aspetta che GetHashCode si comporti in modo ragionevole.

Si noti che una funzione di hash non deve essere così complicata. Una versione base consiste nel prendere l'hash di qualunque variabile membro che si sta usando per l'uguaglianza, moltiplicare ciascuna con un numero coprime separato e XOR insieme.

Answer 4

Fornire un adeguato funzione di hash è non difficile. Molto spesso, è sufficiente un semplice XOR dei risultati di GetHashCode() di tutti i campi.

Answer 5

Penso che ti sbagli se ritieni che implementare un rigoroso predicato ordine sia molto più semplice da implementare di una funzione hash: deve gestire un numero elevato di casi limite (valori nulli, gerarchie di classi). E le funzioni hash aren't that difficult, davvero.

Answer 6

Se si esegue l'override di uguali, è necessario eseguire l'override di GetHashCode() da MSDN: "È consigliabile che qualsiasi classe che esegue l'override di Equals sovrascriva anche System.Object.GetHashCode." http://msdn.microsoft.com/en-us/library/ms173147.aspx

Le due funzioni devono corrispondere nel senso che se due oggetti sono uguali devono avere lo stesso valore di hash. Ciò non significa che se due oggetti hanno lo stesso hash dovrebbero essere uguali. Non è necessario un algoritmo hash troppo complesso, ma dovrebbe tentare di distribuire bene attraverso lo spazio intero.

Answer 7

Un albero AVL sarà molto più lento di un hashtable. Se hai a che fare solo con pochi elementi, non sarà un problema. Gli hashtables hanno O (1) inserimenti, eliminazioni e ricerche, ma un albero AVL ha operazioni O (log (n)).

Vorrei andare avanti e sostituire GetHashCode e Equals per due motivi.

• Non è davvero così difficile ottenere una distribuzione decente utilizzando un'implementazione XOR banale.
• Se le tue classi fanno parte di un'API pubblica, qualcun altro potrebbe volerle archiviare in una tabella hash.

Inoltre, devo mettere in discussione la scelta di BST. Gli alberi AVL sono un po 'fuori moda in questi giorni. Esistono altri BST più moderni che sono più facili da implementare e funzionano altrettanto bene (a volte meglio). Se davvero hai bisogno di una struttura dati che mantenga l'ordine, considera queste alternative.

• Red Black Tree - Già implementato da SortedDictionary.
• Skip List
• Scapegoat Tree
• Splay Tree

---

La strategia XOR ha un problema associatività sottile che può causare collisioni in alcuni casi dal a^b = b^a. C'è una soluzione da Effective Java che ha ottenuto un riconoscimento di tipo cult che è abbastanza semplice da implementare.