È a mia conoscenza che due oggetti non uguali possono avere lo stesso codice hash. Come si gestirà questo quando si aggiunge o si recupera da un HashMap Java?Cosa succede se due oggetti diversi hanno lo stesso codice hash?
Saranno aggiunti allo stesso bucket e verrà utilizzato equals() per distinguerli. Ogni bucket può contenere un elenco di oggetti con lo stesso codice hash.
In teoria è possibile restituire lo stesso numero intero di un codice hash per qualsiasi oggetto di una data classe, ma ciò significherebbe perdere tutti i vantaggi delle prestazioni della mappa hash e, in effetti, memorizzerà gli oggetti in una lista.
Non è un hash supplementare applicato di default per una Hashmap per impedire che ciò accada che introduce qualche distribuzione? – Ajay
Punto aggiuntivo sulle prestazioni, in java8, quando abbiamo troppe chiavi non uguali che danno lo stesso hashcode (indice) - quindi il numero di elementi in un bucket hash cresce oltre una certa soglia (TREEIFY_THRESHOLD = 8), il contenuto di quel bucket passa dall'uso un elenco collegato di oggetti Entry a un albero bilanciato. Questo teoricamente migliora le prestazioni nel caso peggiore da O (n) a O (log n). –
In HashMap, le chiavi insieme ai loro valori associativi sono memorizzate in un nodo di elenco collegato nel bucket e le chiavi vengono essenzialmente confrontate in hashmap utilizzando il metodo equals() non da hashcode.
hm.put("a","aValue"); // Suppose hashcode created for key "a" is 209
hm.put("b","bValue"); // Here hashcode created for key "b" is 209 as well.
a.equals(b) rendimenti true, bValue sostituirà aValue e verrà restituito bValue.a.equals(b) rendimenti false, un altro nodo verrà creato nella lista secchio, in modo che quando si chiama get("b") si otterrà bValue dal a.equals(b) è false.Come posso recuperare il valore di un hash se lo stesso è? Mi darà bValue, ma voglio un valore. È possibile ? – Sanket
In questo caso è possibile utilizzare IdentityHashMap, dove oggetti diversi con lo stesso hash sono considerati diversi in base alle loro identità.
Quando due oggetti non uguali hanno lo stesso valore di hash, ciò causa una collisione nella tabella hash, poiché entrambi gli oggetti vogliono essere nello stesso slot (a volte chiamato un bucket). L'algoritmo hash deve risolvere tali conflitti. Tornando indietro nei ricordi sbiaditi del mio corso sugli algoritmi universitari, ricordo tre modi fondamentali per farlo:
Penso che le classi di hash Java utilizzino il terzo metodo, ma potrebbero utilizzare un approccio combinato. La chiave per un buon hashing è però assicurarsi che la tabella hash abbia una capacità sufficiente e scrivere buone funzioni hash. Una tabella di hash che ha solo un numero di bucket pari agli oggetti in esso contenuti avrà probabilmente dei conflitti. In genere si desidera che la tabella hash sia circa il doppio del numero di oggetti memorizzati. Java HashMap crescerà secondo le necessità, ma se lo desideri potrai dargli una capacità iniziale e un fattore di carico.
La funzione di hash è fino al programmatore. Si potrebbe semplicemente restituire 0 per tutti gli oggetti, ma ciò significa che l'hashing (sia di memorizzazione che di recupero) diventerà O (n) invece di O (1) ... o in termini di lay, sarà lento.
Riferimento: http://www.coderanch.com/t/540275/java/java/objects-hashcode-HashMap-retrieve-objects
HashMap sta lavorando sul concetto di hashing e indicizzazione. Internamente HashMap memorizza i valori in Array of Nodes. Ogni nodo si comporta come LinkedList.
Ogni nodo della lista collegata hanno 4 valori:
int hashK keyV valueNode<K, V> nextHashMap interno:
Mentre si inserisce il valore in HashMap, viene generato il primo codice hash della chiave e in base ad alcuni algoritmi verrà calcolato l'indice.
Quindi il nostro valore verrà memorizzato in un indice specifico con hashcode, chiave, valore e indirizzo dell'elemento successivo.
Durante il recupero del valore da HashMap, il primo hashcode verrà generato e quindi indicizzato (allo stesso modo del momento dell'inserimento). Mentre si ottiene il valore dall'indice, per prima cosa controllerà l'hashcode, se l'hashcode corrisponderà, solo allora controllerà la chiave dal nodo usando il metodo equals. Se la chiave corrisponde, solo restituirà il valore oppure controllerà il nodo successivo con lo stesso codice hash.
BTW: è possibile creare facilmente molti valori lunghi con lo stesso codice hash per provare questo. 'new Long (n * 0x100000001L)' tutti hanno un hashCode di 0 per 'n> = 0' –