HashMap utilizza hashCode(), == e equals() per la ricerca di voci. La sequenza di ricerca per una data chiave k è la seguente:
- Usa
k.hashCode() per determinare quali secchio la voce viene memorizzata, se del caso
- se trovato, per ogni voce della chiave
k1 in quel secchio, se k == k1 || k.equals(k1), poi tornare ingresso
- Eventuali altri esiti, senza voce corrispondente
per dimostrare con un esempio, supponiamo che vogliamo creare un s'dove le chiavi sono qualcosa che è 'logicamente equivalente' se hanno lo stesso valore intero, rappresentato dalla classe AmbiguousInteger. Quindi, costruiamo un HashMap, inseriamo una voce, quindi tentiamo di sovrascrivere il suo valore e recuperare il valore per chiave.
class AmbiguousInteger {
private final int value;
AmbiguousInteger(int value) {
this.value = value;
}
}
HashMap<AmbiguousInteger, Integer> map = new HashMap<>();
// logically equivalent keys
AmbiguousInteger key1 = new AmbiguousInteger(1),
key2 = new AmbiguousInteger(1),
key3 = new AmbiguousInteger(1);
map.put(key1, 1); // put in value for entry '1'
map.put(key2, 2); // attempt to override value for entry '1'
System.out.println(map.get(key1));
System.out.println(map.get(key2));
System.out.println(map.get(key3));
Expected: 2, 2, 2
Non escludere hashCode() e equals(): per default Java genera diversi valori hashCode() per oggetti diversi, in modo da HashMap utilizza questi valori per mappare key1 e key2 in diversi secchi. key3 non ha un bucket corrispondente, quindi non ha alcun valore.
class AmbiguousInteger {
private final int value;
AmbiguousInteger(int value) {
this.value = value;
}
}
map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 2, set as entry 2[1]
map.get(key1); // map to bucket 1, get as entry 1[1]
map.get(key2); // map to bucket 2, get as entry 2[1]
map.get(key3); // map to no bucket
Expected: 2, 2, 2
Output: 1, 2, null
Override hashCode() solo:HashMap mappe key1 e key2 nello stesso secchio, ma rimangono voci diverse a causa di entrambe le key1 == key2 e key1.equals(key2) controlli non riescono, come per impostazione predefinita equals() utilizza == di controllo, e si riferiscono a diversi le istanze. key3 non riesce entrambi gli assegni == e equals() contro key1 e key2 e pertanto non ha alcun valore corrispondente.
class AmbiguousInteger {
private final int value;
AmbiguousInteger(int value) {
this.value = value;
}
@Override
public int hashCode() {
return value;
}
}
map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 1, set as entry 1[2]
map.get(key1); // map to bucket 1, get as entry 1[1]
map.get(key2); // map to bucket 1, get as entry 1[2]
map.get(key3); // map to bucket 1, no corresponding entry
Expected: 2, 2, 2
Output: 1, 2, null
Override equals() solo:HashMap mappe di tutte le chiavi in diversi secchi a causa di predefinito diverso hashCode(). == o equals() qui il controllo è irrilevante poiché HashMap non raggiunge mai il punto in cui è necessario utilizzarli.
class AmbiguousInteger {
private final int value;
AmbiguousInteger(int value) {
this.value = value;
}
@Override
public boolean equals(Object obj) {
return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value;
}
}
map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 2, set as entry 2[1]
map.get(key1); // map to bucket 1, get as entry 1[1]
map.get(key2); // map to bucket 2, get as entry 2[1]
map.get(key3); // map to no bucket
Expected: 2, 2, 2
Actual: 1, 2, null
Override sia hashCode() e equals(): HashMap mappe key1, key2 e key3 nello stesso secchio. I controlli == non riescono quando si confrontano diverse istanze, ma i controlli equals() passano in quanto hanno tutti lo stesso valore e sono considerati "logicamente equivalenti" dalla nostra logica.
class AmbiguousInteger {
private final int value;
AmbiguousInteger(int value) {
this.value = value;
}
@Override
public int hashCode() {
return value;
}
@Override
public boolean equals(Object obj) {
return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value;
}
}
map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 1, set as entry 1[1], override value
map.get(key1); // map to bucket 1, get as entry 1[1]
map.get(key2); // map to bucket 1, get as entry 1[1]
map.get(key3); // map to bucket 1, get as entry 1[1]
Expected: 2, 2, 2
Actual: 2, 2, 2
E se hashCode() è casuale?: HashMap assegnerà un bucket diverso per ciascuna operazione, pertanto non si troverà mai la stessa voce inserita in precedenza.
class AmbiguousInteger {
private static int staticInt;
private final int value;
AmbiguousInteger(int value) {
this.value = value;
}
@Override
public int hashCode() {
return ++staticInt; // every subsequent call gets different value
}
@Override
public boolean equals(Object obj) {
return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value;
}
}
map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 2, set as entry 2[1]
map.get(key1); // map to no bucket, no corresponding value
map.get(key2); // map to no bucket, no corresponding value
map.get(key3); // map to no bucket, no corresponding value
Expected: 2, 2, 2
Actual: null, null, null
E se hashCode() è sempre lo stesso?: HashMap mappa tutte le chiavi in un unico grande secchio. In questo caso, il codice è funzionalmente corretto, ma l'uso di HashMap è praticamente ridondante, poiché qualsiasi recupero dovrebbe scorrere tutte le voci in quel singolo bucket in O (N) tempo(), equivalente all'utilizzo di un List .
class AmbiguousInteger {
private final int value;
AmbiguousInteger(int value) {
this.value = value;
}
@Override
public int hashCode() {
return 0;
}
@Override
public boolean equals(Object obj) {
return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value;
}
}
map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 1, set as entry 1[1]
map.get(key1); // map to bucket 1, get as entry 1[1]
map.get(key2); // map to bucket 1, get as entry 1[1]
map.get(key3); // map to bucket 1, get as entry 1[1]
Expected: 2, 2, 2
Actual: 2, 2, 2
E se equals è sempre falso?: == controllo passa quando si confronta la stessa istanza con se stessa, ma non riesce altrimenti, equals controlli non riesce sempre così key1, key2 e key3 sono considerati 'logicamente diversa', e le mappe di diverse voci, anche se sono ancora nella stessa benna a causa dello stesso hashCode().
class AmbiguousInteger {
private final int value;
AmbiguousInteger(int value) {
this.value = value;
}
@Override
public int hashCode() {
return 0;
}
@Override
public boolean equals(Object obj) {
return false;
}
}
map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 1, set as entry 1[2]
map.get(key1); // map to bucket 1, get as entry 1[1]
map.get(key2); // map to bucket 1, get as entry 1[2]
map.get(key3); // map to bucket 1, no corresponding entry
Expected: 2, 2, 2
Actual: 1, 2, null
Va bene che cosa succede se equals è sempre vero oggi?: stai praticamente dicendo che tutti gli oggetti sono considerati 'logicamente equivalenti' a un altro, quindi tutti si associano allo stesso segmento (a causa dello stesso hashCode()), stessa voce.
class AmbiguousInteger {
private final int value;
AmbiguousInteger(int value) {
this.value = value;
}
@Override
public int hashCode() {
return 0;
}
@Override
public boolean equals(Object obj) {
return true;
}
}
map.put(key1, 1); // map to bucket 1, set as entry 1[1]
map.put(key2, 2); // map to bucket 1, set as entry 1[1], override value
map.put(new AmbiguousInteger(100), 100); // map to bucket 1, set as entry1[1], override value
map.get(key1); // map to bucket 1, get as entry 1[1]
map.get(key2); // map to bucket 1, get as entry 1[1]
map.get(key3); // map to bucket 1, get as entry 1[1]
Expected: 2, 2, 2
Actual: 100, 100, 100
Vale anche la pena notare che la funzione di uguale è implementata in modo errato. Funziona solo su questo caso perché i due letterali stringa "Monday" sono internati e quindi hanno lo stesso riferimento. –
Sì, ben individuato! Abbastanza corretto. –
Il metodo equals dovrebbe anche essere in grado di gestire 'null' e gli argomenti di classi diverse (sottotipi di nota). Se si mantiene 'equals' (e' hashCode') in un modulo standard, allora è banale implementarlo correttamente (anche una macchina potrebbe codificarlo!). –