Table de hachage

Dans ce didacticiel, vous apprendrez ce qu'est la table de hachage. Vous trouverez également des exemples pratiques d'opérations de table de hachage en C, C ++, Java et Python.

La table de hachage est une structure de données qui représente les données sous la forme de paires clé-valeur . Chaque clé est mappée à une valeur dans la table de hachage. Les clés sont utilisées pour indexer les valeurs / données. Une approche similaire est appliquée par un tableau associatif.

Les données sont représentées dans une paire clé / valeur à l'aide de clés, comme illustré dans la figure ci-dessous. Chaque donnée est associée à une clé. La clé est un entier qui pointe vers les données.

1. Table des adresses directes

La table d'adresses directe est utilisée lorsque la quantité d'espace utilisée par la table n'est pas un problème pour le programme. Ici, nous supposons que

  • les clés sont de petits entiers
  • le nombre de clés n'est pas trop grand, et
  • aucune donnée n'a la même clé

Un pool d'entiers est appelé univers U = (0, 1,… ., n-1).
Chaque emplacement d'une table d'adresses directe T(0… n-1)contient un pointeur vers l'élément qui correspond aux données.
L'index du tableau Test la clé elle-même et le contenu de Test un pointeur vers l'ensemble (key, element). S'il n'y a pas d'élément pour une clé, elle est laissée comme NULL.

Parfois, la clé elle-même est la donnée.

Pseudocode pour les opérations

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

Limitations d'une table d'adresses directes

  • La valeur de la clé doit être petite.
  • Le nombre de clés doit être suffisamment petit pour ne pas dépasser la limite de taille d'un tableau.

2. Table de hachage

Dans une table de hachage, les clés sont traitées pour produire un nouvel index qui correspond à l'élément requis. Ce processus s'appelle le hachage.

Soit h(x)une fonction de hachage et kune clé.
h(k)est calculé et il est utilisé comme index pour l'élément.

Limitations d'une table de hachage

  • Si le même index est produit par la fonction de hachage pour plusieurs clés, un conflit survient. Cette situation est appelée collision.
    Pour éviter cela, une fonction de hachage appropriée est choisie. Mais, il est impossible de produire toutes les clés uniques car |U|>m. Ainsi, une bonne fonction de hachage peut ne pas empêcher complètement les collisions, mais elle peut réduire le nombre de collisions.

Cependant, nous avons d'autres techniques pour résoudre les collisions.

Avantages de la table de hachage par rapport à la table d'adresses directe:

Les principaux problèmes avec la table d'adresses directes sont la taille du tableau et la valeur éventuellement élevée d'une clé. La fonction de hachage réduit la plage d'index et donc la taille du tableau est également réduite.
Par exemple, Si k = 9845648451321, alors h(k) = 11(en utilisant une fonction de hachage). Cela permet d'économiser la mémoire gaspillée tout en fournissant l'index du 9845648451321tableau

Résolution de collision par chaînage

Dans cette technique, si une fonction de hachage produit le même index pour plusieurs éléments, ces éléments sont stockés dans le même index à l'aide d'une liste doublement liée.

Si jest l'emplacement pour plusieurs éléments, il contient un pointeur vers la tête de la liste des éléments. Si aucun élément n'est présent, jcontient NIL.

Pseudocode pour les opérations

 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

Implémentation Python, Java, C et 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(); )

Bonnes fonctions de hachage

Une bonne fonction de hachage a les caractéristiques suivantes.

  1. Il ne doit pas générer de clés trop volumineuses et l'espace de seau est petit. L'espace est gaspillé.
  2. Les clés générées ne doivent être ni très proches ni trop éloignées.
  3. La collision doit être minimisée autant que possible.

Certaines des méthodes utilisées pour le hachage sont:

Méthode de division

Si kest une clé et mcorrespond à la taille de la table de hachage, la fonction de hachage h()est calculée comme suit:

h(k) = k mod m

Par exemple, si la taille d'une table de hachage est 10et k = 112alors h(k) = 112mod 10 = 2. La valeur de mne doit pas être les pouvoirs de 2. C'est parce que les puissances du 2format binaire sont 10, 100, 1000,… . Lorsque nous trouvons k mod m, nous obtiendrons toujours les p-bits d'ordre inférieur.

 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,

  • c1et sont des constantes auxiliaires positives,c2
  • i = (0, 1,… .)

Double hachage

Si une collision se produit après l'application d'une fonction de hachage h(k), une autre fonction de hachage est calculée pour trouver l'emplacement suivant.
h(k, i) = (h1(k) + ih2(k)) mod m

Applications de table de hachage

Les tables de hachage sont implémentées là où

  • une recherche et une insertion à temps constant sont requises
  • applications cryptographiques
  • l'indexation des données est requise

Articles intéressants...