Què és Hashing

És el procés de convertir un objecte en un valor enter. El valor sencer ajuda a la indexació i a les cerques més ràpides.

Què és HashMap

HashMap és una part del marc de col·lecció Java. Utilitza una tècnica anomenada Hashing. Implementa la interfície del mapa. Emmagatzema les dades al parell de clau i valor. HashMap conté una matriu dels nodes i el node es representa com una classe. Utilitza una matriu i una estructura de dades LinkedList internament per emmagatzemar la clau i el valor. Hi ha quatre camps a HashMap.

Abans d'entendre el funcionament intern de HashMap, heu de ser conscients del mètode hashCode() i equals().

diferència entre un lleó i un tigre

és igual():Comprova la igualtat de dos objectes. Compara la clau, siguin iguals o no. És un mètode de la classe Object. Es pot anul·lar. Si anul·leu el mètode equals(), és obligatori anul·lar el mètode hashCode().hashCode():Aquest és el mètode de la classe d'objectes. Retorna la referència de memòria de l'objecte en forma enter. El valor rebut del mètode s'utilitza com a número de cub. El número de cub és l'adreça de l'element dins del mapa. El codi hash de la clau nul·la és 0.Cubells:La matriu del node s'anomena cubs. Cada node té una estructura de dades com una LinkedList. Més d'un node pot compartir el mateix cub. Pot ser diferent en capacitat.

Insereix clau, parell de valors a HashMap

Utilitzem el mètode put() per inserir la parella Clau i Valor al HashMap. La mida predeterminada de HashMap és 16 (de 0 a 15).

Exemple

A l'exemple següent, volem inserir tres parells (clau, valor) al HashMap.

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

Vegem a quin índex es desarà la parella clau i valor a HashMap. Quan anomenem el mètode put(), calcula el codi hash de la clau 'Aman'. Suposem que el codi hash de 'Aman' és 2657860. Per emmagatzemar la clau a la memòria, hem de calcular l'índex.

Càlcul de l'índex

L'índex minimitza la mida de la matriu. La fórmula per calcular l'índex és:

unió de cadena java

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

On n és la mida de la matriu. Per tant, el valor de l'índex per a 'Aman' és:

 Index = 2657860 & (16-1) = 4 

El valor 4 és el valor de l'índex calculat on s'emmagatzemaran la clau i el valor a HashMap.

Col·lisió Hash

Aquest és el cas quan el valor de l'índex calculat és el mateix per a dues o més claus. Calculem el codi hash per a una altra clau 'Sunny'. Suposem que el codi hash de 'Sunny' és 63281940. Per emmagatzemar la clau a la memòria, hem de calcular l'índex utilitzant la fórmula d'índex.

 Index=63281940 & (16-1) = 4 

El valor 4 és el valor de l'índex calculat on s'emmagatzemarà la clau a HashMap. En aquest cas, el mètode equals() comprova que les dues claus siguin iguals o no. Si les claus són iguals, substituïu el valor pel valor actual. En cas contrari, connecteu aquest objecte node a l'objecte node existent mitjançant la LinkedList. Per tant, les dues claus s'emmagatzemaran a l'índex 4.

De la mateixa manera, emmagatzemarem la clau 'Ritesh'. Suposem que el codi hash de la clau és 2349873. El valor de l'índex serà 1. Per tant, aquesta clau s'emmagatzemarà a l'índex 1.

una matriu en java

mètode get() a HashMap

El mètode get() s'utilitza per obtenir el valor mitjançant la seva clau. No obtindrà el valor si no coneixeu la clau. Quan es crida al mètode get(K Key), calcula el codi hash de la Key.

Suposem que hem de buscar la clau 'Aman'. S'anomenarà el següent mètode.

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

Genera el codi hash com a 2657860. Ara calculeu el valor de l'índex de 2657860 mitjançant la fórmula d'índex. El valor de l'índex serà 4, tal com hem calculat anteriorment. El mètode get() cerca el valor d'índex 4. Compara el primer element Clau amb la clau donada. Si les dues claus són iguals, retorna el valor, sinó comprova el següent element del node si existeix. En el nostre escenari, es troba com el primer element del node i retorna el valor 19.

Anem a buscar una altra clau 'Sunny'.

El codi hash de la clau 'Sunny' és 63281940. El valor de l'índex calculat de 63281940 és 4, tal com hem calculat per al mètode put(). Aneu a l'índex 4 de la matriu i compareu la clau del primer element amb la clau donada. També compara Keys. En el nostre escenari, la clau donada és el segon element i el següent del node és nul. Compara el segon element Clau amb la clau especificada i retorna el valor 29. Torna nul si el següent del node és nul.