Perché l'utilizzo del metodo hashCode di HashSet non è specificato nell'API?

5

Stavo provando a eseguire il debug del mio codice che utilizza HashSet e cercando in SO, ho scoperto che avevo bisogno di sovrascrivere anche il metodo hashCode . La parte strana è, controllando l' API correlata , Non ho visto alcuna parte in esso menzionando il metodo hashCode . Citando la definizione del metodo add di HashSet come visto nell'API:

public boolean add(E e)

Adds the specified element to this set if it is not already present. More formally, adds the specified element e to this set if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2)). If this set already contains the element, the call leaves the set unchanged and returns false.

Ora nella citazione sopra, non vedo da nessuna parte che menzioni il metodo hashCode . Non dovrebbe essere la frase corretta:

... if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2)) AND if this set contains no element e2 such that (e==null ? e2==null : e.hashCode() == e2.hashCode()).

Ora se dici che: "Se o1.equals(o2) restituisce true, o1.hashCode() == o2.hashCode() DEVE anche valutare su true.", quindi vorrei fare tre domande:

  1. Dove viene specificato questo fatto? (in generale o nell'API)

  2. Anche se questo fatto è specificato da qualche parte, dove nell'API è specificato che HashSet fa uso del metodo hashCode ?

  3. Se questo fatto è effettivamente corretto, perché il compilatore non impone l'override del metodo hashCode , ogni volta che il metodo equals viene sovrascritto?

posta Utku 07.12.2014 - 00:03
fonte

5 risposte

8
  1. nella documentazione dello stesso hashcode :

Returns a hash code value for the object. This method is supported for the benefit of hash tables such as those provided by HashMap.

The general contract of hashCode is:

  • Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
  • If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
  • It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.
  1. non che posso trovare, ma hashcode è specificamente lì per il supporto delle tabelle hash come detto nella documentazione.
risposta data 07.12.2014 - 00:10
fonte
3

Le specifiche dell'hashCode nell'API sono alcuni passaggi profondi da HashSet:

  • HashSet Vedi anche - > HashMap ("Questa classe implementa l'interfaccia Set , supportata da una tabella hash (in realtà un'istanza HashMap ).")
  • HashMap Vedi anche: - > Object.hashCode ()
  • Object # hashCode ()

Lì, si legge:

Returns a hash code value for the object. This method is supported for the benefit of hash tables such as those provided by HashMap.

Il compilatore non conosce o si preoccupa delle relazioni tra oggetti o metodi. D'altra parte, ci sono diversi strumenti di analisi statica a cui fa cura:

Findbug La classe definisce equals () ma non hashCode () :

This class overrides equals(Object), but does not override hashCode(). Therefore, the class may violate the invariant that equal objects must have equal hashcodes.

Findbug La classe definisce equals () e utilizza Object.hashCode ()

This class overrides equals(Object), but does not override hashCode(), and inherits the implementation of hashCode() from java.lang.Object (which returns the identity hash code, an arbitrary value assigned to the object by the VM). Therefore, the class is very likely to violate the invariant that equal objects must have equal hashcodes.

If you don't think instances of this class will ever be inserted into a HashMap/HashTable, the recommended hashCode implementation to use is:

public int hashCode() {
    assert false : "hashCode not designed";
    return 42; // any arbitrary constant will do
}

PMD OverrideBothEqualsAndHashcode

Override both public boolean Object.equals(Object other), and public int Object.hashCode(), or override neither. Even if you are inheriting a hashCode() from a parent class, consider implementing hashCode and explicitly delegating to your superclass.

CheckStyle EqualsHashCode

Checks that classes that override equals() also override hashCode().

Rationale: The contract of equals() and hashCode() requires that equal objects have the same hashCode. Therefore, whenever you override equals() you must override hashCode() to ensure that your class can be used in hash-based collections.

Alcuni IDE possono avere anche strumenti di analisi o generatori statici integrati per creare equazioni e hashcode - a volte come parte dello stesso passo (questi sono i campi di interesse - poof c'è il codice).

    
risposta data 07.12.2014 - 00:19
fonte
2

... if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2)) AND if this set contains no element e2 such that (e==null ? e2==null : e.hashCode() == e2.hashCode()).

L'affermazione precedente non è corretta. È e dovrebbe essere possibile aggiungere un oggetto e1 a un HashSet o un Set in generale, dove il set contiene un elemento e2, che soddisfa e1.hashCode() == e2.hashCode() && e1.equals(e2) == false .

Puoi facilmente creare esempi per questo: Immagina una classe Persona con gli attributi nome, cognome e città residente. Il metodo equals confronta tutti gli attributi e il metodo hashCode utilizza il codice hash della città residente. Il contratto di uguale e hashCode è soddisfatto, ma con il contratto di aggiunta di cui sopra, non sarebbe possibile aggiungere persone a un set che vive nella stessa città.

La documentazione di HashSet non indica esplicitamente l'uso del metodo hashCode (considererei un dettaglio di implementazione.) La cosa importante che devi sapere è che HashSet soddisfa il contratto di Set). Tuttavia, vi è un suggerimento nella documentazione :

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

    
risposta data 07.12.2014 - 11:35
fonte
1
  1. Where is that fact specified? (in general, or in the API)

È specificato chiaramente nel documentazione del metodo .equals() .

Note that it is generally necessary to override the hashCode method whenever this method is overridden, so as to maintain the general contract for the hashCode method, which states that equal objects must have equal hash codes.

Esegui l'override del metodo .equals() senza guardare la documentazione del metodo che stavi ignorando e hai rotto i suoi requisiti.

  1. Even if that fact is specified somewhere, where in the API it is specified that HashSet makes use of the hashCode method?

Non ha bisogno di essere specificato da nessuna parte. .hashCode() è un metodo su Object e quindi tutti gli oggetti ce l'hanno. Qualsiasi classe è autorizzata a utilizzarla.

Quella HashSet utilizza .hashCode() è un dettaglio di implementazione, non parte della sua API. L'API di HashSet è sostanzialmente uguale all'API dell'interfaccia Set implementata. HashSet non aggiunge requisiti aggiuntivi sul tipo, non più di Set . Il contratto Set si assicura che non ci siano due elementi .equals() nel set e che la ricerca dei metodi di ricerca utilizzi .equals() . HashSet fa lo stesso. HashSet utilizza .hashCode() come parte di tali operazioni, ma dovrebbe essere in grado di farlo in modo sicuro poiché .hashCode() deve essere coerente con .equals() come parte del contratto di .equals() .

  1. If that fact is indeed correct, why isn't the compiler enforces overriding the hashCode method, whenever the equals method is overridden?

Non c'è alcun meccanismo nella lingua per far rispettare questo.

    
risposta data 09.12.2014 - 10:34
fonte
0

In assenza di una promessa esplicita di non farlo, qualsiasi raccolta basata sull'uguaglianza può usare hashCode se è così incline a decidere rapidamente che le cose non corrispondono (notare che le raccolte ordinate che riguardano oggetti di uguale valore come matching non sarebbero autorizzati a farlo, dal momento che gli oggetti possono avere uguale rank e tuttavia essere diseguali). Inoltre, non vi è alcuna garanzia che le implementazioni di hashset chiameranno sempre hashCode. Sarebbe legittimo avere un'implementazione hashSet che non si è preoccupata di chiamare hashCode su qualsiasi cosa fino a quando non conteneva un certo numero di elementi. Ciò potrebbe essere utile in alcuni contesti di raccolta nidificata che producono molte istanze di raccolta che non aggiungono mai molti elementi. Pertanto, il nome hashSet in pratica dice che le prestazioni saranno legate alla qualità della funzione hash, ma ciò non significa che è "l'unica cosa che può o lo userà.

    
risposta data 23.03.2015 - 16:40
fonte

Leggi altre domande sui tag