Risoluzione collisione in HashMap

Question

Quando inseriamo la coppia chiave-valore in HashMap, ciò potrebbe accadere che l'hashcode di due chiavi potrebbe essere lo stesso di come in questa condizione verranno gestiti l'archiviazione e il recupero del valore-chiave.

Aggiornamento

Quello che ho capito finora è che se due chiave oggetto ha lo stesso codice hash quindi entrambi gli oggetti chiave saranno memorizzate nel secchio stesso e quando dirò get(key) poi fuori di due oggetti con codice hash di corrispondenza quale elemento da recuperare è deciso da object.equals().

Answer 1

Quando si desidera recuperare un oggetto da hashmap e esistono diversi oggetti con lo stesso hashcode, java chiamerà equals() per determinare l'oggetto giusto.

Ecco perché è così importante eseguire l'override di equals() quando si sostituisce hashCode().

Answer 2

Ogni bucket è rappresentato da un elenco collegato, quindi non vi è alcun limite, diverso dallo spazio heap, sul numero di voci in un bucket. Ci sono meno bucket dei possibili risultati hashCode, quindi più codici hash sono mappati allo stesso bucket, non solo chiavi con lo stesso hashCode.

A hashCode() con un numero elevato di collisioni o una HashMap con un numero di bucket insufficiente, è possibile creare lunghi elenchi collegati. Le buone prestazioni dipendono da brevi elenchi concatenati, poiché la fase finale di una ricerca è una scansione lineare di uno degli elenchi collegati.

Sono d'accordo con la risposta precedente che una corrispondenza dipende sia da equals() sia da hashCode().