java collisione HashMap

Question

Stavo leggendo su come funziona hashmap. Stavo leggendo lo "What will happen if two different objects have same hashcode".

Secondo questo se due oggetti hanno lo stesso codice hash entrambi saranno memorizzati in LinkedList ma per quanto ne so se due hashcode allora quello precedente verrà sovrascritto con uno nuovo (correggimi se ho torto).

qualcuno può mettere più in luce oggetto uso Come hashmap come chiave internamente e che cosa accadrà se due oggetti ha lo stesso codice hash e come entrambi gli oggetti saranno recuperati con get()?

Answer 1

No, il primo non viene sovrascritto solo perché il secondo ha lo stesso hashCode.

Sarà sostituito solo se è uguale (come indicato da equals). In caso contrario, entrambi i valori verranno mantenuti nell'elenco collegato.

Quando si preleva un tasto, tutti i nodi con lo stesso hashCode verranno confrontati con la chiave fornita fino a quando uno è uguale, quindi verrà restituito il suo valore (utilizzando il metodo equals).

Se nessuna chiave nella mappa è uguale, riceverai null.

L'unico problema che hai se molti oggetti hanno la stessa hashCode (o più precisamente lo stesso hashCode modulo la dimensione della interno Entry[] table) è che la lista collegata sarà sempre la lettura, che è più lento (e sconfigge lo scopo di qualsiasi tabella hash). Ecco perché è importante quando si progetta un metodo hashcode per garantire che gli interi generati siano ben distribuiti.

Answer 2

Supponendo che si stiano seguendo le regole per defining hashCode and equals, lo scenario che hai descritto non comporterà la perdita di dati. Al massimo, le prestazioni si degraderanno nel tempo.

Answer 3

Nell'hashmap Java potrebbero utilizzare diversi modi per farlo. Dalla mia vecchia classe CS 201 Data Structures nel periodo buio:

1) Ogni bucket nella mappa hash può diventare la testa di un elenco collegato tenendo tutte le voci aggiunte che hanno lo stesso valore hash. Una collisione in fase di aggiunta significa che aggiungi la nuova voce alla fine dell'elenco collegato. Ricerca significa che devi controllare in modo lineare tutti quelli presenti in qualsiasi elenco collegato dopo averlo inserito nel secchio.

2) Se si verifica una collisione e lo store è concettualmente un array, è possibile eseguire iterazioni a partire da quel punto fino a trovare un punto vuoto e aggiungere la nuova voce lì. Per la ricerca ciò significa che se si trova il bucket hash, è necessario confrontare linearmente da quel punto al successivo punto vuoto dell'array che supporta la mappa hash.

In entrambi i casi, le prestazioni si riducono se vi sono più voci con lo stesso hash. Nel caso generale, ciò significa che una funzione di hash (utilizzata per generare il codice hash) restituisce un piccolo numero di valori possibili, le prestazioni si ridurranno man mano che la mappa si riempie. Java HashMap ha approfittato di 50 anni di ricerche su queste cose per adattarsi al caso generale di dati generali che si trovano in una mappa con hash.

Nota @dystroy ha fatto un commento sulla regola che non è possibile avere due voci nella mappa con quella corrispondenza in base al metodo equals().

Answer 4

Lasciatemi spiegare il funzionamento di hashmap.

di lavoro del metodo put:

HashMap opere in principio di hashing, abbiamo put() e get() metodo per archiviare e recuperare forma oggetto HashMap. Quando passiamo sia una chiave che un valore al metodo per l'archiviazione su HashMap, utilizza il metodo chiave hashcode() per calcolare hashcode e loro applicando l'hashing su quel codice hash che identifica la posizione del bucket per la memorizzazione dell'oggetto valore. Durante il recupero utilizza il metodo chiave equals di oggetti per trovare la coppia di valori chiave corretta e l'oggetto valore di ritorno associato a quella chiave. HashMap utilizza l'elenco collegato in caso di collisione e l'oggetto verrà memorizzato nel nodo successivo dell'elenco collegato. memorizza anche HashMap sia fondamentale valore + tuple in ogni nodo della lista collegata

di lavoro del metodo get:

Quando passiamo oggetto chiave e il valore di put() metodo su Java HashMap, implementazione HashMap chiama il metodo hashCode su Oggetto chiave e applica hashcode restituito nella propria funzione di hashing per trovare una posizione del bucket per la memorizzazione dell'oggetto Entry, il punto importante da menzionare è che HashMap in Java memorizza sia l'oggetto chiave che il valore come Map.Entry nel bucket. Se più di un oggetto Entry viene trovato nel bucket, chiamerà il metodo ke.equals di ciascun nodo nello stesso bucket.