Tabella hash

In questo tutorial imparerai cos'è la tabella hash. Inoltre, troverai esempi funzionanti di operazioni con tabelle hash in C, C ++, Java e Python.

La tabella hash è una struttura dati che rappresenta i dati sotto forma di coppie chiave-valore . Ogni chiave è mappata a un valore nella tabella hash. Le chiavi vengono utilizzate per indicizzare i valori / dati. Un approccio simile viene applicato da un array associativo.

I dati sono rappresentati in una coppia chiave-valore con l'aiuto di chiavi come mostrato nella figura seguente. Ogni dato è associato a una chiave. La chiave è un numero intero che punta ai dati.

1. Tabella degli indirizzi diretti

La tabella degli indirizzi diretti viene utilizzata quando la quantità di spazio utilizzata dalla tabella non è un problema per il programma. Qui, lo assumiamo

  • le chiavi sono piccoli numeri interi
  • il numero di chiavi non è troppo grande e
  • non esistono due dati con la stessa chiave

Viene considerato un pool di numeri interi chiamato universo U = (0, 1,… ., n-1).
Ogni slot di una tabella di indirizzi diretti T(0… n-1)contiene un puntatore all'elemento che corrisponde ai dati.
L'indice dell'array Tè la chiave stessa e il contenuto di Tè un puntatore all'insieme (key, element). Se non è presente alcun elemento per una chiave, viene lasciato come NULL.

A volte, la chiave stessa sono i dati.

Pseudocodice per le operazioni

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

Limitazioni di una tabella di indirizzi diretti

  • Il valore della chiave dovrebbe essere piccolo.
  • Il numero di chiavi deve essere sufficientemente piccolo da non superare il limite di dimensione di un array.

2. Tabella hash

In una tabella hash, le chiavi vengono elaborate per produrre un nuovo indice che esegue il mapping all'elemento richiesto. Questo processo è chiamato hashing.

Sia h(x)una funzione hash e ksia una chiave.
h(k)viene calcolato e viene utilizzato come indice per l'elemento.

Limitazioni di una tabella hash

  • Se lo stesso indice viene prodotto dalla funzione hash per più chiavi, sorge un conflitto. Questa situazione è chiamata collisione.
    Per evitare ciò, viene scelta una funzione hash adatta. Tuttavia, è impossibile produrre tutte le chiavi univoche perché |U|>m. Quindi una buona funzione hash potrebbe non impedire completamente le collisioni, tuttavia può ridurre il numero di collisioni.

Tuttavia, abbiamo altre tecniche per risolvere la collisione.

Vantaggi della tabella hash rispetto alla tabella degli indirizzi diretti:

I problemi principali con la tabella degli indirizzi diretti sono la dimensione dell'array e il valore possibilmente grande di una chiave. La funzione hash riduce l'intervallo dell'indice e quindi viene ridotta anche la dimensione dell'array.
Ad esempio, If k = 9845648451321, then h(k) = 11(utilizzando qualche funzione hash). Questo aiuta a salvare la memoria sprecata fornendo l'indice di 9845648451321all'array

Risoluzione delle collisioni mediante concatenamento

In questa tecnica, se una funzione hash produce lo stesso indice per più elementi, questi elementi vengono memorizzati nello stesso indice utilizzando un elenco a doppio collegamento.

Se jè lo slot per più elementi, contiene un puntatore all'inizio dell'elenco di elementi. Se non è presente alcun elemento, jcontiene NIL.

Pseudocodice per le operazioni

 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

Implementazione di Python, Java, C e C ++

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(); )

Buone funzioni hash

Una buona funzione hash ha le seguenti caratteristiche.

  1. Non dovrebbe generare chiavi troppo grandi e lo spazio del bucket è piccolo. Lo spazio è sprecato.
  2. Le chiavi generate non dovrebbero essere né molto vicine né troppo distanti.
  3. La collisione deve essere minimizzata il più possibile.

Alcuni dei metodi utilizzati per l'hashing sono:

Metodo di divisione

Se kè una chiave ed mè la dimensione della tabella hash, la funzione hash h()viene calcolata come:

h(k) = k mod m

Ad esempio, se la dimensione di una tabella hash è 10e k = 112quindi h(k) = 112mod 10 = 2. Il valore di mnon deve essere il potere di 2. Questo perché i poteri di 2in formato binario sono 10, 100, 1000,… . Quando lo troviamo k mod m, otterremo sempre i p-bit di ordine inferiore.

 if m = 22, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 01 if m = 23, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 001 if m = 24, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 0001 if m = 2p, then h(k) = p lower bits of m

Multiplication Method

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

  • kA mod 1 gives the fractional part kA,
  • ⌊ ⌋ gives the floor value
  • A is any constant. The value of A lies between 0 and 1. But, an optimal choice will be ≈ (√5-1)/2 suggested by Knuth.

Universal Hashing

In Universal hashing, the hash function is chosen at random independent of keys.

Open Addressing

Multiple values can be stored in a single slot in a normal hash table.

By using open addressing, each slot is either filled with a single key or left NIL. All the elements are stored in the hash table itself.

Unlike chaining, multiple elements cannot be fit into the same slot.

Open addressing is basically a collision resolving technique. Some of the methods used by open addressing are:

Linear Probing

In linear probing, collision is resolved by checking the next slot.
h(k, i) = (h'(k) + i) mod m
where,

  • i = (0, 1,… .)
  • h'(k) is a new hash function

If a collision occurs at h(k, 0), then h(k, 1) is checked. In this way, the value of i is incremented linearly.
The problem with linear probing is that a cluster of adjacent slots is filled. When inserting a new element, the entire cluster must be traversed. This adds to the time required to perform operations on the hash table.

Quadratic Probing

In quadratic probing, the spacing between the slots is increased (greater than one) by using the following relation.
h(k, i) = (h'(k) + c1i + c2i2) mod m
where,

  • c1e sono costanti ausiliarie positive,c2
  • i = (0, 1,… .)

Doppio hashing

Se si verifica una collisione dopo aver applicato una funzione h(k)hash, viene calcolata un'altra funzione hash per trovare lo slot successivo.
h(k, i) = (h1(k) + ih2(k)) mod m

Applicazioni tabella hash

Le tabelle hash vengono implementate dove

  • è richiesto un tempo di ricerca e inserimento costante
  • applicazioni crittografiche
  • i dati di indicizzazione sono obbligatori

Articoli interessanti...