Les HashMap liées

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.

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é.

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 :

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
 */
var HashMap = function() {
 this._size = 0;
 this._map = {};
};

HashMap.prototype = {

 /**
  * Encode la paire clé/valeur dans la table,   
  * en écrasant les entrées existantes.
  */
 put: function(key, value) {
   if (!this.containsKey(key)) {
     this._size++;
   }
   this._map[key] = value;
 },
 
 /**
  * Supprime l'entrée associée à la clé
  * et retourne la valeur supprimée.
  */
 remove: function(key) {
   if (this.containsKey(key)) {
     this._size--;
     var value = this._map[key];
     delete this._map[key];
     return value;
   } else {
     return null;
   }
 },
 
 /**
  * Vérifie que la table contient la clé.
  */
 containsKey: function(key) {
   return this._map.hasOwnProperty(key);
 },
 
 /**
  * Vérifie que la table contient la valeur.
  * Notez que cette valeur peut ne pas être unique.
  */
 containsValue: function(value) {
   for (var key in this._map) {
     if (this._map.hasOwnProperty(key)) {
       if (this._map[key] === value) {
         return true;
       }
     }
   }

   return false;
 },
 
 /**
  * Retourne la valeur associée à la clé.
  */
 get: function(key) {
   return this.containsKey(key) ? this._map[key] : null;
 },
 
 /**
  * Vide toutes les entrées de la table.
  */
 clear: function() {
   this._size = 0;
   this._map = {};
 },
 
 /**
  * Retourne un tableau de toutes les clés dans la table.
  */
 keys: function() {
   var keys = [];
   for (var key in this._map) {
     if (this._map.hasOwnProperty(key)) {
       keys.push(key);
     }
   }
   return keys;
 },
 
 /**
  * Retourne un tableau de toutes les valeurs dans la table.
  */
 values: function() {
   var values = [];
   for (var key in this._map) {
     if (this._map.hasOwnProperty(key)) {
       values.push(this._map[key]);
     }
   }
   return values;
 },
 
 /**
  * Retourne la taille de la table,
  * qui correspond au nombre de clés.
  */
 size: function() {
   return this._size;
 }
};

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

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.

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.

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).

/**
 * Constructeur qui initialise la HashMap parent
 * et la liste doublement liée.
 */
var LinkedHashMap = function() {
 // invoque le super constructeur
 HashMap.apply(this, arguments);

 // Classe d'entrée "inner".
 this._Entry = function(value) {
   this.prev = null;
   this.head = null;
   this.value = value;
 };

 // Variable d'instance de la liste doublement liée.
 this._head = this._tail = null;
};

// Étendre la HashMap et réécrire les fonctions nécessaires.
var temp = function() {};
temp.prototype = HashMap.prototype;
LinkedHashMap.prototype = new temp();

/**
 * Insère la paire clé/valeur dans la table
 * et mémorise l'enregistrement s'il n'existe pas encore.
 * 
 * @override HashMap.put()
 */
LinkedHashMap.prototype.put = function(key, value) {
 var entry = new this._Entry(key);

 if (!this.containsKey(key)) {
   if (this.size() === 0) {
     this._head = entry;
     this._tail = entry;
   } else {
     this._tail.next = entry;
     entry.prev = this._tail;
     this._tail = entry;
   }
 }

 HashMap.prototype.put.apply(this, arguments);
};

/**
 * Supprime la paire clé/valeur de la table
 * et la clé de l'ordre d'insertion.
 * 
 * @override Hashmap.remove()
 */
LinkedHashMap.prototype.remove = function(key) {
 if (this.containsKey(key)) {
   // iterate over list keys and remove the entry
   for (var cur = this._head; cur != null; cur = cur.next) {
     if (key === cur.value) {
       if (cur === this._head) {
         this._head = cur.next;
         this._head.prev = null;
       } else if (cur === this._tail) {
         this._tail = cur.prev;
         this._tail.next = null;
       } else {
         cur.prev.next = cur.next;
         cur.next.prev = cur.prev;
       }

       break;
     }
   }
 }

 return HashMap.prototype.remove.apply(this, arguments);
};

/**
 * Vide la table et l'ordre d'insertion.
 *
 * @override HashMap.clear()
 */
LinkedHashMap.prototype.clear = function() {
 HashMap.prototype.clear.apply(this, arguments);
 this._head = this._tail = null;
};

/**
 * Retourne les clés de la table dans l'ordre d'insertion.
 *
 * @override HashMap.keys()
 */
LinkedHashMap.prototype.keys = function() {
 var keys = [];
 for (var cur = this._head; cur != null; cur = cur.next) {
   keys.push(cur.value);
 }
 return keys;
};

/**
 * Retourne les valeurs de la table dans l'ordre d'insertion.
 * 
 * @override HashMap.values()
 */
LinkedHashMap.prototype.values = function() {
 var values = [];
 for (var cur = this._head; cur != null; cur = cur.next) {
   values.push(this.get(cur.value));
 }
 return values;
};

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.

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é.

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.

Cet article a été publié avec l'aimable autorisation de Justin Naifeh pour l'article original Linking the Hash Map publié sur le site DailyJS.
Je remercie également Torgar pour sa relecture attentive et assidue.