Hash-tabelle

In diesem Tutorial erfahren Sie, was eine Hash-Tabelle ist. Außerdem finden Sie Arbeitsbeispiele für Hash-Tabellenoperationen in C, C ++, Java und Python.

Die Hash-Tabelle ist eine Datenstruktur, die Daten in Form von Schlüssel-Wert- Paaren darstellt. Jeder Schlüssel ist einem Wert in der Hash-Tabelle zugeordnet. Die Schlüssel dienen zur Indizierung der Werte / Daten. Ein ähnlicher Ansatz wird von einem assoziativen Array angewendet.

Die Daten werden mit Hilfe von Schlüsseln in einem Schlüsselwertpaar dargestellt (siehe Abbildung unten). Jeder Daten ist ein Schlüssel zugeordnet. Der Schlüssel ist eine Ganzzahl, die auf die Daten verweist.

1. Direkte Adresstabelle

Die direkte Adresstabelle wird verwendet, wenn der von der Tabelle verwendete Speicherplatz für das Programm kein Problem darstellt. Hier nehmen wir das an

  • Die Schlüssel sind kleine ganze Zahlen
  • die Anzahl der Schlüssel ist nicht zu groß, und
  • Keine zwei Daten haben den gleichen Schlüssel

Ein Pool von ganzen Zahlen wird als Universum bezeichnet U = (0, 1,… ., n-1).
Jeder Slot einer direkten Adresstabelle T(0… n-1)enthält einen Zeiger auf das Element, das den Daten entspricht.
Der Index des Arrays Tist der Schlüssel selbst und der Inhalt von Tist ein Zeiger auf die Menge (key, element). Wenn es für einen Schlüssel kein Element gibt, bleibt es als NULL.

Manchmal sind die Daten der Schlüssel.

Pseudocode für Operationen

 directAddressSearch(T, k) return T(k) directAddressInsert(T, x) T(x.key) = x directAddressDelete(T, x) T(x.key) = NIL

Einschränkungen einer direkten Adresstabelle

  • Der Wert des Schlüssels sollte klein sein.
  • Die Anzahl der Schlüssel muss klein genug sein, damit die Größenbeschränkung eines Arrays nicht überschritten wird.

2. Hash-Tabelle

In einer Hash-Tabelle werden die Schlüssel verarbeitet, um einen neuen Index zu erstellen, der dem erforderlichen Element zugeordnet ist. Dieser Vorgang wird als Hashing bezeichnet.

Sei h(x)eine Hash-Funktion und ksei ein Schlüssel.
h(k)wird berechnet und als Index für das Element verwendet.

Einschränkungen einer Hash-Tabelle

  • Wenn der gleiche Index von der Hash-Funktion für mehrere Schlüssel erzeugt wird, entsteht ein Konflikt. Diese Situation nennt man Kollision.
    Um dies zu vermeiden, wird eine geeignete Hash-Funktion ausgewählt. Es ist jedoch unmöglich, alle eindeutigen Schlüssel zu erstellen, da |U|>m. Daher kann eine gute Hash-Funktion die Kollisionen möglicherweise nicht vollständig verhindern, jedoch die Anzahl der Kollisionen verringern.

Wir haben jedoch andere Techniken, um Kollisionen aufzulösen.

Vorteile der Hash-Tabelle gegenüber der direkten Adresstabelle:

Die Hauptprobleme bei der direkten Adresstabelle sind die Größe des Arrays und der möglicherweise große Wert eines Schlüssels. Die Hash-Funktion reduziert den Indexbereich und damit auch die Größe des Arrays.
Zum Beispiel If k = 9845648451321, then h(k) = 11(mithilfe einer Hash-Funktion). Dies hilft beim Speichern des verschwendeten Speichers, während der Index des 9845648451321Arrays bereitgestellt wird

Kollisionsauflösung durch Verkettung

Wenn bei dieser Technik eine Hash-Funktion denselben Index für mehrere Elemente erzeugt, werden diese Elemente unter Verwendung einer doppelt verknüpften Liste im selben Index gespeichert.

Wenn jder Steckplatz für mehrere Elemente ist, enthält er einen Zeiger auf den Kopf der Liste der Elemente. Wenn kein Element vorhanden ist, jenthält NIL.

Pseudocode für Operationen

 chainedHashSearch(T, k) return T(h(k)) chainedHashInsert(T, x) T(h(x.key)) = x //insert at the head chainedHashDelete(T, x) T(h(x.key)) = NIL

Python-, Java-, C- und C ++ - Implementierung

Python Java C C ++ 
 # Python program to demonstrate working of HashTable hashTable = ((),) * 10 def checkPrime(n): if n == 1 or n == 0: return 0 for i in range(2, n//2): if n % i == 0: return 0 return 1 def getPrime(n): if n % 2 == 0: n = n + 1 while not checkPrime(n): n += 2 return n def hashFunction(key): capacity = getPrime(10) return key % capacity def insertData(key, data): index = hashFunction(key) hashTable(index) = (key, data) def removeData(key): index = hashFunction(key) hashTable(index) = 0 insertData(123, "apple") insertData(432, "mango") insertData(213, "banana") insertData(654, "guava") print(hashTable) removeData(123) print(hashTable) 
 // Java program to demonstrate working of HashTable import java.util.*; class HashTable ( public static void main(String args()) ( Hashtable ht = new Hashtable(); ht.put(123, 432); ht.put(12, 2345); ht.put(15, 5643); ht.put(3, 321); ht.remove(12); System.out.println(ht); ) ) 
 // Implementing hash table in C #include #include struct set ( int key; int data; ); struct set *array; int capacity = 10; int size = 0; int hashFunction(int key) ( return (key % capacity); ) int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i < n / 2; i++) ( if (n % i == 0) ( return 0; ) ) return 1; ) int getPrime(int n) ( if (n % 2 == 0) ( n++; ) while (!checkPrime(n)) ( n += 2; ) return n; ) void init_array() ( capacity = getPrime(capacity); array = (struct set *)malloc(capacity * sizeof(struct set)); for (int i = 0; i < capacity; i++) ( array(i).key = 0; array(i).data = 0; ) ) void insert(int key, int data) ( int index = hashFunction(key); if (array(index).data == 0) ( array(index).key = key; array(index).data = data; size++; printf(" Key (%d) has been inserted ", key); ) else if (array(index).key == key) ( array(index).data = data; ) else ( printf(" Collision occured "); ) ) void remove_element(int key) ( int index = hashFunction(key); if (array(index).data == 0) ( printf(" This key does not exist "); ) else ( array(index).key = 0; array(index).data = 0; size--; printf(" Key (%d) has been removed ", key); ) ) void display() ( int i; for (i = 0; i < capacity; i++) ( if (array(i).data == 0) ( printf(" array(%d): / ", i); ) else ( printf(" key: %d array(%d): %d ", array(i).key, i, array(i).data); ) ) ) int size_of_hashtable() ( return size; ) int main() ( int choice, key, data, n; int c = 0; init_array(); do ( printf("1.Insert item in the Hash Table" "2.Remove item from the Hash Table" "3.Check the size of Hash Table" "4.Display a Hash Table" " Please enter your choice: "); scanf("%d", &choice); switch (choice) ( case 1: printf("Enter key -: "); scanf("%d", &key); printf("Enter data -: "); scanf("%d", &data); insert(key, data); break; case 2: printf("Enter the key to delete-:"); scanf("%d", &key); remove_element(key); break; case 3: n = size_of_hashtable(); printf("Size of Hash Table is-:%d", n); break; case 4: display(); break; default: printf("Invalid Input"); ) printf("Do you want to continue (press 1 for yes): "); scanf("%d", &c); ) while (c == 1); )
 // Implementing hash table in C++ #include #include using namespace std; class HashTable ( int capacity; list *table; public: HashTable(int V); void insertItem(int key, int data); void deleteItem(int key); int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i  capacity = size; table = new list(capacity); ) void HashTable::insertItem(int key, int data) ( int index = hashFunction(key); table(index).push_back(data); ) void HashTable::deleteItem(int key) ( int index = hashFunction(key); list::iterator i; for (i = table(index).begin(); i != table(index).end(); i++) ( if (*i == key) break; ) if (i != table(index).end()) table(index).erase(i); ) void HashTable::displayHash() ( for (int i = 0; i < capacity; i++) ( cout << "table(" << i << ")"; for (auto x : table(i)) cout < " << x; cout << endl; ) ) int main() ( int key() = (231, 321, 212, 321, 433, 262); int data() = (123, 432, 523, 43, 423, 111); int size = sizeof(key) / sizeof(key(0)); HashTable h(size); for (int i = 0; i < n; i++) h.insertItem(key(i), data(i)); h.deleteItem(12); h.displayHash(); )

Gute Hash-Funktionen

Eine gute Hash-Funktion hat die folgenden Eigenschaften.

  1. Es sollten keine zu großen Schlüssel generiert werden und der Bucket Space ist klein. Platz wird verschwendet.
  2. Die generierten Schlüssel sollten weder sehr nah noch zu weit entfernt sein.
  3. Die Kollision muss so weit wie möglich minimiert werden.

Einige der zum Hashing verwendeten Methoden sind:

Teilungsmethode

Wenn kes sich um einen Schlüssel und mdie Größe der Hash-Tabelle handelt, wird die Hash-Funktion wie h()folgt berechnet:

h(k) = k mod m

Zum Beispiel, wenn die Größe einer Hash-Tabelle ist 10und k = 112dann h(k) = 112mod 10 = 2. Der Wert von mdarf nicht die Macht von sein 2. Dies liegt daran, dass die Potenzen 2im Binärformat sind 10, 100, 1000,… . Wenn wir finden k mod m, erhalten wir immer die p-Bits niedrigerer Ordnung.

 wenn m = 22, k = 17, dann ist h (k) = 17 mod 22 = 10001 mod 100 = 01 wenn m = 23, k = 17, dann ist h (k) = 17 mod 22 = 10001 mod 100 = 001 wenn m = 24, k = 17, dann h (k) = 17 mod 22 = 10001 mod 100 = 0001, wenn m = 2p, dann h (k) = p untere Bits von m

Multiplikationsmethode

h(k) = ⌊m(kA mod 1)⌋
wo,

  • kA mod 1gibt den Bruchteil an kA,
  • ⌊ ⌋ gibt den Bodenwert an
  • Aist eine beliebige Konstante. Der Wert von Aliegt zwischen 0 und 1. ≈ (√5-1)/2Knuth schlägt jedoch eine optimale Wahl vor.

Universal Hashing

Beim universellen Hashing wird die Hash-Funktion unabhängig von den Tasten zufällig ausgewählt.

Adressierung öffnen

In einer normalen Hash-Tabelle können mehrere Werte in einem einzigen Slot gespeichert werden.

Bei Verwendung der offenen Adressierung wird jeder Steckplatz entweder mit einem einzelnen Schlüssel gefüllt oder bleibt übrig NIL. Alle Elemente werden in der Hash-Tabelle selbst gespeichert.

Im Gegensatz zur Verkettung können nicht mehrere Elemente in denselben Steckplatz passen.

Offene Adressierung ist im Grunde eine Kollisionslösungstechnik. Einige der von der offenen Adressierung verwendeten Methoden sind:

Lineare Abtastung

Bei der linearen Abtastung wird die Kollision durch Überprüfen des nächsten Schlitzes behoben.
h(k, i) = (h'(k) + i) mod m
wo,

  • i = (0, 1,… .)
  • h'(k) ist eine neue Hash-Funktion

Wenn eine Kollision um auftritt h(k, 0), h(k, 1)wird geprüft. Auf diese Weise wird der Wert von ilinear erhöht.
Das Problem bei der linearen Abtastung besteht darin, dass ein Cluster benachbarter Schlitze gefüllt ist. Beim Einfügen eines neuen Elements muss der gesamte Cluster durchlaufen werden. Dies erhöht die Zeit, die zum Ausführen von Operationen an der Hash-Tabelle erforderlich ist.

Quadratische Prüfung

Bei der quadratischen Abtastung wird der Abstand zwischen den Schlitzen unter Verwendung der folgenden Beziehung vergrößert (größer als eins). wo,
h(k, i) = (h'(k) + c1i + c2i2) mod m

  • c1und sind positive Hilfskonstanten,c2
  • i = (0, 1,… .)

Doppeltes Hashing

Wenn nach dem Anwenden einer Hash-Funktion eine Kollision auftritt, wird eine h(k)andere Hash-Funktion berechnet, um den nächsten Slot zu finden.
h(k, i) = (h1(k) + ih2(k)) mod m

Hash-Tabellenanwendungen

Hash-Tabellen werden wo implementiert

  • Eine konstante Zeitsuche und Einfügung ist erforderlich
  • kryptografische Anwendungen
  • Indizierungsdaten sind erforderlich

Interessante Beiträge...