Cos'è l'hashing

È il processo di conversione di un oggetto in un valore intero. Il valore intero aiuta nell'indicizzazione e nelle ricerche più veloci.

Cos'è HashMap

HashMap fa parte del framework di raccolta Java. Utilizza una tecnica chiamata Hashing. Implementa l'interfaccia della mappa. Memorizza i dati nella coppia Chiave e Valore. HashMap contiene un array di nodi e il nodo è rappresentato come una classe. Utilizza internamente un array e una struttura dati LinkedList per archiviare chiave e valore. Ci sono quattro campi in HashMap.

Prima di comprendere il funzionamento interno di HashMap, è necessario conoscere il metodo hashCode() e equals().

conversione dell'oggetto in stringa

equivale():Verifica l'uguaglianza di due oggetti. Confronta la chiave, indipendentemente dal fatto che siano uguali o meno. È un metodo della classe Object. Può essere sovrascritto. Se si sovrascrive il metodo equals(), è obbligatorio sovrascrivere il metodo hashCode().codice hash():Questo è il metodo della classe oggetto. Restituisce il riferimento alla memoria dell'oggetto in forma intera. Il valore ricevuto dal metodo viene utilizzato come numero del bucket. Il numero del bucket è l'indirizzo dell'elemento all'interno della mappa. Il codice hash della chiave null è 0.Benne:L'array del nodo è chiamato bucket. Ogni nodo ha una struttura dati come una LinkedList. Più di un nodo può condividere lo stesso bucket. Potrebbe essere diverso in termini di capacità.

Inserisci chiave, coppia valore in HashMap

Usiamo il metodo put() per inserire la coppia Chiave e Valore nell'HashMap. La dimensione predefinita di HashMap è 16 (da 0 a 15).

Esempio

Nell'esempio seguente, vogliamo inserire tre coppie (Chiave, Valore) nell'HashMap.

 HashMap map = new HashMap(); map.put('Aman', 19); map.put('Sunny', 29); map.put('Ritesh', 39); 

Vediamo in quale indice la coppia chiave-valore verrà salvata in HashMap. Quando chiamiamo il metodo put(), calcola il codice hash della chiave 'Aman.' Supponiamo che il codice hash di 'Aman' sia 2657860. Per archiviare la chiave in memoria, dobbiamo calcolare l'indice.

Indice di calcolo

L'indice riduce al minimo la dimensione dell'array. La formula per calcolare l'indice è:

 Index = hashcode(Key) & (n-1) 

Dove n è la dimensione dell'array. Quindi il valore dell'indice per 'Aman' è:

 Index = 2657860 & (16-1) = 4 

Il valore 4 è il valore dell'indice calcolato in cui la chiave e il valore verranno archiviati in HashMap.

confrontare con Java

Collisione di hash

Questo è il caso in cui il valore dell'indice calcolato è lo stesso per due o più chiavi. Calcoliamo il codice hash per un'altra chiave 'Sunny'. Supponiamo che il codice hash per 'Sunny' sia 63281940. Per archiviare la chiave in memoria, dobbiamo calcolare l'indice utilizzando la formula dell'indice.

 Index=63281940 & (16-1) = 4 

Il valore 4 è il valore dell'indice calcolato in cui la chiave verrà archiviata in HashMap. In questo caso, il metodo equals() verifica che entrambe le chiavi siano uguali o meno. Se le chiavi sono le stesse, sostituire il valore con il valore corrente. Altrimenti, collega questo oggetto nodo all'oggetto nodo esistente tramite LinkedList. Quindi entrambe le chiavi verranno archiviate nell'indice 4.

Allo stesso modo, memorizzeremo la chiave 'Ritesh'. Supponiamo che il codice hash per la chiave sia 2349873. Il valore dell'indice sarà 1. Quindi questa chiave verrà archiviata nell'indice 1.

get() metodo in HashMap

Il metodo get() viene utilizzato per ottenere il valore tramite la sua chiave. Non recupererà il valore se non conosci la chiave. Quando viene chiamato il metodo get(K Key), calcola il codice hash della chiave.

Supponiamo di dover recuperare la chiave 'Aman'. Verrà chiamato il seguente metodo.

la stringa Java contiene

 map.get(new Key('Aman')); 

Genera il codice hash come 2657860. Ora calcola il valore dell'indice di 2657860 utilizzando la formula dell'indice. Il valore dell'indice sarà 4, come abbiamo calcolato sopra. Il metodo get() cerca il valore dell'indice 4. Confronta il primo elemento Key con la Key specificata. Se entrambe le chiavi sono uguali, restituisce il valore altrimenti controlla l'elemento successivo nel nodo, se esiste. Nel nostro scenario, si trova come primo elemento del nodo e restituisce il valore 19.

Andiamo a prendere un'altra chiave 'Sunny'.

Il codice hash della chiave 'Sunny' è 63281940. Il valore dell'indice calcolato di 63281940 è 4, come abbiamo calcolato per il metodo put(). Vai all'indice 4 dell'array e confronta la chiave del primo elemento con la chiave data. Confronta anche Keys. Nel nostro scenario, la chiave specificata è il secondo elemento e il successivo del nodo è nullo. Confronta il secondo elemento Key con la Key specificata e restituisce il valore 29. Restituisce null se il successivo del nodo è null.