Comment implémenter une table de hachage simple en JavaScript

Est {}-ce que c'est beau ?

Il vous permet de stocker les valeurs par clé et de les récupérer de manière très économique ( O(1)plus d'informations à ce sujet plus tard).

Dans cet article, je veux implémenter une table de hachage très basique et jeter un coup d'œil à son fonctionnement interne pour expliquer l'une des idées les plus ingénieuses de l'informatique.

Le problème

Imaginez que vous construisez un nouveau langage de programmation: vous commencez par avoir des types assez simples (chaînes, entiers, flottants,…) et ensuite vous procédez à l'implémentation de structures de données très basiques. D'abord vous venez avec le tableau ( []), puis vient la table de hachage (autrement connue sous le nom de dictionnaire, tableau associatif, hashmap, map, et… la liste continue).

Vous êtes-vous déjà demandé comment ils fonctionnent? Comment ils sont si rapides?

Eh bien, disons que JavaScript n'avait pas {}ou new Map(), et implémentons le nôtre DumbMap!

Une note sur la complexité

Avant de commencer, nous devons comprendre comment fonctionne la complexité d'une fonction: Wikipedia a un bon rappel sur la complexité de calcul, mais j'ajouterai une brève explication pour les paresseux.

La complexité mesure le nombre d'étapes requises par notre fonction - moins il y a d'étapes, plus l'exécution est rapide (également appelée «temps d'exécution»).

Jetons un coup d'œil à l'extrait de code suivant:

function fn(n, m) { return n * m}

La complexité de calcul (désormais simplement «complexité») de fnest O(1), ce qui signifie qu'elle est constante (vous pouvez lire O(1)comme « le coût est un »): quels que soient les arguments que vous passez, la plate-forme qui exécute ce code n'a qu'une seule opération (multiplier nen m). Encore une fois, puisqu'il s'agit d'une opération, le coût est appelé O(1).

La complexité est mesurée en supposant que les arguments de votre fonction peuvent avoir de très grandes valeurs. Regardons cet exemple:

function fn(n, m) { let s = 0
 for (i = 0; i < 3; i++) { s += n * m }
 return s}

Vous penseriez que sa complexité est O(3), non?

Encore une fois, comme la complexité est mesurée dans le contexte de très gros arguments, nous avons tendance à «supprimer» les constantes et à considérer O(3)la même chose que O(1). Donc, même dans ce cas, nous dirions que la complexité de fnest O(1). Quelle que soit la valeur de net m, vous finissez toujours par effectuer trois opérations - ce qui, encore une fois, est un coût constant (donc O(1)).

Maintenant, cet exemple est un peu différent:

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(m) }
 return s}

Comme vous le voyez, nous bouclons autant de fois que la valeur de n, qui pourrait se chiffrer en millions. Dans ce cas, nous définissons la complexité de cette fonction comme O(n), car vous devrez effectuer autant d'opérations que la valeur de l'un de vos arguments.

D'autres exemples?

function fn(n, m) { let s = []
 for (i = 0; i < 2 * n; i++) { s.push(m) }
 return s}

Cet exemple boucle les 2 * ntemps, ce qui signifie que la complexité devrait être O(2n). Puisque nous avons mentionné que les constantes sont «ignorées» lors du calcul de la complexité d'une fonction, cet exemple est également classé comme O(n).

Un de plus?

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { for (i = 0; i < n; i++) { s.push(m) } }
 return s}

Ici, nous bouclons net bouclons à nouveau à l'intérieur de la boucle principale, ce qui signifie que la complexité est «au carré» ( n * n): si nest 2, nous exécuterons s.push(m)4 fois, si 3 nous l'exécuterons 9 fois, et ainsi de suite.

Dans ce cas, la complexité de la fonction est appelée O(n²).

Un dernier exemple?

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(n) }
 for (i = 0; i < m; i++) { s.push(m) }
 return s}

Dans ce cas, nous n'avons pas de boucles imbriquées, mais nous bouclons deux fois sur deux arguments différents: la complexité est définie comme O(n+m). Clair comme de l'eau de roche.

Maintenant que vous venez de recevoir une brève introduction (ou un rappel) sur la complexité, il est très facile de comprendre qu'une fonction complexe O(1)fonctionnera bien mieux qu'une fonction avec O(n).

Les tables de hachage ont une O(1)complexité: en termes simples, elles sont ultra-rapides . Allons-nous en.

(Je suis un peu allongé sur des tables de hachage toujours O(1)complexes, mais continuez à lire;))

Construisons une table de hachage (stupide)

Notre table de hachage a 2 méthodes simples - set(x, y)et get(x). Commençons à écrire du code:

Et implémentons un moyen très simple et inefficace de stocker ces paires clé-valeur et de les récupérer plus tard. Nous commençons par les stocker dans un tableau interne (rappelez-vous, nous ne pouvons pas les utiliser {}puisque nous les implémentons {}- époustouflants!):

Ensuite, il s'agit simplement d'obtenir le bon élément de la liste:

Notre exemple complet:

Notre DumbMap est incroyable! Cela fonctionne dès la sortie de la boîte, mais comment fonctionnera-t-il lorsque nous ajoutons un grand nombre de paires clé-valeur?

Essayons une simple référence. Nous allons d'abord essayer de trouver un élément non existant dans une table de hachage avec très peu d'éléments, puis essayer la même chose dans une avec une grande quantité d'éléments:

Les resultats? Pas si encourageant:

with very few records in the map: 0.118mswith lots of records in the map: 14.412ms

Dans notre implémentation, nous devons parcourir tous les éléments à l'intérieur this.listafin d'en trouver un avec la clé correspondante. Le coût est O(n), et c'est assez terrible.

Fais le plus rapidement)

Nous devons trouver un moyen d'éviter de parcourir notre liste en boucle: il est temps de remettre le hachage dans la table de hachage .

Vous êtes-vous déjà demandé pourquoi cette structure de données s'appelle une table de hachage ? C'est parce qu'une fonction de hachage est utilisée sur les clés que vous définissez et obtenez. Nous utiliserons cette fonction pour transformer notre clé en un entier iet stocker notre valeur à l'index ide notre liste interne. Puisque l'accès à un élément, par son index, à partir d'une liste a un coût constant ( O(1)), alors la table de hachage aura également un coût de O(1).

Essayons ceci:

Ici, nous utilisons le module string-hash, qui convertit simplement une chaîne en un hachage numérique. Nous l'utilisons pour stocker et récupérer des éléments à l'index hash(key)de notre liste. Les resultats?

with lots of records in the map: 0.013ms

W - O - W. C'est ce dont je parle!

Nous n'avons pas besoin de parcourir tous les éléments de la liste et la récupération des éléments DumbMapest très rapide!

Permettez-moi de dire ceci aussi simplement que possible: le hachage est ce qui rend les tables de hachage extrêmement efficaces . Pas de magie. Rien de plus. Nada. Juste une idée simple, intelligente et ingénieuse.

Le coût de sélection de la bonne fonction de hachage

Bien sûr, choisir une fonction de hachage rapide est très important. Si notre hash(key)fonctionne dans quelques secondes, notre fonction sera assez lente quelle que soit sa complexité.

Dans le même temps, il est très important de s'assurer que notre fonction de hachage ne produit pas beaucoup de collisions , car cela nuirait à la complexité de notre table de hachage.

Confus? Regardons de plus près les collisions.

Collisions

Vous pourriez penser « Ah, une bonne fonction de hachage ne génère jamais de collisions! »: Eh bien, revenez dans le monde réel et repensez-y. Google a pu produire des collisions pour l'algorithme de hachage SHA-1, et ce n'est qu'une question de temps, ou de puissance de calcul, avant qu'une fonction de hachage se fissure et renvoie le même hachage pour 2 entrées différentes. Supposez toujours que votre fonction de hachage génère des collisions et implémentez la bonne défense contre de tels cas.

Par exemple, essayons d'utiliser une hash()fonction qui génère beaucoup de collisions:

Cette fonction utilise un tableau de 10 éléments pour stocker les valeurs, ce qui signifie que les éléments sont susceptibles d'être remplacés - un vilain bogue dans notre DumbMap:

Afin de résoudre le problème, nous pouvons simplement stocker plusieurs paires clé-valeur dans le même index. Alors modifions notre table de hachage:

Comme vous le remarquerez peut-être, nous revenons ici à notre implémentation d'origine: stocker une liste de paires clé-valeur et parcourir chacune d'elles. Cela va être assez lent quand il y a beaucoup de collisions pour un index particulier de la liste.

Comparons cela en utilisant notre propre hash()fonction qui génère des index de 1 à 10:

with lots of records in the map: 11.919ms

et en utilisant la fonction de hachage de string-hash, qui génère des index aléatoires:

with lots of records in the map: 0.014ms

Whoa! Il y a le coût de choisir la bonne fonction de hachage - assez rapidement pour ne pas ralentir notre exécution par elle-même, et assez bien pour ne pas produire beaucoup de collisions.

Généralement O (1)

Tu te souviens de mes paroles?

Les hashtables ont une O(1)complexité

Eh bien, j'ai menti: la complexité d'une table de hachage dépend de la fonction de hachage que vous choisissez. Plus vous générez de collisions, plus la complexité tend vers O(n).

Une fonction de hachage telle que:

function hash(key) { return 0}

signifierait que notre table de hachage a une complexité de O(n).

C'est pourquoi, en général, la complexité des calculs comporte trois mesures: les meilleurs, les moyens et les pires scénarios. Les tables de hachage ont une O(1)complexité dans les meilleurs scénarios et les scénarios moyens, mais tombent O(n)dans leur pire scénario.

Rappelez-vous: une bonne fonction de hachage est la clé d'une table de hachage efficace - ni plus, ni moins.

En savoir plus sur les collisions…

La technique que nous avons utilisée pour corriger DumbMapen cas de collisions s'appelle le chaînage séparé: nous stockons toutes les paires de clés qui génèrent des collisions dans une liste et les parcourons en boucle.

L'adressage ouvert est une autre technique populaire:

  • à chaque index de notre liste, nous stockons une et une seule paire clé-valeur
  • lorsque vous essayez de stocker une paire à l'index x, s'il existe déjà une paire clé-valeur, essayez de stocker notre nouvelle paire àx + 1
  • si elle x + 1est prise, essayez x + 2et ainsi de suite…
  • lors de la récupération d'un élément, hachez la clé et voyez si l'élément à cette position ( x) correspond à notre clé
  • sinon, essayez d'accéder à l'élément à la position x + 1
  • rincez et répétez jusqu'à ce que vous arriviez à la fin de la liste, ou lorsque vous trouvez un index vide - cela signifie que notre élément n'est pas dans la table de hachage

Intelligent, simple, élégant et généralement très efficace!

FAQ (ou TL; DR)

Une table de hachage hache-t-elle les valeurs que nous stockons?

Non, les clés sont hachées afin de pouvoir être transformées en un entier i, et les clés et les valeurs sont stockées à la position idans une liste.

Les fonctions de hachage utilisées par les tables de hachage génèrent-elles des collisions?

Absolument - les tables de hachage sont donc implémentées avec des stratégies de défense pour éviter les bugs désagréables.

Les tables de hachage utilisent-elles une liste ou une liste chaînée en interne?

Cela dépend, les deux peuvent fonctionner. Dans nos exemples, nous utilisons le tableau JavaScript ( []) qui peut être redimensionné dynamiquement:

> a = []
> a[3] = 1
> a[ , 1 ]

Pourquoi avez-vous choisi JavaScript pour les exemples? Les tableaux JS SONT des tables de hachage!

Par exemple:

> a = [][]
> a["some"] = "thing"'thing'
> a[ some: 'thing' ]
> typeof a'object'

Je sais, putain de JavaScript.

JavaScript est «universel» et probablement le langage le plus simple à comprendre lorsque l'on regarde un exemple de code. JS n'est peut-être pas le meilleur langage, mais j'espère que ces exemples sont suffisamment clairs.

Votre exemple est-il vraiment une bonne implémentation d'une table de hachage? Est-ce vraiment si simple?

Non pas du tout.

Jetez un œil à «implémenter une table de hachage en JavaScript» par Matt Zeunert, car cela vous donnera un peu plus de contexte. Il y a beaucoup plus à apprendre, alors je vous suggère également de vérifier:

  • Cours de Paul Kube sur les tables de hachage
  • Implémentation de notre propre table de hachage avec chaînage séparé en Java
  • Algorithmes, 4e édition - Tables de hachage
  • Concevoir une table de hachage rapide

À la fin…

Les tables de hachage sont une idée très intelligente que nous utilisons régulièrement: que vous créiez un dictionnaire en Python, un tableau associatif en PHP ou une carte en JavaScript. Ils partagent tous les mêmes concepts et fonctionnent à merveille pour nous permettre de stocker et de récupérer l'élément par un identifiant, à un coût constant (le plus probable).

J'espère que cet article vous a plu et n'hésitez pas à partager vos commentaires avec moi.

Un merci spécial à Joe qui m'a aidé en examinant cet article.

Adios!