La description du problème
JavaScript n'a pas en général une carte de type (parfois appelé tableau associatif ou dictionnaire) qui permet d'accéder à des valeurs arbitraires par clés arbitraires. JavaScript fondamentale de la structure de données est l' objet, un type spécial de carte qui accepte uniquement les chaînes que les clés et spécifiques de la sémantique comme l'héritage par prototype, les getters et les setters et de quelques autres vaudou.
Lors de l'usage des objets, des cartes, vous devez vous rappeler que la clé sera converti en chaîne de valeur par l'intermédiaire d' toString(), ce qui entraîne dans la cartographie des 5 et '5' à la même valeur et tous les objets qui n'écrasent pas l' toString() méthode de la valeur indexée par '[object Object]'. Vous pourriez aussi involontairement accéder à ses propriétés héritées si vous ne cochez pas hasOwnProperty().
JavaScript est intégré dans le tableau de type de ne pas aider un peu: les tableaux JavaScript ne sont pas des tableaux associatifs, mais seulement des objets avec un peu plus de propriétés spéciales. Si vous voulez savoir pourquoi ils ne peuvent pas être utilisées comme des cartes, regardez ici.
Eugène de Solution
Eugène Lazutkin déjà décrit l'idée de base de l'aide personnalisée fonction de hachage pour générer des chaînes uniques qui peuvent être utilisés pour rechercher les valeurs associées à des propriétés d'un objet dictionary. Ce sera probablement la solution la plus rapide, car les objets sont mis en œuvre en interne comme les tables de hachage.
-
Remarque: les tables de Hachage (parfois appelé hash cartes) sont un particulier de la mise en œuvre de la carte conceptuelle à l'aide d'un support de tableau et de la recherche via numérique des valeurs de hachage. L'environnement d'exécution peut utiliser d'autres structures (comme les arbres de recherche ou skip lists) pour mettre en œuvre des objets en JavaScript, mais comme les objets sont les données fondamentales de la structure, ils doivent être suffisamment optimisé.
Afin d'obtenir une unique valeur de hachage pour les objets arbitraires, une possibilité consiste à utiliser un compteur global et le cache de la valeur de hachage de l'objet lui-même (par exemple, dans une propriété nommée __hash).
Une fonction de hachage qui ne c'est et travaille pour des valeurs primitives et des objets est:
function hash(value) {
return (typeof value) + ' ' + (value instanceof Object ?
(value.__hash || (value.__hash = ++arguments.callee.current)) :
value.toString());
}
hash.current = 0;
Cette fonction peut être utilisée comme décrit par Eugène. Pour des raisons de commodité, nous allons poursuivre l'envelopper dans un Map classe.
Mon Map mise en œuvre
La suite de la mise en œuvre sera en outre stocker la clé-valeur-paires dans une liste doublement chaînée, afin de permettre rapidement d'une itération sur les touches du clavier et valeurs. Afin de fournir à votre propre fonction de hachage, vous pouvez remplacer l'instance de l' hash() méthode après la création.
// linking the key-value-pairs is optional
// if no argument is provided, linkItems === undefined, i.e. !== false
// --> linking will be enabled
function Map(linkItems) {
this.current = undefined;
this.size = 0;
if(linkItems === false)
this.disableLinking();
}
Map.noop = function() {
return this;
};
Map.illegal = function() {
throw new Error("illegal operation for maps without linking");
};
// map initialisation from existing object
// doesn't add inherited properties if not explicitly instructed to:
// omitting foreignKeys means foreignKeys === undefined, i.e. == false
// --> inherited properties won't be added
Map.from = function(obj, foreignKeys) {
var map = new Map;
for(var prop in obj) {
if(foreignKeys || obj.hasOwnProperty(prop))
map.put(prop, obj[prop]);
}
return map;
};
Map.prototype.disableLinking = function() {
this.link = Map.noop;
this.unlink = Map.noop;
this.disableLinking = Map.noop;
this.next = Map.illegal;
this.key = Map.illegal;
this.value = Map.illegal;
this.removeAll = Map.illegal;
return this;
};
// overwrite in Map instance if necessary
Map.prototype.hash = function(value) {
return (typeof value) + ' ' + (value instanceof Object ?
(value.__hash || (value.__hash = ++arguments.callee.current)) :
value.toString());
};
Map.prototype.hash.current = 0;
// --- mapping functions
Map.prototype.get = function(key) {
var item = this[this.hash(key)];
return item === undefined ? undefined : item.value;
};
Map.prototype.put = function(key, value) {
var hash = this.hash(key);
if(this[hash] === undefined) {
var item = { key : key, value : value };
this[hash] = item;
this.link(item);
++this.size;
}
else this[hash].value = value;
return this;
};
Map.prototype.remove = function(key) {
var hash = this.hash(key);
var item = this[hash];
if(item !== undefined) {
--this.size;
this.unlink(item);
delete this[hash];
}
return this;
};
// only works if linked
Map.prototype.removeAll = function() {
while(this.size)
this.remove(this.key());
return this;
};
// --- linked list helper functions
Map.prototype.link = function(item) {
if(this.size == 0) {
item.prev = item;
item.next = item;
this.current = item;
}
else {
item.prev = this.current.prev;
item.prev.next = item;
item.next = this.current;
this.current.prev = item;
}
};
Map.prototype.unlink = function(item) {
if(this.size == 0)
this.current = undefined;
else {
item.prev.next = item.next;
item.next.prev = item.prev;
if(item === this.current)
this.current = item.next;
}
};
// --- iterator functions - only work if map is linked
Map.prototype.next = function() {
this.current = this.current.next;
};
Map.prototype.key = function() {
return this.current.key;
};
Map.prototype.value = function() {
return this.current.value;
};
Exemple
Le script suivant
var map = new Map;
map.put('spam', 'eggs').
put('foo', 'bar').
put('foo', 'baz').
put({}, 'an object').
put({}, 'another object').
put(5, 'five').
put(5, 'five again').
put('5', 'another five');
for(var i = 0; i++ < map.size; map.next())
document.writeln(map.hash(map.key()) + ' : ' + map.value());
génère la sortie suivante:
string spam : eggs
string foo : baz
object 1 : an object
object 2 : another object
number 5 : five again
string 5 : another five
D'autres considérations
PEZ a suggéré de remplacer l' toString() méthode, sans doute avec notre fonction de hachage. Ce n'est pas possible car il ne fonctionne pas pour des valeurs primitives (évolution toString() pour les primitives est une très mauvaise idée). Si nous voulons toString() de retour des valeurs significatives pour les objets arbitraires, nous devons modifier Object.prototype, que certaines personnes (moi non inclus) considèrent verboten.
Edit: La version actuelle de mon Map mise en œuvre ainsi que d'autres JavaScript goodies peuvent être obtenus à partir d'ici.
