Assoziative Arrays als Hashmaps selbst verwalten

Viele Programmier- und Scriptsprachen (allen voran Perl und PHP) bieten eine Datenstruktur namens „assoziatives Array“ an. Diese „assoziativen Arrays“ können Daten aufnehmen und erlauben das effiziente Suchen dar in. Computer beherrschen die Organisation von Daten in „assoziativen Arrays“ allerdings nicht von Haus aus wie etwas das speichern in „normalen“ Arrays durch Adressierung. Aus diesem Grund muss der Entwickler selbst (oder seine Programmiersprache) für diese Organisation sorgen. In der Tat gibt es für quasi alle Programmiersprachen entsprechende Implementationen. Für den interessierten Entwickler möchte ich heute aber mal zeigen wie genau diese Datenorganisation von statten geht und eine eigene rudimentäre Implementation in C++ anbieten.

Vorüberlegungen

Die Technik, mit der „assoziative Arrays“ in der Regel organisiert sind heißen Hashmaps oder auch Hashtables. In Java heißen die Klassen für die Benutzung von „assoziativen Arrays“ auch entsprechend. Um zu zeigen wie eine Hashmap funktioniert möchte ich zunächst darauf eingehen, wie man naiv die Daten speichern würde.

Jeder Eintrag besteht aus einem Daten paar – dem Schlüssel und dem Wert. Man definiert zuerst, dass der Schlüssel eine endliche Zeichenkette darstellt. Der Datentyp, der als „Wert“ gespeichert werden soll, soll dabei undefiniert bleiben um jeden Datentyp als Wert zu verwenden.

Wenn nun z.B. ein Paar (’Schlüssel’, ‘Wert’) gespeichert werden soll, dann würde man z.B. eine Datenstruktur (C++) anlegen, die folgendermaßen aussieht:

typedef struct item
{
	char *key;
	void *value;
}

Hashmaps

Diese würde man in einem „normalen“ Array abspeichern.
Um nun zu einem Schlüssel wieder den abgespeicherten Wert zu bekommen geht man alle definierten Elemente des Arrays durch und vergleicht den Eintrag „key“ mit dem gesuchten Schlüssel. Gibt es eine Übereinstimmung, so wird der „Wert“ zurückgeliefert.

Die Daten so zu organisieren man auf den ersten Blick als logisch erscheinen, ist aber vor allem bei großen Datenmengen denkbar ineffizient. Sollte sich der gesuchte Datensatz am Ende des Arrays befinden müssen alle eingetragen Daten auf den Suchschlüssel geprüft werden.

Um die Daten deutlich effizienter für den Lesezugriff zu speichern kann man die oben erwähnten Hashmaps verwenden.

Statt das jeder Eintrag sequentiell in das Array geschrieben wird, wird bei einer Hashmap der Eintrag an eine strategisch bessere Position, nämlich einer anhand des Schlüssels schnell wieder auffindbaren Position, gespeichert.
Dies ist möglich indem man über den Schlüssel mittels einer Hashfunktion einen so genannten Hashwert bildet.

Laut Wikipedia wird eine Hashfunktion folgendermaßen definiert:

Eine Hash-Funktion bzw. Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe aus einer im Allgemeinen kleineren Zielmenge erzeugt. Diese Hash-Werte bzw. Streuwerte sind meist skalare Werte aus einer Teilmenge der natürlichen Zahlen. Ein Hash-Wert wird auch als Fingerprint bezeichnet. Denn wie ein Fingerabdruck einen Menschen nahezu eindeutig identifiziert, ist ein Hash-Wert eine nahezu eindeutige Kennzeichnung einer übergeordneten Menge.

Man kann also sagen, dass man die Hashfunktion dafür benutzt um (in diesem Fall) aus einem String einen möglichst eindeutigen Integer zu machen. Diese Funktion ist allerdings in der Regel nicht reversibel – man kann also aus dem Hash-Wert nicht mehr den dazugehörigen Schlüssel erzeugen. Eine solche Funktion sollte in der Lage sein möglichst selten für unterschiedliche Strings den gleichen Integerwert zu erzeugen. Falls dies passiert (und es wird passieren) nennt man diesen Zustand eine Kollision und muss ihn extra behandeln. Außerdem muss die Funktion Integer-Werte innerhalb eines definierten Wertebereichs erzeugen. Der größtmögliche Wert entspricht der Größe des Arrays.

Hashfunktionen

Es gibt verschiedene Hashfunktionen. In diesem Fall habe ich die sogenannte „Divisionsrestmethode“ verwendet. Aber auch jede andere Hashfunktion sollte man statt dieser verwenden können.

long HashTable::createHash(long size, char *key)
{
	long m = size;
 
	if (strlen(key) == 0) return -1;
 
	long h = key[1] % m;
	for (unsigned int i = 0; i < strlen(key); i++)
	{
		h = (h * 128 + key[i]) % m;
	}
	return h;
}

In der Variable „size“ wird der maximal zu erzeugende Integer-Wert übergeben.

Implementation der Hashmaps

Der so erzeugte Integerwert kann nun direkt als Schlüssel für das Array benutzt werden, wenn es keine Kollision gibt. Sollte es doch einen Kollision geben, so muss man sich eine Strategie einfallen lassen die Daten an einer anderen Position abzuspeichern. Grundsätzlich gilt hier:

Je größer verwendete Array um so kleiner ist die Wahrscheinlichkeit einer Kollision.

Hier einige Möglichkeiten wie man bei einer Kollision vorgeht:

Den nächsten freien Platz im Array verwenden (kann im bei sehr geringer Tabellengröße eine Rückkehr zur naiven Speicherung bedeuten)
Verwenden einer bzw. mehrerer alternativer Hashfunktionen.
Anlegen einer neuen Hashmap innerhalb für den betroffenen Datensatz.
Dynamisches vergrößern des Datenarrays. (Hat zur Folge, dass die im schlechtesten Fall bei jedem Schreibzugriff die komplette Tabelle umorganisiert werden muss)

Ich habe ich für die Variante entschieden eine neue Hashmap innerhalb des betroffenen Datensatzes zu erzeugen, weil dadurch die Tabelle bzw. das Array anfangs klein gehalten werden kann. Nicht immer hat man eine Vorstellung davon, wie groß die Datenmenge ist, die man in der Hashmap speichern will.
Bei meinem Beispiel werden rekursiv je nach Verwendung weitere Hashmaps angelegt, die jeweils eine um eins vergrößerte Länge als die aufrufende Hashmap haben. Somit ist garantiert, dass der zu schreibende Datensatz immer einen Platz in der Tabelle hat.

Klasse HashTable:

#include <iostream>
#include "HashTable.h"
 
using namespace std;
 
HashTable::HashTable()
{
	m_tableSize = 1;
	m_data = new bucket[m_tableSize];
}
 
HashTable::HashTable(long tableSize)
{
	m_tableSize = tableSize;
	m_data = new bucket[m_tableSize];
}
 
HashTable::~HashTable()
{
	for (int i = 0; i < m_tableSize; i++)
 
	{
		delete m_data[i].ht;
	}
	delete [] m_data;
}
 
void *HashTable::get(char *key)
{
	long nKey = createHash(m_tableSize, key);
	if (nKey < m_tableSize)
	{
		if (m_data[nKey].used)
		{
			if (m_data[nKey].key == key)
			{
				if (m_data[nKey].single) return m_data[nKey].value;
			}
			if (!m_data[nKey].single)
			{
				if (m_data[nKey].ht) return m_data[nKey].ht->get(key);
			}
		}
	}
	return false;
}
 
bool HashTable::add(char *key, void *value)
{
	long nKey = createHash(m_tableSize, key);
	if (nKey < m_tableSize)
	{
		if (!m_data[nKey].used)
		{
			m_data[nKey].used = true;
			m_data[nKey].single = true;
			m_data[nKey].key = key;
			m_data[nKey].value = value;
			return true;
		}
		else
		{
			if (m_data[nKey].single)
			{
				m_data[nKey].ht = new HashTable(m_tableSize + 1);
				m_data[nKey].ht->add(m_data[nKey].key, m_data[nKey].value);
				m_data[nKey].single = false;
				m_data[nKey].key = false;
				m_data[nKey].value = false;
			}
			if (m_data[nKey].ht != 0)
			{
				m_data[nKey].ht->add(key, value);
				return true;
			}
		}
	}
	return false;
}
 
long HashTable::createHash(long size, char *key)
{
	long m = size;
 
	if (strlen(key) == 0) return -1;
 
	long h = key[1] % m;
	for (unsigned int i = 0; i < strlen(key); i++)
	{
		h = (h * 128 + key[i]) % m;
	}
	return h;
}

Dazugehörige Header-Datei:

class HashTable
{
protected:
	long m_tableSize;
 
	static long createHash(long size, char *key);
 
public:
 
	typedef struct bucket
	{
		bool used;
		bool single;
		char *key;
		void *value;
		HashTable *ht;
	};
 
	HashTable();
	HashTable(long tableSize);
	virtual ~HashTable();
 
	bool add(char *key, void *value);
	void *get(char *key);
 
	bucket *m_data;
};