Werbung

Hash Table ist eine Datenstruktur, die Daten assoziativ speichert. In einer Hash-Tabelle werden die Daten in einem Array-Format gespeichert, wobei jeder Datenwert seinen eigenen eindeutigen Indexwert hat. Der Zugriff auf die Daten wird sehr schnell, wenn wir den Index der gewünschten Daten kennen.

So wird sie zu einer Datenstruktur, in der Einfüge- und Suchvorgänge unabhängig von der Größe der Daten sehr schnell sind. Die Hash-Tabelle verwendet ein Array als Speichermedium und nutzt die Hash-Technik, um einen Index zu erzeugen, in den ein Element eingefügt oder von dem aus es gesucht werden soll.

Hashing

Hashing ist eine Technik zur Umwandlung eines Bereichs von Schlüsselwerten in einen Bereich von Indizes eines Arrays. Wir werden den Modulo-Operator verwenden, um einen Bereich von Schlüsselwerten zu erhalten. Nehmen wir ein Beispiel für eine Hash-Tabelle der Größe 20, in der die folgenden Elemente gespeichert werden sollen. Die Elemente haben das Format (Schlüssel, Wert).

Hash-Funktion

  • (1,20)
  • (2,70)
  • (42,80)
  • (4,25)
  • (12,44)
  • (14,32)
  • (17,11)
  • (13,78)
  • (37,98)
Sr.Nr. Schlüssel Hash Array Index
1 1 1 % 20 = 1 1
2 2 2 % 20 = 2 2
3 42 42 % 20 = 2 2
4 4 4 % 20 = 4 4
5 12 12 % 20 = 12 12
6 14 14 % 20 = 14 14
7 17 17 % 20 = 17 17
8 13 13 % 20 = 13 13
9 37 37 % 20 = 17 17

Linear Probing

Wie wir sehen können, kann es vorkommen, dass die Hashing-Technik verwendet wird, um einen bereits verwendeten Index des Arrays zu erstellen. In einem solchen Fall können wir die nächste leere Stelle im Array suchen, indem wir in die nächste Zelle schauen, bis wir eine leere Zelle finden. Diese Technik wird lineares Sondieren genannt.

Sr.Nr. Schlüssel Hash Array Index Nach Linear Probing, Array Index
1 1 1 % 20 = 1 1 1
2 2 2 % 20 = 2 2 2
3 42 42 % 20 = 2 2 3
4 4 4 % 20 = 4 4 4
5 12 12 % 20 = 12 12 12
6 14 14 % 20 = 14 14 14
7 17 17 % 20 = 17 17 17
8 13 13 % 20 = 13 13 13
9 37 37 % 20 = 17 17 18

Grundlegende Operationen

Nachfolgend sind die grundlegenden primären Operationen einer Hashtabelle aufgeführt.

  • Suchen – Sucht ein Element in einer Hashtabelle.

  • Einfügen – Fügt ein Element in eine Hashtabelle ein.

  • Löschen – Löscht ein Element aus einer Hashtabelle.

DataItem

Definiere ein Datenelement mit einigen Daten und einem Schlüssel, auf dessen Grundlage die Suche in einer Hash-Tabelle durchgeführt werden soll.

struct DataItem { int data; int key;};

Hash-Methode

Definieren Sie eine Hash-Methode, um den Hash-Code des Schlüssels des Datenelements zu berechnen.

int hashCode(int key){ return key % SIZE;}

Suchvorgang

Wenn ein Element gesucht werden soll, berechnen Sie den Hash-Code des übergebenen Schlüssels und suchen Sie das Element mit diesem Hash-Code als Index im Array. Verwenden Sie lineares Sondieren, um das Element zu finden, wenn das Element nicht mit dem berechneten Hash-Code gefunden wird.

Beispiel

struct DataItem *search(int key) { //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray != NULL) { if(hashArray->key == key) return hashArray; //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; }

Einfügevorgang

Wann immer ein Element eingefügt werden soll, berechnen Sie den Hash-Code des übergebenen Schlüssels und suchen Sie den Index mit diesem Hash-Code als Index im Array. Verwenden Sie lineares Sondieren für eine leere Stelle, wenn ein Element am berechneten Hash-Code gefunden wird.

Beispiel

void insert(int key,int data) { struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem)); item->data = data; item->key = key; //get the hash int hashIndex = hashCode(key); //move in array until an empty or deleted cell while(hashArray != NULL && hashArray->key != -1) { //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } hashArray = item; }

Löschvorgang

Wann immer ein Element gelöscht werden soll, berechnen Sie den Hash-Code des übergebenen Schlüssels und suchen Sie den Index unter Verwendung dieses Hash-Codes als Index im Array. Wenn ein Element mit dem berechneten Hash-Code nicht gefunden wird, wird das Element durch lineares Sondieren ermittelt. Wenn es gefunden wurde, speichern Sie dort ein Dummy-Element, um die Leistung der Hash-Tabelle intakt zu halten.

Beispiel

struct DataItem* delete(struct DataItem* item) { int key = item->key; //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray !=NULL) { if(hashArray->key == key) { struct DataItem* temp = hashArray; //assign a dummy item at deleted position hashArray = dummyItem; return temp; } //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; }

Um mehr über die Hash-Implementierung in der Programmiersprache C zu erfahren, klicken Sie bitte hier.

Werbung