Datenstruktur und Algorithmen - Hash-Tabelle

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

Somit wird es zu einer Datenstruktur, in der Einfüge- und Suchvorgänge unabhängig von der Größe der Daten sehr schnell sind. Hash Table verwendet ein Array als Speichermedium und generiert mithilfe der Hash-Technik einen Index, in den ein Element eingefügt werden soll oder von dem aus es gefunden werden soll.

Hashing

Hashing ist eine Technik zum Konvertieren eines Bereichs von Schlüsselwerten in einen Bereich von Indizes eines Arrays. Wir werden den Modulo-Operator verwenden, um eine Reihe von Schlüsselwerten zu erhalten. Betrachten Sie ein Beispiel für eine Hash-Tabelle der Größe 20, und die folgenden Elemente müssen gespeichert werden. Artikel sind im Format (Schlüssel, Wert).

(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

Lineare Abtastung

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 durchsuchen, indem wir in die nächste Zelle schauen, bis wir eine leere Zelle finden. Diese Technik wird als lineare Abtastung bezeichnet.

Sr.Nr.	Schlüssel	Hash	Array-Index	Nach der linearen Prüfung 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

Grundoperationen

Im Folgenden sind die grundlegenden primären Operationen einer Hash-Tabelle aufgeführt.

Search - Sucht ein Element in einer Hash-Tabelle.
Insert - fügt ein Element in eine Hash-Tabelle ein.
delete - Löscht ein Element aus einer Hash-Tabelle.

DataItem

Definieren Sie ein Datenelement mit einigen Daten und Schlüsseln, anhand dessen die Suche in einer Hash-Tabelle durchgeführt werden soll.

struct DataItem {
   int data;
   int key;
};

Hash-Methode

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

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

Suchvorgang

Wenn ein Element durchsucht werden soll, berechnen Sie den Hash-Code des übergebenen Schlüssels und suchen Sie das Element anhand dieses Hash-Codes als Index im Array. Verwenden Sie die lineare Prüfung, um das Element voranzubringen, wenn das Element im berechneten Hash-Code nicht gefunden wird.

Beispiel

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

   return NULL;        
}

Operation einfügen

Wenn ein Element eingefügt 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. Verwenden Sie die lineare Prüfung für die leere Position, wenn im berechneten Hashcode ein Element 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[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }
	
   hashArray[hashIndex] = item;        
}

Vorgang löschen

Wenn 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. Verwenden Sie die lineare Prüfung, um das Element voranzubringen, wenn im berechneten Hash-Code kein Element gefunden wird. Wenn gefunden, speichern Sie dort ein Dummy-Element, um die Leistung der Hash-Tabelle aufrechtzuerhalten.

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[hashIndex] !=NULL) {
	
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
			
         //assign a dummy item at deleted position
         hashArray[hashIndex] = 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 .