TechCodeview

Was ist Hashing?

Dabei handelt es sich um den Prozess der Konvertierung eines Objekts in einen ganzzahligen Wert. Der ganzzahlige Wert hilft bei der Indizierung und schnelleren Suchvorgängen.

Was ist HashMap?

HashMap ist Teil des Java-Collection-Frameworks. Es verwendet eine Technik namens Hashing. Es implementiert die Kartenschnittstelle. Es speichert die Daten im Paar Schlüssel und Wert. HashMap enthält ein Array der Knoten und der Knoten wird als Klasse dargestellt. Es verwendet intern ein Array und eine LinkedList-Datenstruktur zum Speichern von Schlüssel und Wert. Es gibt vier Felder in HashMap.

Bevor Sie die interne Funktionsweise von HashMap verstehen, müssen Sie die Methoden hashCode() und equal() kennen.

Arten von Binärbäumen

gleich():Es prüft die Gleichheit zweier Objekte. Es vergleicht den Schlüssel, ob sie gleich sind oder nicht. Es ist eine Methode der Object-Klasse. Es kann überschrieben werden. Wenn Sie die Methode equal() überschreiben, ist es zwingend erforderlich, die Methode hashCode() zu überschreiben.Hash-Code():Dies ist die Methode der Objektklasse. Es gibt die Speicherreferenz des Objekts in ganzzahliger Form zurück. Der von der Methode erhaltene Wert wird als Bucket-Nummer verwendet. Die Bucket-Nummer ist die Adresse des Elements innerhalb der Karte. Der Hash-Code des Nullschlüssels ist 0.Eimer:Das Array des Knotens wird Buckets genannt. Jeder Knoten hat eine Datenstruktur wie eine LinkedList. Mehrere Knoten können denselben Bucket gemeinsam nutzen. Die Kapazität kann unterschiedlich sein.

Fügen Sie ein Schlüssel-Wert-Paar in HashMap ein

Wir verwenden die Methode put(), um das Schlüssel-Wert-Paar in die HashMap einzufügen. Die Standardgröße von HashMap beträgt 16 (0 bis 15).

Beispiel

Im folgenden Beispiel möchten wir drei Paare (Schlüssel, Wert) in die HashMap einfügen.

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

Sehen wir uns an, bei welchem ​​Index das Schlüssel-Wert-Paar in HashMap gespeichert wird. Wenn wir die put()-Methode aufrufen, berechnet sie den Hash-Code des Schlüssels „Aman“. Angenommen, der Hash-Code von „Aman“ lautet 2657860. Um den Schlüssel im Speicher zu speichern, müssen wir den Index berechnen.

Index berechnen

Index minimiert die Größe des Arrays. Die Formel zur Berechnung des Index lautet:

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

Wobei n die Größe des Arrays ist. Daher ist der Indexwert für „Aman“:

 Index = 2657860 & (16-1) = 4 

Der Wert 4 ist der berechnete Indexwert, in dem der Schlüssel und der Wert in HashMap gespeichert werden.

Hash-Kollision

Dies ist der Fall, wenn der berechnete Indexwert für zwei oder mehr Schlüssel gleich ist. Berechnen wir den Hash-Code für einen anderen Schlüssel „Sunny“. Angenommen, der Hash-Code für „Sunny“ lautet 63281940. Um den Schlüssel im Speicher zu speichern, müssen wir den Index mithilfe der Indexformel berechnen.

Zeichenfolge im Array in c

 Index=63281940 & (16-1) = 4 

Der Wert 4 ist der berechnete Indexwert, in dem der Schlüssel in HashMap gespeichert wird. In diesem Fall prüft die Methode equal(), ob beide Schlüssel gleich sind oder nicht. Wenn die Schlüssel gleich sind, ersetzen Sie den Wert durch den aktuellen Wert. Andernfalls verbinden Sie dieses Knotenobjekt über die LinkedList mit dem vorhandenen Knotenobjekt. Daher werden beide Schlüssel auf Index 4 gespeichert.

Ebenso werden wir den Schlüssel „Ritesh“ speichern. Angenommen, der Hash-Code für den Schlüssel ist 2349873. Der Indexwert ist 1. Daher wird dieser Schlüssel bei Index 1 gespeichert.

get()-Methode in HashMap

Die Methode get() wird verwendet, um den Wert anhand seines Schlüssels abzurufen. Der Wert wird nicht abgerufen, wenn Sie den Schlüssel nicht kennen. Wenn die Methode get(K Key) aufgerufen wird, berechnet sie den Hash-Code des Schlüssels.

Angenommen, wir müssen den Schlüssel „Aman“ holen. Die folgende Methode wird aufgerufen.

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

Es generiert den Hash-Code als 2657860. Berechnen Sie nun den Indexwert von 2657860 mithilfe der Indexformel. Der Indexwert beträgt 4, wie wir oben berechnet haben. Die Methode get() sucht nach dem Indexwert 4. Sie vergleicht das erste Element Key mit dem angegebenen Key. Wenn beide Schlüssel gleich sind, wird der Wert zurückgegeben. Andernfalls wird nach dem nächsten Element im Knoten gesucht, falls vorhanden. In unserem Szenario wird es als erstes Element des Knotens gefunden und gibt den Wert 19 zurück.

Einschränkungen des E-Bankings

Lass uns einen weiteren Schlüssel holen, „Sunny“.

Der Hash-Code des Schlüssels „Sunny“ ist 63281940. Der berechnete Indexwert von 63281940 ist 4, wie wir für die Methode put() berechnet haben. Gehen Sie zu Index 4 des Arrays und vergleichen Sie den Schlüssel des ersten Elements mit dem angegebenen Schlüssel. Es vergleicht auch Schlüssel. In unserem Szenario ist der angegebene Schlüssel das zweite Element und der nächste Knoten ist null. Es vergleicht das zweite Element Key mit dem angegebenen Key und gibt den Wert 29 zurück. Es gibt null zurück, wenn der nächste Knoten null ist.