Qu'est-ce qu'une table de hachage ?

Pour les simulations de tissu, nous devrons utiliser une table de hachage spatiale afin d'implémenter les collisions. Avant de continuer, j'ai pensé qu'il serait intéressant de vraiment plonger dans les tables de hachage pour mieux comprendre une telle structure.

Keywords: javascript, tutoriel, table de hachage spatiale, carte de hachage, structures de données, leetcode

By Carmen Cincotti

September 26, 2022

Qu’est-ce qu’une table de hachage ?
Comment créer une table de hachage
- JavaScript
- Python
- C++
- Go
La fonction de hachage
Des ressources (en français et anglais)

Qu’est-ce qu’une table de hachage ?

Une table de hachage (table de hachage) est une structure de données qui associe des clés à des valeurs.

A map of key to value

C’est une collection non ordonnée, car on utilise une fonction de hachage pour distribuer “uniformément”** les éléments dans des seaux (buckets) dans une structure de données sous-jacente (par exemple un tableau). ** J’utilise des guillemets, car ce n’est pas toujours uniforme, comme nous le verrons.

A hash table example

Cette distribution uniforme est importante parce que le but est de réduire le temps de recherche à un temps constant $O(1)$ .

Un exemple

Pour voir l’utilité d’une telle structure, prenons cet exemple. J’ai un tableau comme celui-ci :

Array with elements 1, 3, 2, 5, 4

Si je voulais trouver s’il y a un $4$ dans ce tableau, je dois le traverser entièrement.

Traversing an array

On dirait que la complexité temporelle pour rechercher dans une telle structure est donc $O(n)$ en moyenne, car nous devrons peut-être traverser tout le tableau pour finalement trouver un élément.

Cependant, avec une table de hachage qui est bien configurée (avec plus de seaux que d’éléments), je pourrais accéder à un tel élément avec une complexité temporelle constante $O(1)$ en moyenne.

Accessing an element with a hash table

Sur l’image ci-dessus, on passe une clé arbitraryKey à une fonction de hachage. La fonction de hachage nous renvoie l’indice du tableau pour trouver $4$ .

Les chances d’accéder à un seau avec un seul élément sont élevées. On peut dire qu’en moyenne, la complexité temporelle pour rechercher un élément dans une table de hachage est de $O(1)$ .

Collisions de hachage

Cependant, il est possible que plusieurs clés soient hachées dans le même seau.

Hash collisions example

Ce phénomène est causé par des collisions de hachage que nous verrons ensemble plus tard.

Cela dit, on peut dire qu’en moyenne, la complexité temporelle pour rechercher un élément est de $O(1)$

La complexité temporelle

Pour résumer, une table de hachage nous donne une complexité temporelle plus efficiente par rapport à un tableau ou à une liste chaînée quand nous voudrions rechercher, insérer ou supprimer un élément (en moyenne).

Structure	Access	Search	Insertion	Deletion
Array	$O(1)$	$O(n)$	$O(n)$	$O(n)$
Linked List	$O(n)$	$O(n)$	$O(1)$	$O(1)$
Hash Table	$O(1)$	$O(1)$	$O(1)$	$O(1)$

Et dans le scénario du pire des cas, nous verrions ces complexités temporelles :

Structure	Access	Search	Insertion	Deletion
Array	$O(1)$	$O(n)$	$O(n)$	$O(n)$
Linked List	$O(n)$	$O(n)$	$O(1)$	$O(1)$
Hash Table	$O(n)$	$O(n)$	$O(n)$	$O(n)$

Pourquoi y a-t-il un cas pire ? C’est dû aux collisions de hachage. Avant de voir ce phénomène, il faut d’abord comprendre comment fonctionne une fonction de hachage.

Comment créer une table de hachage

Pour ceux qui ne sont intéressés que par l’implémentation de ces structures dans le code, je vous laisse quelques exemples :

JavaScript

Il existe deux façons de ce faire en JavaScript. Avec un type Object et un type Map.

const obj = {}
obj.name = "Carmen"
obj["name"] // Carmen


const map = new Map()
map.set("name", "Carmen")
map.get("name") // Carmen

Quelle est la différence ? Toutes les propriétés du type Object sont modifiables, même celles héritées par la classe de base Object - ce qui rend cette structure moins sécurisée.

Par exemple, je pourrais faire la suivante :

const obj = {};
obj.name = "Carmen"
obj.hasOwnProperty = "Whoops"

obj.hasOwnProperty("name")
// ERROR: obj.hasOwnProperty is not a function

Il n’est pas possible de faire cela avec Map.

Python

# Declare a dictionary 
dictionary = {'Name': 'Carmen'}
dictionary["Name"] # Carmen

C++

std::unordered_map<std::string, std::string> u = {
    {"Name","Carmen"},
};

u["Name"] // Carmen

Go

var m map[string]string
m = make(map[string]string)

m["name"] = "Carmen"
m["name"] // Carmen

La fonction de hachage

La fonction de hachage est une fonction qui prend en tant qu’entrée une clé et qui nous renvoie un indice pour accéder à une valeur dans une structure dans laquelle nous pouvons indexer (un tableau).

The hash function

Une entrée de la fonction de hachage peut être n’importe quoi. C’est le travail du développeur de créer une fonction de hachage capable de hacher le type d’entrée.

Imaginons que je vends des fruits. J’ai en stock les suivants :

Fruit	Stock
Pomme	2
Pamplemousse	4

Je voudrais accéder au stock de chaque fruit en temps constant $O(1)$ . C’est un travail pour une table de hachage !

Pour ce faire, je crée une fonction de hachage, hash comme suit qui prend un string key en tant qu’entrée :

    function hash(key: string): number {
        var h = 0, l = key.length, i = 0;
        if ( l > 0 )
            while (i < l)
                h = (h << 5) - h + key.charCodeAt(i++) | 0;
        return h; // a number
    }

Si j’utilise cette fonction avec une entrée comme "pomme", je vais obtenir une sortie comme 106849382 - qui est l’indice que l’on utilise pour accéder à la valeur dans le tableau. De plus, si j’utilise "pamplemousse" comme entrée - j’obtiendrai 465401887.

Avec ces indices - je pourrais placer les valeurs dans un tableau à ces indices comme suit :

Using a hash table to insert an item

OK, mais il y a un petit problème. Avec un indice comme 106849382, on dirait que nous devons avoir un tableau avec une taille d’au moins 106849382. C’est trop gros pour stocker deux valeurs, même du gaspillage !

Nous devons également résoudre les sorties négatives de la fonction de hachage, car les indices négatifs n’existent pas.

Pour avancer, imaginons à nouveau que nous voudrions utiliser un seul tableau d’éléments de taille $5$ pour stocker nos données.

An array of size 5

Ensuite, je crée une fonction goodHash qui appelle la fonction badHash, mais je pousse la sortie à être positive et à être entre $[0, 5)$ .

    function badHash(key: string): number {
        var h = 0, l = key.length, i = 0;
        if ( l > 0 )
            while (i < l)
                h = (h << 5) - h + key.charCodeAt(i++) | 0;
        return h; // a number
    }

    function goodHash(key: string): number {
        var bad = badHash(key)
        var arraySize = 5
        return Math.abs(bad) % arraySize
    }

Si j’utilise "pomme" comme entrée de la fonction goodHash, je vais recevoir $2$ comme sortie. Je place donc la valeur de pomme dans le seau qui correspond à l’indice $2$ :

Placing the string pomme into hash map

Après je fais pareil du mot pamplemousse. La fonction goodHash nous renvoie le même indice, $2$ . Hein ?:

Placing the string pamplemousse into a hash map

Il y a un problème ! Si je continue à placer la valeur de pamplemousse dans le tableau à l’indice $2$ , j’écraserai la valeur de pomme !

On vient de voir ce qu’on appelle une collision de hachage.

Collision de hachage - lorsqu’une fonction de hachage renvoie le même indice pour plusieurs clés. Il y aura une “collision” entre ces deux clés dans la structure de stockage sous-jacente.

Ce phénomène mérite son propre article. À plus !

Carmen's Graphics Blog