317 votes

JavaScript Hashmap Équivalent

Comme l'indique clairement la mise à jour 3 sur cette réponse, cette notation:

var hash = {};
hash[X]

n'a pas fait de hachage de l'objet X; il en fait juste convertit X d'une chaîne de caractères (par .toString() si c'est un objet, ou d'une autre intégrée dans les conversions pour divers types primitifs) et puis regarde cette chaîne, sans hachage, dans "hash". Objet de l'égalité est pas non vérifié - si deux objets ont la même chaîne de conversion, ils vont tout simplement écraser les uns les autres.

Compte tenu de cette - est-il efficace implémentations de hashmaps en javascript? (Par exemple, le 2ème Google suite de l' javascript hashmap donne une mise en œuvre qui est O(n) pour toute opération. Diverses autres résultats ignorer le fait que les différents objets avec les mêmes représentations de chaîne d'écraser les uns les autres.

321voto

Eugene Lazutkin Points 22414

Pourquoi ne pas hachage vos objets vous-même, et d'utiliser les chaînes de caractères comme des clés pour un JavaScript dictionnaire? Après tout, vous êtes le mieux placé pour savoir ce qui rend vos objets uniques. C'est ce que je fais.

Exemple:

var hash = function(obj){
  // some cool hashing
  return obj.lastName + obj.firstName; // just an example
};

var dict = {};

dict[hash(obj1)] = obj1;
dict[hash(obj2)] = obj2;

De cette façon, vous pouvez contrôler le hachage fait en JavaScript sans soulever des poids lourds de l'allocation de la mémoire, de dépassement et de manutention.

Bien sûr, si vous voulez vraiment la "classe industrielle de la solution", vous pouvez créer une classe paramétrée par la fonction de hachage, et avec toutes les API nécessaires du conteneur, mais ... nous l'utilisation de JavaScript, et d'essayer d'être simple et léger, cette solution fonctionnelle est simple et rapide.

La fonction de hachage peut être aussi simple que de sélectionner droit attributs de l'objet, par exemple, une "clé", ou un ensemble de touches, qui sont déjà unique, ou aussi complexe que l'utilisation de certaines des empreintes cryptographiques comme dans DojoX Encodage, ou DojoX UUID.

171voto

Christoph Points 64389

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.

19voto

Oriol Points 20803

Vous pouvez utiliser ES6 WeakMap ou Map:

  • WeakMaps sont la clé/valeur des cartes dans lequel les clés sont des objets.

  • Map des objets sont simples clé/valeur des cartes. N'importe quelle valeur (à la fois des objets et des valeurs primitives) peut être utilisé comme une clé ou une valeur.

Sachez que ni est largement pris en charge, mais vous pouvez utiliser ES6 Cale (nécessite des ES5 ou ES5 Cale) pour appuyer Map, mais pas WeakMap (voir pourquoi).

13voto

pottedmeat Points 1625

Vous devez stocker dans certains état interne des couplets de l'objet/de la valeur des paires

HashMap = function(){
  this._dict = [];
}
HashMap.prototype._get = function(key){
  for(var i=0, couplet; couplet = this._dict[i]; i++){
    if(couplet[0] === key){
      return couplet;
    }
  }
}
HashMap.prototype.put = function(key, value){
  var couplet = this._get(key);
  if(couplet){
    couplet[1] = value;
  }else{
    this._dict.push([key, value]);
  }
  return this; // for chaining
}
HashMap.prototype.get = function(key){
  var couplet = this._get(key);
  if(couplet){
    return couplet[1];
  }
}

Et à l'utiliser comme tel:

var color = {}; // unique object instance
var shape = {}; // unique object instance
var map = new HashMap();
map.put(color, "blue");
map.put(shape, "round");
console.log("Item is", map.get(color), "and", map.get(shape));

Bien sûr, cette mise en œuvre est aussi quelque part le long des lignes de O(n). Eugène exemples ci-dessus sont la seule façon d'obtenir un hash qui fonctionne avec n'importe quel type de vitesse que vous attendez d'un réel de hachage.

Mise à jour:

Une autre approche, à l'instar d'Eugène de réponse est en quelque sorte joindre un ID unique pour tous les objets. L'un de mes préférés approches est de prendre l'une des méthodes héritées de l'Objet de la superclasse, la remplacer avec une fonction personnalisée d'intercommunication et de fixer les propriétés de la fonction d'objet. Si vous deviez réécrire mon HashMap méthode pour ce faire, il devrait ressembler à:

HashMap = function(){
  this._dict = {};
}
HashMap.prototype._shared = {id: 1};
HashMap.prototype.put = function put(key, value){
  if(typeof key == "object"){
    if(!key.hasOwnProperty._id){
      key.hasOwnProperty = function(key){
        return Object.prototype.hasOwnProperty.call(this, key);
      }
      key.hasOwnProperty._id = this._shared.id++;
    }
    this._dict[key.hasOwnProperty._id] = value;
  }else{
    this._dict[key] = value;
  }
  return this; // for chaining
}
HashMap.prototype.get = function get(key){
  if(typeof key == "object"){
    return this._dict[key.hasOwnProperty._id];
  }
  return this._dict[key];
}

Cette version semble être légèrement plus rapide, mais en théorie, il sera nettement plus rapide pour les grands ensembles de données.

11voto

spektom Points 11130

Malheureusement, aucune des réponses ci-dessus ont été bonnes pour mon cas: différents objets peuvent avoir le même code de hachage. Donc, j'ai écrit un simple Java-comme table de hachage version:

function HashMap() {
    this.buckets = {};
}

HashMap.prototype.put = function(key, value) {
    var hashCode = key.hashCode();
    var bucket = this.buckets[hashCode];
    if (!bucket) {
        bucket = new Array();
        this.buckets[hashCode] = bucket;
    }
    for (var i = 0; i < bucket.length; ++i) {
        if (bucket[i].key.equals(key)) {
            bucket[i].value = value;
            return;
        }
    }
    bucket.push({ key: key, value: value });
}

HashMap.prototype.get = function(key) {
    var hashCode = key.hashCode();
    var bucket = this.buckets[hashCode];
    if (!bucket) {
        return null;
    }
    for (var i = 0; i < bucket.length; ++i) {
        if (bucket[i].key.equals(key)) {
            return bucket[i].value;
        }
    }
}

HashMap.prototype.keys = function() {
    var keys = new Array();
    for (var hashKey in this.buckets) {
        var bucket = this.buckets[hashKey];
        for (var i = 0; i < bucket.length; ++i) {
            keys.push(bucket[i].key);
        }
    }
    return keys;
}

HashMap.prototype.values = function() {
    var values = new Array();
    for (var hashKey in this.buckets) {
        var bucket = this.buckets[hashKey];
        for (var i = 0; i < bucket.length; ++i) {
            values.push(bucket[i].value);
        }
    }
    return values;
}

Remarque: les objets doivent "mettre en œuvre" hashCode() et equals() méthodes.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by: