Was ist eine Hashmap und wie implementierst du damit eine extrem effektive Datenstruktur in Java?

Keylearnings:

• Was ist eine Hashmap?
• Was ist ein Assoziativspeicher?
• Was ist eine Kollision?
• Wie du eine Hashmap in JAVA realisierst.
• Hashmap nach der Divisions Rest Methode.
• Hashverfahren mit Verkettung der Überläufer.
• Was sind offene Hashverfahren?
• Was ist eine Sondierungsfunktion
• Wie die Suche in einem Assoziativspeicher funktioniert.
• Wie du eine Java Hashmap mit der Klasse Hashmap implementierst (VIDEOERKLÄRUNG) 

Wusstest du das die Postleitzahl 56077 zu Koblenz gehört?

Nein? Du hättest nachsehen müssen. Richtig?

Sehr gut, denn genau hierum geht es in diesem Artikel.

Wir werden uns sogenannte Assoziativspeicher ansehen, mit denen wir sehr effektiv Zuordnungsprobleme dieser Art lösen können.

Hast du schon mal Möbel in einem schwedischen Möbelhaus gekauft?

Ich habe mir kürzlich einen neuen Sessel gegönnt, und ich sag dir die haben ein riesiges Lager, über das man schnell den Überblick verliert.

Aber die haben das sehr clever gemacht. Jedes Möbelstück hat eine Artikelnummer, über die man es sehr einfach finden kann.

Und genau so funktioniert auch ein Assoziativspeicher.

Bei einem Assoziativspeicher werden Paare bestehend aus einem Schlüssel und den eigentlichen Daten gespeichert.

Im schwedischen Möbelhaus entspricht die Artikelnummer dem Schlüssel und das Möbelstück den Daten.

Genauso ist bei einem Postleitzahlendatensatz die Postleitzahl 56077 der Schlüssel und die Stadt Koblenz der Datensatz.

Das ist allerdings eine Einbahnstraße. In einem Assoziativspeicher gibt es keine effiziente Möglichkeit über den Datensatz auf den Schlüssel zu zugreifen.

Wenn wir die Postleitzahl als Schlüssel und die Städtenamen als Daten auffassen, ist es nicht effizient möglich über den Städtenamen Koblenz auf die Postleitzahl 56077 zu schließen.

Ziel bei einem Assoziativspeicher ist es möglichst schnell über den Schlüssel auf gesuchte Daten zu zugreifen.

Allerdings spricht nichts dagegen einen zweiten Assoziativspeicher anzulegen, in dem wir die Rollen von Schlüssel und Daten vertauschen, d.h. die Städtename die Schlüssel sind und die Postleitzahlen die Daten bilden, so dass wir über den Städtenamen leicht auf die Postleitzahl zugreifen können.

Kern eines Assoziativspeichers ist die sogenannte Hashmap, oft auch Hashfunktion genannt.

Was ist eine Hashmap?

Die Hashmap ist eine Zuordnung, die jedem Schlüssel (z.B. Artikelnummer) einen Datensatz zuordnet (z.B. Artikelname).

Ziel ist es die Hashmap so aufzubauen, dass über den Schlüssel schnell auf den zugehörigen Datensatz zugegriffen werden kann.

Hierbei haben wir es insbesondere mit drei, leider teilweise konkurrierenden Herausforderungen, zu tun.

1. Wir wollen auf einen  Datensatz zugreifen.
2. Wir wollen Datensätze einfügen.
3. Wir wollen Datensätze löschen.

Die Auswahl einer guten Hashmap ist intensiver Forschungsgegenstand der Informatik.

Beginnen wir mit der einfachsten Methode.

Hashmap nach der Division Rest Methode

Was wir als erstes brauchen ist ein Lager, in dem wir unsere Möbel speichern können.

Da wir noch nicht so groß wie unsere Kollegen aus Schweden sind, reichen uns 7 Lagerplätze, die wir mit einem String Array der Länge 7 realisieren.

String[] memory = new String[7];

Wir bestücken unser Lager mit folgenden Artikeln, wobei jeder Artikel eine entsprechende Artikelnummer besitzt.

12	Stuhl
53	Sessel
5	Schrank
15	Tisch
2	Lampe
19	Sofa

So nun aber auf zu den Hashfunktionen.

Die Divisions Rest Methode macht intensiven gebrauch des modulo mod Operators. Aber werden wir praktisch!

Hier die Implementierung dieser Methode in einer Methode. Hier die Methode! 🙂 Erklärung folgt!

private int divisionRestMethode(int k){
	return (k % 7);
}

Sieht doch garnicht so schlimm aus.

Die Methode erwartet als Parameter den Schlüssel k, also in unserem Fall die Artikelnummer des einzulagernden Möbelstücks.

Der Rückgabewert ist der Rest der Division des Schlüssels k durch sieben.

Aber warum ausgerechnet durch Sieben??

Nun ja, sieben ist die Länge unseres Lager-Arrays. Bei der Divisions Rest Methode müssen wir den Schlüssel durch die Anzahl der Lagerelemente, also die Länge des Speicher-Arrays mit Rest teilen.

Die allgemeine Formel bei der Divisions Rest Methode für die Hashfunktion ist also:

Schlüssel % Größe des Speichers

Und das Ergebnis dieser Rechnung nennt man Hashadresse.

Wenn dein Lager also größer ist und meinetwegen zehn Möbelstücke aufnehmen kann, dann lautet die Rechnung Schlüssel%10.

Aber was zum Geier haben wir davon?

Überlegen wir uns, welche Werte die Funktion divisionRestMethode zurückliefern kann.

Wenn man eine ganze Zahl mit Rest durch sieben teilt, sind die möglichen Reste 0, 1, 2, 3, 4, 5 und 6. Und genau das sind auch die möglichen Rückgabewerte der Methode divisionRestMethode.

Die Idee bei einer Hashmap ist es, diese Rückgabewerte als Index unseres Lager-Arrays zu verwenden. Diesen Index nennt man Hashwert bzw. Hashadresse.

So ist beispielsweise 53%7=4 weshalb wir den Wert Sessel im Arrayelement 4 speichern.

Also auf geht’s! Schreiben wir eine Einfüge-Methode, die auf diesem Prinzip beruht.

public void insert(int k, String data){
   memory[divisionRestMethode(k)] = data;
}

Unsere Einfügemethode insert erwartet zwei Parameter, zum einen den Schlüssel und zum anderen die zu diesem Schlüssel gehörigen Daten.

Im Methodenrumpf werden die Daten an die Stelle des zum Schlüssel k berechneten Hashwerts im Lager-Array memory gespeichert.

Versuchen wir die Daten unserer Möbeltabelle in die Hashmap einzufügen.

HashMapTest test = new HashMapTest(7);
test.insert(12,"Stuhl");
test.insert(53,"Sessel");
test.insert(5, "Schrank");
test.insert(15, "Tisch");
test.insert(2, "Lampe");
test.insert(19, "Sofa");

Um das Ergebnis zu überprüfen schreiben wir noch eine Methode output, mit der wir den gesamten Inhalt der Hashmap auf dem Bildschirm ausgeben können.

public void output(){
   for(int i=0;i<size;i++){
      System.out.println(i+": "+memory[i]);
   }
}

Diese Methode ist easy. Das einzige was wir hier machen, ist das Lager-Array zu durchlaufen und den Inhalt jedes Elements auf dem Bildschirm auszugeben.

Fein, rufen wir die output Methode auf und sehen uns das Resultat der Einfüge-Operationen an. Die Bildschirmausgabe ist:

0: null
1: Tisch
2: Lampe
3: null
4: Sessel
5: Sofa
6: null    

Oh, oh das sieht nicht gut aus! Der Schrank und der Stuhl fehlt.

Was ist schiefgelaufen?

Analysieren wir unsere Einfüge-Operationen indem wir den Algorithmus zu „Fuß“ durchgehen.

In Schritt Eins fügen wir der Hashmap den Artikel Stuhl mit der Artikelnummer 12 hinzu.

Die Hashadresse berechnen wir indem wir die Artikelnummer mit Rest durch die Länge des Arrays dividieren. Wir erhalten 12 % 7 = 5. Somit wird der Stuhl in Array-Position 5 eingelagert.

Als nächstes kümmern wir uns um den Sessel mit Artikelnummer 53. Es ist 53 % 7 = 4 weshalb der Sessel auf Position 4 aufbewahrt wird.

Weiter geht’s mit unserem Schrank mit Artikelnummer 5. Die Hashadresse ist in diesem Fall 5 % 7 = 5 weshalb der Schrank auf Position fünf landet.

STOOOPPPPP!!!

An Position 5 lagert bereits unser Stuhl.

Hierauf nimmt der Algorihtmus aber keine Rücksicht und schmeißt den Stuhl gnadenlos aus dem Lager und ersetzt ihn durch einen Schrank. Das ist ein Fehler, den wir auf jeden Fall flicken müssen.

Aber fahren wir fort, ich verspreche dir es wird noch toller!

Machen wir weiter mit dem Tisch mit Artikelnummer 15.

Es ist 15 % 7 = 1. Glück gehabt, diese Hashadresse verweist auf einen leeren Platz und wir können den Tisch problemlos einlagern.

Jetzt die Lampe mit Artikelnummer 2.

Es ist 2 % 7 = 2. Super, das ist auch nochmal gut gegangen auch diese Position gehört zu einem freien Platz, in dem die Lampe ein neues zu Hause findet.

Fehlt nur noch das Sofa mit der Artikelnummer 19.

Und hier haben wir wieder das gleiche Problem!

Die Hashadresse 19 % 7 = 5 ist aktuell mit einem Schrank belegt worauf der Algorithmus aber keine Rücksicht nimmt und deshalb den Schrank durch das Sofa ersetzt.

Jetzt haben wir die Erklärung dafür, weshalb der Schrank und der Stuhl bei unseren Einfüge-Operationen auf der Strecke bleiben.

Unsere Hashmap Artikelnummer % 7 bildet die Artikelnummern 12, 5 und 19 auf die gleiche Hashadresse nämlich die 5 ab.

Fachmännisch ausgedrückt sprechen wir hierbei von einer Kollision der Schlüssel 12, 5 und 19.

Oder als Mathefreak, kannst du meinetwegen auch sagen, dass unsere Hashmap nicht injektiv ist.

Kollisionsvermeidung in einer Hashmap

Die Kollisionsanfälligkeit gehört neben einer effizienten Berechnungsmöglichkeit zu den Qualitätskriterien, die eine gute Hashfunktion zu erfüllen hat.

Da der Modulo-Operator % sehr schnell ausgeführt werden kann, ist die Effizienz einer Hashmap nach der Division Reste Methode kein Problem.

Was allerdings die Kollisionsanfälligkeit angeht ist zu zugeben, dass es deutlich bessere Verfahren auf dem Markt gibt, die aber ebenfalls weit weg davon sind Kollisionsfrei zu sein. Weil solche Verfahren außerdem weniger intuitiv sind, wollen wir uns in diesem Einführungsartikel mit der Divisions Reste Methode begnügen.

Hint: Vielleicht hast du dich bereits gewundert, weshalb die Länge unseres Array ausgerechnet 7 ist. Das ist ein Ergebnis der theoretischen Informatik. Untersuchungen haben nämlich ergeben, dass in Arrays mit einer Länge, die eine Primzahl ist am wenigsten Kollisionen auftreten.

Aber wie dem auch sei. Kollisionen sind sicher wie das Amen in der Kirche und deshalb müssen wir uns um das Problem kümmern.

„Was soll ich tun? “ sprach Zeus. Die Götter sind besoffen!

Um mit Kollisionen umzugehen gibt es zwei Vorgehensweisen:

1. Hashverfahren mit Verkettung der Überläufer.
2. Offene Hashvefahren.

Betrachten wir das im einzelnen.

Hashverfahren mit Verkettung der Überläufer

Bei der Verkettung der Überläufer adressieren wir nicht mehr ein einfaches Array sondern ein Array von verketteten Listen.

Die Hashmap adressiert bei diesem Verfahren nicht mehr nur einzelne Speicherzellen, sondern jede Hashadresse zeigt auf eine verkettete Liste.

Unser Möbellager besteht daher aus einem Array von verketteten Listen. Nach wie vor soll unser Lager aus sieben Lagerplätzen bestehen.

private LinkedList[] memoryList = new LinkedList[7];

Nach dieser Anweisung haben wir Speicherplatz für sieben verkettete Listen definiert, den wir mit Hilfe einer for Schleife mit sieben Instanzen einer LinkedList initialisieren.

for(int i = 0;i<7;i++){
    memoryList[i] = new LinkedList();
}

Schauen wir uns als nächstes an wie wir unsere Möbel in das Lager einsortieren. Hierfür schreiben wir eine eigene Einfüge-Methode.

public void insert2(int k, String data){
   memoryList[divisionRestMethode(k)].add(data);
}

Die Funktionsweise ist sehr ähnlich wie bei unserem Versuch von oben.

Der einzige Unterschied besteht darin, dass wir unsere Daten in Listen schreiben und die Hashadresse eine ganze Liste und nicht mehr nur eine einzelne Speicherzelle adressiert.

Beauftragen wir die Möbelpacker und sortieren unser Lager ein.

HashMapTest test = new HashMapTest(7);
test.insert2(12,"Stuhl");
test.insert2(53,"Sessel");
test.insert2(5, "Schrank");
test.insert2(15, "Tisch");
test.insert2(2, "Lampe");
test.insert2(19, "Sofa");

Anstatt der Einfüge-Methode insert rufen wir diesmal die neue Methode insert2 ebenfalls mit den Parametern Artikelnummer und den zu speichernden Daten auf.

Um das Ergebnis überprüfen zu können, erstellen wir noch eine Methode um den Inhalt der Datenstruktur auf dem Bildschirm auszugeben.

public void output2(){
   for(int i=0;i<7;i++){
	for(int j = 0;j<memoryList[i].size();j++){
	   System.out.println(i+": "+" "+memoryList[i].get(j));
	}
  }
}    

Die Methode besteht aus zwei ineinander verschachtelten for-Schleifen.

Die erste Schleife durchläuft unser komplettes Lager, also das Array, das aus den verketteten Listen besteht. In der zweiten Schleife wird der Inhalt jeder Liste auf den Bildschirm ausgegeben.

Gut, rufen wir die Funktion auf und schauen uns die Ausgabe an.

1:  Tisch
2:  Lampe
4:  Sessel
5:  Stuhl
5:  Schrank
5:  Sofa

Sehr gut! Alle unsere Möbel sind eingelagert. Analysieren wir die Ausgabe in dem wir den Algorithmus per Hand nachvollziehen.

Wir beginnen mit dem Stuhl mit Artikelnummer 12. Es ist 12 % 7 = 5, somit ist der Stuhl das erste Element in der Liste an Array-Position 5.

Als nächstes fügen wir den Sessel mit Artikelnummer 53 in die Datenstruktur ein. Es ist 53 % 7 = 4. Also ist der Sessel das erste Element in der Liste an Array-Position 4.

Bisher kein Unterschied zu unserem vorgehen von oben.

Jetzt der Schrank mit Artikelnummer 5. Es gilt 5 % 7 = 5. Aha, diese Hashadresse hatten wir bereits beim Stuhl, deshalb ist unser Schrank der ZWEITE Eintrag in der Liste an Array-Position 5.

Weiter geht’s mit dem Tisch mit Artikelnummer 15. Das mache ich kurz. Wegen 15 % 7 = 1 ist dies der erste Eintrag in der Liste an Array-Position 1.

Die Lampe mit Artikelnummer 2 überlass ich dir. Diese landet als erster Eintrag in der Liste bei Array-Position 2.

Das Sofa ist wieder spannend, denn genau wie beim Stuhl und dem Schrank haben wir hier die Hashadresse 19 % 7 = 5, weshalb das Sofa dem dritten Eintrag in der Liste an Array-Position 5 entspricht.

Leider hat die Methode der Verkettung der Überläufer einen Nachteil.

Dadurch, dass wir bei einer Kollision auf eine verkettete Liste umsteigen, ist der Zugriff auf Elemente über den Schlüssel der Datenstruktur nicht mehr eindeutig und nicht mehr so effizient möglich.

Nehmen wir an, wir suchen den Artikel mit der Nummer 12.

Es ist 12 % 7 = 5, d.h. wir greifen in unserem Lager-Array auf die Liste mit dem Inhalt Stuhl, Schrank und Sofa zu. In dieser müssen wir dann erneut nach dem richtigen Element suchen.

Offene Hashverfahren

Bei offenen Hashverfahren wird bei einer Kollision geprüft, ob im Lager-Array noch freie Plätze vorhanden sind, ist das der Fall, wird auf diese ausgewichen.

Hierfür müssen wir unsere Hashfunktion um eine sogenannte Sondierungsfunktion erweitern.

Hashmaps mit Sondierungsfunktion

Hier gibt es auch wieder mehrere Möglichkeiten. Fangen wir mit der einfachsten an, nämlich der linearen Sondierungsfunktion.

Die lineare Sondierungsfunktion

Immer dann, wenn eine Kollision auftritt, betrachten wir das Element, welches links von der Array-Position liegt, an der wir einfügen wollen.

Ist auch diese belegt, gehen wir eine weitere Position nach links. Falls auch hier kein Platz ist, wiederholen wir das Spielchen solange bis wir entweder einen freien Platz gefunden haben oder die erste Position des Arrays erreicht haben.

Finden wir links von der Hashadresse keinen freien Platz, inspizieren wir die Elemente rechts solange bis wir entweder einen freien Platz gefunden haben oder das Ende des Lager-Arrays erreichen.

Haben wir das Ende des Arrays erreicht und ist auch hier kein freier Platz verfügbar, wissen wir, dass die Kapazität unseres Lager-Arrays erreicht ist.

Überlegen wir uns wie wir das Verfahren in Quellcode formulieren können und passen unsere insert Einfüge-Methode entsprechend an.

1: public void insert(int k, String data){
2:  int key = divisionRestMethode(k);
3:  if (memory[key] == null){ 
4:	memory[key] = data;
5:  }else{
6:	int sondierung = 0;
7:	while((memory[key-sondierung] != null) && ((key-sondierung)>0)){
8:		sondierung++;
9:	}
10:	if(((key-sondierung)==0) && (memory[0] != null)){
11:	  sondierung = 0;
12:	  while((memory[key+sondierung] != null) && ((key+sondierung)<(memory.length-1))){
13:	      sondierung++;
14:	   }
15:	   if (memory[key+sondierung] == null){
16:		memory[key+sondierung] = data;
17:	   }
18:	}else{
19:		memory[key-sondierung] = data;
20:	}
21:  }
22:}

Wie gehabt berechnen wir in Zeile zwei die Hashadresse durch Aufruf der Methode divisionRestMethode(). Anschließend überprüfen wir, ob dieser Speicherplatz noch frei ist oder das Einfügen eines Datensatz zu einer Kollision führt.

Handelt es sich um eine freien Speicherplatz, fügen wir den Datensatz ein und sind fertig.

Stellen wir eine Kollision fest, kommt der Block Zeile 6-21 zum zug. Dieser besteht im Wesentlichen aus zwei while Schleifen.

In der ersten Schleife werden die Plätze rechts von der Hashadresse inspiziert.

Hierbei wird die Integer-Variable sondierung solange inkrementiert bis wir entweder einen freien Speicherplatz gefunden haben (dann gilt memory[key+sondierung] == null) oder den Anfang des Lager-Arrays erreicht haben (dann gilt (key-sondierung)==0)).

Die if Bedingung in Zeile 10 zehn überprüft, ob der gesamte Teil, der links von der Hashadresse liegt überprüft wurde und das erste Element des Lager-Arrays bereits einen Wert besitzt. In diesem Fall war die linksseitige Suche nicht erfolgreich und wir müssen die Elemente rechts der Hashadresse überprüfen. Andernfalls wurde ein freies Plätzchen gefunden, in das in Zeile 19 der zu speichernden Datensatz geschrieben wird.

Die rechtsseitige Überprüfung erfolgt in der zweiten while Schleife in den Zeilen 11-13. Hier wird die Integer Variable Sondierung solange inkrementiert bis entweder ein freier Speicherplatz gefunden wurde (dann gilt memory[key+sondierung] != null) oder das Ende des Arrays erreicht wurde (dann ist (key+sondierung)==(memory.length-1)).

Machen wir einen Probelauf und nehmen unsere Möbel ins Lager auf.

Bei dieser Gelegenheit testen wir auch gleich was passiert, wenn wir versuchen mehr als sieben Elemente in unser Lager einzufügen.

HashMapTest test = new HashMapTest(7);
test.insert(12,"Stuhl");
test.insert(53,"Sessel");
test.insert(5, "Schrank");
test.insert(15, "Tisch");
test.insert(2, "Lampe");
test.insert(19, "Sofa");
test.insert(98, "Matratze");
test.insert(110,"Bett");

Um zu sehen, ob es funktioniert hat, rufen wir die output Methode auf und geben den gesamten Inhalt auf den Bildschirm aus. Wir erhalten:

0: Key: 98 Sofa
1: Key: 15 Tisch
2: Key: 2 Lampe
3: Key: 0 Schrank
4: Key: 53 Sessel
5: Key: 110 Stuhl
6: Key: 0 Matratze

Super, das hat geklappt. Nur das achte Elemente, unser Bett, hat nicht mehr ins Lager gepasst.

Der Vollständigkeit wegen, wollen wir auch das nochmal per Hand durchführen.

Wie gewohnt berechnen wir die Hashadresse gemäß der Formel Artikelnummer % Lagerlänge. Das weißt du bereits, weshalb wir darauf nicht mehr im Detail eingehen brauchen.

1. Der Stuhl hat die Hashadresse 5. Dieser Platz ist noch frei, weshalb wir den Stuhl an Position fünf einlagern.

2. Der Sessel hat die Hashadresse 4. Da auch dieser Platz noch nicht belegt ist, ist die Einlagerung problemlos.

3. Der Schrank hat die Hashadresse 5. Moment! Die hatten wir schon. Gemäß unserem Algorithmus müssen wir daher die Plätze links der fünf inspizieren. Leider ist die 4 bereits mit dem Sessel belegt, weshalb uns nichts anderes übrig bleibt als den Schrank an Position drei zu lagern.

4. Der Tisch ist wieder problemlos. Dieser hat die Hashadresse 1, welche noch frei ist.

5. Auch haben wir bei der Lampe kein Problem. Die Hashadresse 2 ist ebenfalls frei.

6. Beim Sofa landen wir allerdings schon wieder bei der Hashadresse 5, die bereits vom Stuhl belegt ist, weshalb wir alle Plätze links von der fünf überprüfen müssen.

Auf Position 4 befindet sich bereits der Sessel. Auch ist auf Position 3 kein Platz, da hier der Schrank lagert. Ebenfalls schlecht ist Position 2, denn hier befindet sich eine Lampe. Auch haben wir Pech bei Nummer 1, denn die ist durch den Tisch blockiert. Glücklicherweise ist der Lagerplatz mit Nummer 0 noch frei, in dem wir das Sofa einlagern können.

7. Die Matratze hat die Hashadresse 0, welche aber bereits durch das Sofa belegt ist. Da es links von der Null keine Speicherplätze gibt, werden alle Lagerplätze größer 0 inspiziert. Der einzig verfügbare Speicherplatz ist die Adresse 6, in der wir die Matratze aufbewahren können.

8. Damit ist unser Lager voll und wir haben keinen Platz mehr für das Bett, mit Hashadresse 5.

Hier werden zuerst alle Speicherplätze mit einer Adresse kleiner fünf und danach alle Speicherplätze mit Adresse größer fünf geprüft. Da der Algorithmus auf beiden Seiten keinen freien Speicherplatz finden kann, wird das Bett nicht eingefügt. In der Praxis sollten wir in einem solchen Fall natürlich eine Exception werfen.

Die Suche in einer Hashmap

In unserem Beispiel hat der Stuhl, der Schrank und die Lampe die Hashadresse fünf.

Allerdings lässt sich lediglich der Stuhl über diese Hashadresse finden. Was machen wir also, wenn wir den Schrank oder die Lampe suchen?

In diesem Fall müssen wir genau wie wir es beim Einfüge-Algorithmus getan haben, zusätzlich die Plätze links und rechts von der Hashadresse, die wir mit Hilfe der Hashmap und der Artikelnummer berechnet haben inspizieren.

Um eine eindeutige Zuordnung vornehmen zu können, müssen wir die Datensätze in unserem Speicherarray um die Artikelnummer, also den Schlüssel erweitern.

Für diesen Zweck schreiben wir eine Klasse Node, in der wir den Möbeltyp als String und den Schlüssel als Integer speichern.

private class Node{
		
1:	private String data;
2:	private int key;
		
3:	public void setData(String pdata){
4:	   data = pdata;
5:	}
		
6:	public String getData(){
7:	  return data;
8:	}
		
9:	public void setKey(int pkey){
10:	   key = pkey;
11:	}
		
12:	public int getKey(){
13:	   return key;
14:	}		
15:}

Die Klasse besteht lediglich aus den Instanzvariablen, data, in der wir den Namen des Möbelstücks, und der Integer- Variablen key, in der wir den Schlüssel, d.h. die Artikelnummer speichern.

Aufgrund guten Programmierstils spendieren wir der Klasse außerdem entsprechende getter und setter Methoden.

Unser Lagerray, das bisher ein Array von String-Elementen war, ändern wir in ein Array bestehend aus Instanzen der Klasse Node.

1: Node[] memoryNode = new Node[7];
2: for(int i = 0;i<psize;i++){
3:	memoryNode[i] = new Node();
4:}

In Zeile eins erzeugen wir ein Array, das Platz für sieben Node Instanzen bietet, die wir in der for Schleife entsprechend initialisieren.

Um unser neues Lager-Array nutzen zu können, müssen wir unsere Einfüge-Methode anpassen. Was im Wesentlichen eine Ersetzung des Lager-Arrays vom Typ String durch das neue Node Arrays bedeutet.

1: public void insert3(int k, String data){
2:	int key = divisionRestMethode(k);
3:	if (memoryNode[key] == null){ 
4:		memoryNode[key].setData(data);
5:		memoryNode[key].setKey(k);
6:	}else{
7:		int sondierung = 0;
8:		while((memoryNode[key-sondierung].getData() != null) && ((key-sondierung)>0)){
9:			sondierung++;
10:		}
11:		if(((key-sondierung)==0) && (memoryNode[0].getData() != null)){
12:			sondierung = 0;
13:			while((memoryNode[key+sondierung].getData() != null) && ((key+sondierung)<    (memoryNode.length-1))){
14:				sondierung++;
15:			}
16:			if (memoryNode[key+sondierung].getData() == null){
17:				memoryNode[key+sondierung].setData(data);
18:				memoryNode[key+sondierung].setKey(k);
19:			}
20:		}else{
21:			memoryNode[key-sondierung].setData(data);
22:			memoryNode[key-sondierung].setKey(k);
23:		}
24:	}
25:}

Die Funktionsweise der Methode bleibt unverändert. Wir müssen nur daran denken die Daten und den Schlüssel über die entsprechenden setter Methoden in der Node-Instanz zu sichern.

Wenden wir uns der Suche zu.

Die Suche implementieren wir in einer Methode find, die als Parameter den Schlüssel, d.h. in unserem Fall die Artikelnummer erwartet. Der Rückgabewert der Methode ist ein String, in dem wir den Namen des gefundenen Möbelstücks speichern.

1: public String find(int k){
2:	int key = divisionRestMethode(k);
3:	int sondierung = key;
4:	while((memoryNode[sondierung].getKey() != k) && (sondierung > 0)){
5:		sondierung--;
6:	}
7:	if(memoryNode[sondierung].getKey() == k){
8:	  return memoryNode[sondierung].getData();
9:	}else{
10:	  sondierung = key;
11:	  while((memoryNode[sondierung].getKey() != k) && (sondierung < (memoryNode.length - 1))){
12:		sondierung++;
13:	  }
14:	  if(memoryNode[sondierung].getKey() == k){
15:		return memoryNode[sondierung].getData();
15:	  }else{
17:		return null;
18:	  }
19:	}
20:}

In Zeile zwei bestimmen wir zunächst die Hashadresse, an der wir mit unserer Suche beginnen.

Falls der Datensatz an der Position der Hashadresse nicht dem gesuchten Schlüssel entspricht inspizieren wir zunächst alle Einträge links der Hashadresse.

Hierfür dekrementieren wir in der while Schleife die Variable sondierung solange bis wir entweder den gesuchten Schlüssel gefunden haben oder den Beginn des Lagerarrays erreicht haben.

Haben wir den gesuchten Schlüssel gefunden, geben wir in Zeile 8 die zu diesem Schlüssel gehörenden Daten aus, andernfalls müssen wir unsere Suche auf der rechten Seite der Hashadresse fortsetzen.

Und genau das passiert in der while Schleife in den Zeilen 11-13, in der die Variable sondierung solange inkrementiert wird bis entweder der gesuchte Schlüssel gefunden wurde oder das Ende des Lager-Arrays erreicht ist.

Im ersten Fall geben wir die zu dem Schlüssel gehörenden Daten aus (Zeile 15). Tritt der zweite Fall ein, bedeutet dies, dass zu dem gesuchten Schlüssel keine Daten existieren und wir daher in Zeile 17 einen Null-String zurückgeben.

Fazit

Wie du siehst ist die Hashmap eine echt coole Datenstruktur mit der du recht einfach eine kleine Datenbank aufbauen kannst. Auch hier gibt es wieder zahlreiche Möglichkeiten die Datenstruktur zu tunen.

Ein über Hashmaps realisierter Assoziativspeicher ist besonders effizient, wenn die Hashfunktion einfach zu berechnen ist und selten Kollisionen erzeugt.

Die Häufigkeit von Kollisionen hängt insbesondere von der Wahl der Sondierungsfunktion ab. Der Einfachheit wegen haben wir uns in diesem Artikel auf die lineare Sondierung beschränkt.

Diese ist zwar leicht zu verstehen, bezüglich auftretenden Kollisionen aber nicht ideal. Hier sollte besser auf das double Hashing oder das quadratische Hashing ausgewichen werden.

Diesen Hashfunktionen werde ich einen eigenen Artikel widmen.

Eine in der Praxis bewährte Methode Kollisionen zu verringern ist, die Größe des Lager-Arrays so zu wählen, dass diese doppelt so groß wie der tatsächlich zu erwartene Speicherbedarf ist.

Aber egal, für welche Hashfunktion du dich entscheidest, bleibt das Prinzip des über Hashmaps realisierten Assoziativspeichers stets das selbe.

In diesem Artikel ging es mir lediglich darum dir ein Verständnis der Hashmaps zu vermitteln. Wenn du Hashmaps in der Praxis einsetzt macht es natürlich sinn hierfür die Java Klasse Hashmap zu verwenden. Wie das geht zeige ich dir im folgenden Video:

Java Hashmap mit Hilfe der Standardbibliothek

Wie immer freue ich mich über deine Fragen im Kommentarbereich!

Hat dir der Artikel gefallen? Dann folge uns doch am besten gleich auf Facebook!