Tableau de hachage mappé trie

Un trie mappé par tableau de hachage ( HAMT ) est une implémentation d'un tableau associatif qui combine les caractéristiques d'une table de hachage et d'un trie mappé par tableau . Il s'agit d'une version raffinée de la notion plus générale d' arbre de hachage .

Un HAMT est un trie mappé en tableau où les clés sont d'abord hachées pour garantir une distribution uniforme des clés et une longueur de clé constante.

Dans une implémentation typique du trie mappé en tableau de HAMT, chaque nœud contient une table avec un nombre fixe N d'emplacements, chaque emplacement contenant soit un pointeur nul, soit un pointeur vers un autre nœud. N est généralement égal à 32. Comme l'allocation d'espace pour N pointeurs pour chaque nœud serait coûteuse, chaque nœud contient à la place une bitmap de N bits de long, chaque bit indiquant la présence d'un pointeur non nul. Ceci est suivi d'un tableau de pointeurs de longueur égale au nombre de uns dans la bitmap (son poids de Hamming ).

Le trie mappé en tableau de hachage atteint une vitesse proche de celle d'une table de hachage tout en utilisant la mémoire de manière beaucoup plus économique. De plus, une table de hachage peut devoir être périodiquement redimensionnée, une opération coûteuse, alors que les HAMT se développent de manière dynamique. En général, les performances des HAMT sont améliorées par une table racine plus grande avec un multiple de N emplacements ; certaines variantes de HAMT permettent à la racine de croître paresseusement avec un impact négligeable sur les performances.

L'implémentation d'un HAMT implique l'utilisation de la fonction de comptage de population , qui compte le nombre d'unités dans la représentation binaire d'un nombre. Cette opération est disponible dans de nombreuses architectures de jeux d'instructions , mais elle n'est disponible que dans certains langages de haut niveau . Bien que le comptage de population puisse être implémenté dans un logiciel en temps O(1) à l'aide d'une série d'instructions de décalage et d'ajout , cela peut ralentir l'opération d'un ordre de grandeur.

Les langages de programmation Clojure , Scala et Frege utilisent une variante persistante des tentatives mappées par tableau de hachage pour leur type de carte de hachage natif. La bibliothèque Haskell "unordered-containers" utilise la même chose pour implémenter des structures de données de carte et d'ensemble persistantes. Une autre bibliothèque Haskell "stm-containers" adapte l'algorithme pour une utilisation dans le contexte de la mémoire transactionnelle logicielle . Une bibliothèque Javascript HAMT basée sur l'implémentation Clojure est également disponible. L' implémentation Rubinius de Ruby inclut un HAMT, principalement écrit en Ruby mais avec 3 primitives. Les grandes cartes en Erlang utilisent une représentation HAMT persistante en interne depuis la version 18.0. Le langage de programmation Pony utilise un HAMT pour la carte de hachage dans son package de collections persistantes. Les caisses im et im-rc, qui fournissent des types de collection persistants pour le langage de programmation Rust, utilisent un HAMT pour leurs tables de hachage et leurs ensembles de hachage persistants.

La version concurrente sans verrou du hachage trie appelée Ctrie est une implémentation thread-safe mutable qui garantit la progression. La structure de données s'est avérée correcte - il a été démontré que les opérations Ctrie ont les propriétés d'atomicité , de linéarisabilité et d'absence de verrou .