I. HashMap

La table de hachage (HashMapHashMap) est une structure indispensable de données classiques dans la programmation d'applications. C'est tellement omniprésent que pratiquement tous les langages modernes la supportent grâce à leur bibliothèque, ou en intégrant les fonctionnalités dans la syntaxe elle-même. Les tables de hachage sont souvent implémentées sous forme de tableau associatif.

Une HashMap fournit l'accès permanent à une valeur via une clé unique. La méthode la plus commune en JavaScript est d'utiliser un objet littéral comme une HashMap.

 
Sélectionnez
var map = {};

// notation par point
map.foo = "bar";
console.log(map.foo); // "bar"

// notation par crochets
map["foo"] = "bar";
console.log(map["foo"]); // "bar"

// un mélange des deux
map.foo = "bar";
console.log(map["foo"]); // "bar"


Dans cet exemple, la chaîne bar est la valeur assignée à la propriété foo. Notez que le traitement d'un objet littéral comme une HashMap est la même syntaxe que l'accès normal à la propriété et à sa manipulation. Nous pouvons tirer parti du langage lui-même comme d'une structure de données. Parce qu'il n'y a pas de prise en charge du hachage en JavaScript natif, la méthode Object.prototype.toString() est appelée pour créer le nom de la propriété.

 
Sélectionnez
var map = {};
 
map[1] = "one";
console.log(map[1] === "one"); // true
console.log(map["1"] === "one"); // true
console.log(map[(1).toString()] === "one"); // true


Tandis que les objets littéraux suffisent pour les usages basiques d'une HashMap, il y a beaucoup d'opérations qui requièrent du code réutilisable comme lister toutes les valeurs d'une HashMap :

 
Sélectionnez
var map = {};

map["key1"] = "one";
map["key2"] = "two";
map["key3"] = "three";

// récupérer toutes les valeurs
var values = [];
for (var key in map) {
 if (map.hasOwnProperty(key)) {
   values.push(map[key]);
 }
}

// l'ordre des clés n'est pas garanti avec une HashMap basique
// et chaque navigateur a son implémentation
console.log(values.join(',')); // "two,three,one"


Pour nous éviter de réinventer la roue, il est conseillé d'utiliser une classe HashMap qui encapsule le comportement. La mise en œuvre dépasse la portée de cet article, mais il y a beaucoup de bibliothèques open source et d'articles qui méritent d'être lu attentivement pour plus de détails. Pour cet article, nous allons utiliser la classe HashMap rudimentaire suivante :

Simple classe HashMap
CacherSélectionnez


Cette classe HashMap manque de fonctionnalités avancées, mais elle est simple, efficace et indépendante d'une bibliothèque.

II. Ordre d'insertion

Même une HashMap robuste et bien testée a une lacune si elle s'appuie sur un objet littéral : l'ordre retourné des HashMap.keys() ou des HashMap.values() est imprévisible, ce qui signifie que l'ordre d'insertion n'est pas conservé. Le poids que représente la sauvegarde de l'ordre d'insertion explique pourquoi la plupart des HashMap ignorent une telle exigence et ne garantissent pas l'ordre retourné.

Bien que l'ordre d'insertion semble trivial, il y a beaucoup de cas où il est essentiel d'utiliser des HashMap pour un accès permanent, tout en restant également attentif lorsque les paires clé/valeur sont insérées dans la table. Par exemple, une bibliothèque d'interface utilisateur peut permettre à un développeur d'ajouter des objets Widget à un tableau de bord.

Les objets Widget sont ajoutés à un tableau de bord et lorsqu'un tableau de bord est affiché, tous ses enfants de type Widget sont dans un ordre prévisible. Il s'agit d'éviter d'avoir des objets Widget répartis aléatoirement dans la mise en page et qui change à chaque affichage.

 
Sélectionnez
var dashboard = new Dashboard();
dashboard.add(new Calendar("myCalendar"));
dashboard.add(new StockTicker("myStockTicker"));
dashboard.add(new Twitter("myTwitter"));

// modifie le calendrier avant de l'afficher
var calendar = dashboard.getWidget("myCalendar");
calendar.setTimeZone("MST");

// affiche le tableau de bord et ses widgets dans l'ordre : Calendar, StockTicker, Twitter
<code langage="javascript" titre=""><![CDATA[
dashboard.render();


Nous accédons à l'objet Calendar via son id unique (il en va de même pour les autres objets Widget), avec l'instruction Dashboard.getWidget() qui délègue la tâche en interne à une HashMap privée. Cela présente un problème d'implémentation : nous voulons préserver l'ordre d'insertion des objets Widget mais en donnant l'accès permanent au développeur aux enfants de ses objets Widget. Une solution courante consiste à maintenir les deux structures de données dans le tableau de bord en synchronisant une HashMap pour les accès et un Array pour l'ordre.


Le code permettant d'assurer la cohérence et l'intégrité entre les deux structures est non négligeable et non réutilisable, donc ce n'est pas idéal. Une autre solution consiste à abandonner la HashMap et de se fonder uniquement sur un Array, mais cela ralentira l'accès aux objets Widget (O(n)), qui est tout aussi inacceptable.

III. Les HashMap liées

Une HashMap liée est une HashMap spécialisée qui est synchronisée avec une liste doublement chaînée. Nous pouvons fusionner les structures de ces deux données dans une nouvelle classe appelée LinkedHashMap, qui permet un accès permanent, soutenu par une liste doublement liée qui permet de préserver l'ordre d'insertion. Il y a une charge minimale pour synchroniser les deux structures lors de l'exécution des opérations d'écriture dans la HashMap. En étendant la classe HashMap nous pouvons ajouter une liste doublement liée optimisée pour assurer le suivi des clés (si la HashMap ne peut pas être remaniée, envisagez alors de créer votre propre classe s'il existe des exigences spécifiques à l'application et à l'optimisation).

Classe LinkedHashMap
CacherSélectionnez


Cette nouvelle structure de données, un mariage entre une HashMap et une liste doublement liée, est parfaite pour gérer les objets Widgets.

IV. Conclusion

Avec juste un peu de lourdeur pour les opérations d'écriture dans la LinkedHashMap, même les problèmes élémentaires nécessitant un comportement de type HashMap peuvent interroger l'ordre d'insertion en toute simplicité.

 
Sélectionnez
var map = new LinkedHashMap();

map.put("key1", "one");
map.put("key2", "two");
map.put("key3", "three");

// l'ordre retournée est maintenant prévisible
console.log(map.keys().join(',')); // "key1,key2,key3"
console.log(map.values().join(',')); // "one,two,three"


Comme LinkedHashMap implémente la même API que HashMap via un héritage, le code en cours peut passer à une LinkedHashMap au moment de l'exécution sans aucun risque. La beauté de la conception orientée objet, est que le type déclaré (HashMap) d'une variable est sans rapport avec le type d'exécution (LinkedHashMap). La seule difficulté est l'application de l'API dans un langage non typé tel que le JavaScript... mais c'est une autre histoire.

V. Remerciements

Cet article a été publié avec l'aimable autorisation de Justin Naifeh. L'article original peut être lu sur le site DailyJSDailyJS : Linking the Hash MapLinking the Hash Map.
Je remercie également Torgar pour sa relecture attentive et assidue.