Tag Archives: datastructures

Table de hachage

La table de hachage vous permet d’implémenter une structure de données de tableau associatif (dictionnaire) avec des performances moyennes O(1) pour les opérations d’insertion, de suppression et de recherche.

Vous trouverez ci-dessous un exemple de l’implémentation la plus simple d’une carte de hachage dans nodeJS :

Comment ça marche ? Surveillez vos mains :

  • À l’intérieur de la carte de hachage se trouve un tableau
  • À l’intérieur de l’élément du tableau se trouve un pointeur vers le premier nœud de la liste chaînée
  • La mémoire est allouée à un tableau de pointeurs (par exemple, 65 535 éléments)
  • Ils implémentent une fonction de hachage, la clé du dictionnaire est l’entrée, et en sortie elle peut tout faire, mais à la fin elle renvoie l’index de l’élément du tableau

Comment fonctionne l’enregistrement :

  • A l’entrée, il y a une paire de clés – valeur
  • La fonction de hachage renvoie l’index par clé
  • Obtenir un nœud de liste chaînée à partir d’un tableau par index
  • Vérifiez si cela correspond à la clé
  • Si cela correspond, remplacez la valeur
  • S’il ne correspond pas, passez au nœud suivant jusqu’à ce que nous trouvions ou trouvions un nœud avec la clé requise.
  • Si le nœud n’est toujours pas trouvé, créez-le à la fin de la liste chaînée

Fonctionnement de la recherche par clé :

  • A l’entrée, il y a une paire de clés – valeur
  • La fonction de hachage renvoie l’index par clé
  • Obtenir un nœud de liste chaînée à partir d’un tableau par index
  • Vérifiez si cela correspond à la clé
  • Si cela correspond, renvoyez la valeur
  • S’il ne correspond pas, passez au nœud suivant jusqu’à ce que nous trouvions ou trouvions un nœud avec la clé requise.

Pourquoi avons-nous besoin d’une liste chaînée dans un tableau ? En raison de collisions possibles lors du calcul de la fonction de hachage. Dans ce cas, plusieurs paires clé-valeur différentes seront situées au même index dans le tableau, auquel cas la liste chaînée est parcourue pour trouver la clé requise.

Sources

https://ru.wikipedia.org/wiki/Hash table
https://www.youtube.com/watch?v=wg8hZxMRwcw

Code source

https://gitlab.com/demensdeum/datastructures

Machine à empiler et RPN

Supposons que nous devions implémenter un simple interpréteur de bytecode, quelle approche pour implémenter cette tâche devrions-nous choisir ?

Structure des données La pile offre la possibilité d’implémenter une machine de bytecode simple. Les fonctionnalités et les implémentations des machines à pile sont décrites dans de nombreux articles sur l’Internet occidental et national ; je mentionnerai simplement que la machine virtuelle Java est un exemple de machine à pile.

Le principe de fonctionnement de la machine est simple, un programme contenant des données et des codes d’opération (opcodes) est fourni à l’entrée, et les opérations nécessaires sont mises en œuvre à l’aide de manipulations avec la pile. Regardons un exemple de programme de bytecode de ma machine à pile :

пMVkcatS olleHП

En sortie, nous recevrons la chaîne « Hello StackVM ». La machine à pile lit le programme de gauche à droite, chargeant les données caractère par caractère sur la pile lorsqu’un opcode apparaît dans le symbole – implémente la commande en utilisant la pile.

Exemple d’implémentation d’une stack machine dans nodejs :

Notation polonaise inversée (RPN)

Les machines Stack sont également faciles à utiliser pour mettre en œuvre des calculatrices, pour cela elles utilisent la notation polonaise inversée (notation suffixe).
Exemple de notation infixe régulière :
2*2+3*4

Convertit en RPN :
22*34*+

Pour compter l’enregistrement postfix, nous utilisons une machine à pile :
2– en haut de la pile (pile : 2)
2– en haut de la pile (pile : 2,2)
*– obtenir le haut de la pile deux fois, multiplier le résultat, l’envoyer en haut de la pile (pile : 4)
3– en haut de la pile (pile : 4, 3)
4– en haut de la pile (pile : 4, 3, 4)
*– obtenir le haut de la pile deux fois, multiplier le résultat, l’envoyer en haut de la pile (pile : 4, 12)
+– récupérez deux fois le haut de la pile, ajoutez le résultat, envoyez-le en haut de la pile (pile : 16)

Comme vous pouvez le voir – le résultat des opérations 16 reste sur la pile, il peut être imprimé en implémentant des opcodes d’impression de pile, par exemple :
p22*34*+P

P – Opcode de démarrage de l’impression de la pile, p – opcode pour terminer l’impression de la pile et envoyer la ligne finale pour le rendu.
Pour convertir les opérations arithmétiques d’infixe en suffixe, l’algorithme d’Edsger Dijkstra appelé « Sorting Yard » est utilisé. Un exemple d’implémentation peut être vu ci-dessus, ou dans le référentiel du projet de pile de machines nodejs ci-dessous.

Sources

https:/ /tech.badoo.com/ru/article/579/interpretatory-bajt-kodov-svoimi-rukami/
https://ru.wikipedia.org/wiki/Обратная_польская_запись

Code source

https://gitlab.com/demensdeum/stackvm/< /p>