Java HashMap – Esempio Collisione

– Indice Tutorial –

Per poter usare correttamente l’HashMap bisogna implementare correttamente l’override delle funzioni hashcode() e equals() altrimenti si incorre nel problema delle collisioni, ossia per due chiavi diverse che hanno lo stesso hashcode,e quindi andranno nella stessa locazione,  non ci sarà modo di capire se si devono essere sovrascritti o aggiunti in quella locazione.

Per risolvere questo problema si deve fare l’override di haschcode (in modo da ridurre al minimo la possibilità che due chiavi diverse abbiano lo stesso hash) e anche di equals.In questo modo quando due chiavi diverse (due chiavi associati a due valori diversi) hanno lo stesso hashcode  viene utilizzata la  funzione equals per capire se è la stessa chiave o no. Se è la stessa chiave, viene aggiornata la coppia chiave-valore (ricordiamoci che nella locazione vengono inserite le coppie chiavi-valori), altrimenti viene aggiunta.

Vediamo un esempio che mostra un caso di hashmap con collisione risolto tramite l’equals:

Esempio:

Definiamo una classe Persona in cui l override di hashcode è fatto in modo tale che ritorni l’id.

[java]

package example.hashmap;

public class Persona {
private String nome;
private int id;

public Persona(String nome, int id) {
this.nome = nome;
this.id = id;
}

public String getNome() {
return nome;
}
public void setNome(String nome) {
this.nome = nome;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}

@Override
public int hashCode() {

System.out.println(“chiamato hashCode per =”+ id+”.”+nome);
return id;
}

@Override
public boolean equals(Object obj) {
System.out.println(“called equals on =”+ id+”.”+nome + ” to compare with = “+ ((Persona)obj).getId() + “.”+ ((Persona)obj).getNome());

if( ((Persona)obj).getId() == id && ((Persona)obj).getNome().equals(nome) )
return true;
return false;
}
}

[/java]

Nel main, vengono create 3 chiavi, di cui due i (p1 e p3)  hanno lo stesso id (1), quindi lo stesso hashcode, e inserite dentro una mappa.

[java]

package example.hashmap;

import java.util.HashMap;

public class ProvaMap {

public static void main(String[] args) {

// //ESEMPIO COLLISIONE
Persona p1 = new Persona(“mario”,1);
Persona p2 = new Persona(“gino”,2);
Persona p3 = new Persona(“flavio”,1);// viene messo lo stesso id di p1, l hashcode per
// come definito ritorna l id.

HashMap<Persona, String> mappa = new HashMap<Persona, String>();

mappa.put(p1, “ONE”);
mappa.put(p2, “TWO”);
mappa.put(p3, “THREE”);

Persona p1Bis = new Persona(“mario”,1);

String value = mappa.get(p1Bis);
System.out.println(” value: “+ value);

//nell output si vede che chiama l hashcode per “mario” che da 1,
//// ma nella posizione 1 è memorizzato anche “flavio” quindi
//// chiama anche equals per capire quale chiave è corretta

}

}

[/java]

L’output sarà:

Quando inserisco la p3 nella mappa, nell’output si nota  la chiamata al metodo equals per capire se la chiave già presente nella locazione con indirizzo 1 (ossia p1, “1.mario”) è uguale o no alla p3 (“1.flavio”).  Equals dice che sono diversi quindi avremo che nella locazione 1 ci sono due coppie chiave-valore (p1-ONE e p3-THREE)

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.