Équivalent Hashmap JavaScript

354

Comme indiqué clairement dans la mise à jour 3 sur cette réponse , cette notation:

var hash = {};
hash[X]

ne hache pas réellement l'objet X; en fait, il se convertit simplement Xen chaîne (via .toString()s'il s'agit d'un objet ou d'autres conversions intégrées pour divers types primitifs), puis recherche cette chaîne, sans la hacher, dans " hash". L'égalité des objets n'est pas non plus vérifiée - si deux objets différents ont la même conversion de chaîne, ils se remplaceront simplement.

Compte tenu de cela - existe-t-il des implémentations efficaces de hashmaps en javascript? (Par exemple, le deuxième résultat de Google javascript hashmapdonne une implémentation qui est O (n) pour toute opération. Divers autres résultats ignorent le fait que différents objets avec des représentations de chaînes équivalentes se remplacent.

Claudiu
la source
1
@Claudiu: Désolé pour la modification, mais la "carte" dans le titre était vraiment trompeuse. Revenez en arrière si vous n'êtes pas d'accord, je n'avais pas l'intention de fréquenter. :)
Tomalak
6
@Claudiu: Vous posez beaucoup de questions sur javascript. Bonnes questions. J'aime ça.
certains
2
@Claudiu: Pouvez-vous également créer un lien vers le résultat Google auquel vous faites référence? Différentes versions locales de Google renvoient des résultats différents, l'implémentation à laquelle vous faites référence ne semble même pas apparaître pour moi.
Tomalak
@Tomalak: J'allais juste écrire exactement la même chose!
certains
3
@Claudiu Non, ne liez pas à Google. Lien vers la page dont vous parliez (que vous avez trouvée par le biais de Google). Lier à google a tous les mêmes problèmes que d'expliquer quoi rechercher: google personnalisation des résultats en fonction de l'emplacement ou de l'historique de recherche, les résultats de google changeant au fil du temps (actuellement, c'est le meilleur résultat pour cette recherche) et tout ce qui peut le rendre montrer des résultats différents.
Jasper

Réponses:

371

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

Exemple:

var key = function(obj){
  // some unique object-dependent key
  return obj.totallyUniqueEmployeeIdKey; // just an example
};

var dict = {};

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

De cette façon, vous pouvez contrôler l'indexation effectuée par JavaScript sans soulever lourdement l'allocation de mémoire et la gestion des débordements.

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

La fonction de clé peut être aussi simple que de sélectionner les bons attributs de l'objet, par exemple, une clé ou un ensemble de clés, qui sont déjà uniques, une combinaison de clés, qui sont uniques ensemble, ou aussi complexe que d'utiliser des hachages cryptographiques comme dans DojoX Encoding ou DojoX UUID . Bien que ces dernières solutions puissent produire des clés uniques, personnellement, j'essaie de les éviter à tout prix, surtout si je sais ce qui rend mes objets uniques.

Mise à jour en 2014: Répondue en 2008, cette solution simple nécessite encore plus d'explications. Permettez-moi de clarifier l'idée sous forme de questions / réponses.

Votre solution n'a pas de vrai hachage. Où est-ce???

JavaScript est un langage de haut niveau. Sa primitive de base ( Object ) comprend une table de hachage pour conserver les propriétés. Cette table de hachage est généralement écrite dans un langage de bas niveau pour plus d'efficacité. En utilisant un objet simple avec des clés de chaîne, nous utilisons une table de hachage efficacement implémentée sans aucun effort de notre part.

Comment savez-vous qu'ils utilisent du hachage?

Il existe trois façons principales de conserver une collection d'objets adressables par une clé:

  • Non ordonné. Dans ce cas, pour récupérer un objet par sa clé, nous devons parcourir toutes les clés s'arrêtant lorsque nous le trouvons. En moyenne, il faudra n / 2 comparaisons.
  • Commandé.
    • Exemple # 1: un tableau trié - en faisant une recherche binaire, nous trouverons notre clé après des comparaisons de ~ log2 (n) en moyenne. Bien mieux.
    • Exemple # 2: un arbre. Encore une fois, ce sera ~ tentatives (log).
  • Table de hachage. En moyenne, cela nécessite un temps constant. Comparez: O (n) vs O (log n) vs O (1). Boom.

De toute évidence, les objets JavaScript utilisent des tables de hachage sous une forme ou une autre pour gérer les cas généraux.

Les fournisseurs de navigateurs utilisent-ils vraiment les tables de hachage ???

Vraiment.

Gèrent-ils les collisions?

Oui. Voir au dessus. Si vous avez trouvé une collision sur des chaînes inégales, n'hésitez pas à déposer un bug auprès d'un vendeur.

Alors quelle est votre idée?

Si vous voulez hacher un objet, trouvez ce qui le rend unique et utilisez-le comme clé. N'essayez pas de calculer le vrai hachage ou d'émuler des tables de hachage - il est déjà géré efficacement par l'objet JavaScript sous-jacent.

Utilisez cette clé avec JavaScript Objectpour tirer parti de sa table de hachage intégrée tout en évitant les conflits possibles avec les propriétés par défaut.

Exemples pour vous aider à démarrer:

  • Si vos objets incluent un nom d'utilisateur unique - utilisez-le comme clé.
  • S'il comprend un numéro de client unique - utilisez-le comme clé.
    • S'il comprend des numéros uniques émis par le gouvernement, comme un SSN ou un numéro de passeport, et que votre système n'autorise pas les doublons, utilisez-le comme clé.
  • Si une combinaison de champs est unique, utilisez-la comme clé.
    • L'abréviation d'état + le numéro de permis de conduire constituent une excellente clé.
    • L'abréviation du pays + le numéro de passeport est également une excellente clé.
  • Certaines fonctions sur des champs ou un objet entier peuvent renvoyer une valeur unique - utilisez-la comme clé.

J'ai utilisé votre suggestion et mis en cache tous les objets en utilisant un nom d'utilisateur. Mais un sage est nommé "toString", qui est une propriété intégrée! Qu'est-ce que je devrais faire maintenant?

De toute évidence, s'il est même possible à distance que la clé résultante soit exclusivement composée de caractères latins, vous devriez faire quelque chose. Par exemple, ajoutez tout caractère Unicode non latin que vous aimez au début ou à la fin pour annuler le conflit avec les propriétés par défaut: "#toString", "#MarySmith". Si une clé composite est utilisée, séparez les composants clés en utilisant une sorte de délimiteur non latin: "nom, ville, état".

En général, c'est l'endroit où nous devons être créatifs et sélectionner les clés les plus faciles avec des limitations données (unicité, conflits potentiels avec des propriétés par défaut).

Remarque: les clés uniques ne s'affrontent pas par définition, tandis que les conflits de hachage potentiels seront gérés par le sous-jacent Object.

Pourquoi n'aimez-vous pas les solutions industrielles?

À mon humble avis, le meilleur code n'est pas du tout un code: il ne contient aucune erreur, ne nécessite aucune maintenance, est facile à comprendre et s'exécute instantanément. Toutes les "tables de hachage en JavaScript" que j'ai vues étaient> 100 lignes de code et impliquaient plusieurs objets. Comparez avec: dict[key] = value.

Autre point: est-il même possible de battre une performance d'un objet primordial écrit dans un langage de bas niveau, en utilisant JavaScript et les mêmes objets primordiaux pour implémenter ce qui est déjà implémenté?

Je veux toujours hacher mes objets sans aucune clé!

Nous avons de la chance: ECMAScript 6 (prévu pour la version mi-2015, donner ou prendre 1-2 ans après pour se généraliser) définit la carte et le set .

À en juger par la définition, ils peuvent utiliser l'adresse de l'objet comme clé, ce qui rend les objets instantanément distincts sans clés artificielles. OTOH, deux objets différents, mais identiques, seront mappés comme distincts.

Ventilation de comparaison de MDN :

Les objets sont similaires aux cartes dans la mesure où ils vous permettent de définir des clés pour des valeurs, de récupérer ces valeurs, de supprimer des clés et de détecter si quelque chose est stocké sur une clé. Pour cette raison (et parce qu'il n'y avait pas d'alternatives intégrées), les objets ont été utilisés comme cartes historiquement; cependant, il existe des différences importantes qui rendent l'utilisation d'une carte préférable dans certains cas:

  • Les clés d'un objet sont des chaînes et des symboles, alors qu'elles peuvent être n'importe quelle valeur pour une carte, y compris les fonctions, les objets et toute primitive.
  • Les clés de la carte sont ordonnées tandis que les clés ajoutées à l'objet ne le sont pas. Ainsi, lors de son itération, un objet Map renvoie les clés par ordre d'insertion.
  • Vous pouvez facilement obtenir la taille d'une carte avec la propriété size, tandis que le nombre de propriétés dans un objet doit être déterminé manuellement.
  • Une carte est un itérable et peut donc être directement itéré, alors que l'itération sur un objet nécessite d'obtenir ses clés d'une certaine manière et de les itérer.
  • Un objet a un prototype, il y a donc des clés par défaut dans la carte qui pourraient entrer en collision avec vos clés si vous ne faites pas attention. Depuis ES5, cela peut être contourné en utilisant map = Object.create (null), mais cela est rarement fait.
  • Une carte peut mieux fonctionner dans des scénarios impliquant l'ajout et la suppression fréquents de paires de clés.
Eugene Lazutkin
la source
13
Cela ne ressemble pas à une bonne carte, car vous ne gérez pas les collisions. Si cela se produit: hash (obj1) == hash (obj2), vous allez perdre vos données.
beefeather
32
Le ciel vous aide lorsque "PAUL AINLEY" et "PAULA INLEY" s'inscrivent dans votre système ...
Matt R
34
@MattR En fait, votre exemple fonctionnera correctement sans l'aide du ciel, même avec une fonction de hachage simulée. J'espère que d'autres lecteurs se rendront compte qu'une fonction de hachage non réaliste trop simplifiée a été utilisée comme espace réservé pour démontrer une technique différente. Les deux codes commentent, et la réponse elle-même souligne qu'elle n'est pas réelle. La sélection des clés appropriées est discutée dans le dernier paragraphe de la réponse.
Eugene Lazutkin
6
@EugeneLazutkin - vous vous trompez toujours, j'ai peur. Votre exemple est toujours sujet aux collisions de hachage. Ne pensez pas que le simple fait de mettre le nom de famille en premier vous aidera en quelque sorte!
Matt R
3
@EugeneLazutkin La plupart des gens ne lisent pas que vous avez répondu à ceci AVANT qu'ES6 n'apparaisse même ... Permettez-moi de vous féliciter pour votre connaissance approfondie de JS.
Gabriel Andrés Brancolini
171

Description du problème

JavaScript n'a pas de type de carte général intégré (parfois appelé tableau associatif ou dictionnaire ) qui permet d'accéder à des valeurs arbitraires par des clés arbitraires. La structure de données fondamentale de JavaScript est l' objet , un type spécial de carte qui n'accepte que les chaînes comme clés et possède une sémantique spéciale comme l'héritage prototypique, les getters et setters et quelques autres vaudous.

Lorsque vous utilisez des objets comme cartes, vous devez vous rappeler que la clé sera convertie en une valeur de chaîne via toString(), ce qui entraîne un mappage 5et '5'la même valeur et tous les objets qui n'écrasent pas la toString()méthode à la valeur indexée par '[object Object]'. Vous pouvez également accéder involontairement à ses propriétés héritées si vous ne cochez pas hasOwnProperty().

Le type de tableau intégré de JavaScript n'aide pas du tout: les tableaux JavaScript ne sont pas des tableaux associatifs, mais seulement des objets avec quelques propriétés supplémentaires. Si vous voulez savoir pourquoi elles ne peuvent pas être utilisées comme cartes, regardez ici .

La solution d'Eugène

Eugene Lazutkin a déjà décrit l'idée de base d'utiliser une fonction de hachage personnalisée pour générer des chaînes uniques qui peuvent être utilisées pour rechercher les valeurs associées en tant que propriétés d'un objet dictionnaire. Ce sera probablement la solution la plus rapide, car les objets sont implémentés en interne sous forme de tables de hachage .

  • Remarque: les tables de hachage (parfois appelées cartes de hachage ) sont une implémentation particulière du concept de carte utilisant un tableau de sauvegarde et une recherche via des valeurs de hachage numériques. L'environnement d'exécution peut utiliser d'autres structures (telles que des arbres de recherche ou des listes de sauts ) pour implémenter des objets JavaScript, mais comme les objets sont la structure de données fondamentale, ils doivent être suffisamment optimisés.

Afin d'obtenir une valeur de hachage unique pour des objets arbitraires, une possibilité consiste à utiliser un compteur global et à mettre en cache la valeur de hachage dans l'objet lui-même (par exemple dans une propriété nommée __hash).

Une fonction de hachage qui fait cela est et fonctionne pour les valeurs primitives et les 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 Eugene. Pour plus de commodité, nous allons envelopper davantage dans une Mapclasse.

Ma Mapmise en œuvre

L'implémentation suivante stockera en outre les paires clé-valeur dans une liste doublement liée afin de permettre une itération rapide sur les clés et les valeurs. Pour fournir votre propre fonction de hachage, vous pouvez remplacer la hash()méthode de l'instance après sa 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 cette sortie:

string spam : eggs
string foo : baz
object 1 : an object
object 2 : another object
number 5 : five again
string 5 : another five

Considérations supplémentaires

PEZ a suggéré d'écraser la toString()méthode, probablement avec notre fonction de hachage. Ce n'est pas faisable car cela ne fonctionne pas pour les valeurs primitives (changer toString()pour les primitives est une très mauvaise idée). Si nous voulons toString()renvoyer des valeurs significatives pour des objets arbitraires, nous devrons les modifier Object.prototype, ce que certaines personnes (moi non compris) considèrent comme verboten .


Edit: La version actuelle de mon Mapimplémentation ainsi que d'autres goodies JavaScript peuvent être obtenus à partir d'ici .

Christoph
la source
ES5 déconseille l'utilisation de l' appelé ( goo.gl/EeStE ). Au lieu de cela, je suggère Map._counter = 0, et dans le constructeur de carte, faites this._hash = 'object ' + Map._counter++. Puis hash () devientreturn (value && value._hash) || (typeof(value) + ' ' + String(value));
broofa
Le lien vers le code est rompu: mercurial.intuxication.org/hg/js-hacks/raw-file/tip/map.js
ahcox
salut @Christoph, pourriez-vous mettre à jour votre lien vers où trouver l'implémentation de votre carte?
NumenorForLife
2
@ jsc123: J'examinerai cela - pour l'instant, vous pouvez obtenir un vidage du référentiel à pikacode.com/mercurial.intuxication.org/js-hacks.tar.gz
Christoph
58

Je sais que cette question est assez ancienne, mais il existe aujourd'hui de très bonnes solutions avec des bibliothèques externes.

JavaScript dispose également de son langage Map.

Jamel Toms
la source
2
C'est la façon d'avancer au 21ème siècle. Dommage que j'ai trouvé votre message après avoir fini mon code avec une moche carte faite maison. Les DEEE ont besoin de plus de votes pour votre réponse
Phung D. An
1
Collections.js a quelques implémentations, mais je n'en trouve pas dans underscore.js ou lodash ... à quoi faisiez-vous référence dans le soulignement qui serait utile?
Codebling
@CodeBling aucune idée. je pense que je l'ai confondu avec la fonction de carte. je vais le supprimer de la réponse.
Jamel Toms
3
C'est juste. Quiconque envisage Collections.js doit être conscient qu'il modifie les prototypes globaux Array, Function, Object et Regexp de manière problématique ( voir les problèmes que j'ai rencontrés ici ). Bien que j'étais initialement très satisfait de collections.js (et donc de cette réponse), les risques associés à son utilisation étaient trop élevés, alors je l'ai abandonné. Seule la branche v2 de kriskowal de collections.js (en particulier, v2.0.2 +) élimine les modifications globales du prototype et est sûre à utiliser.
Codebling
28

Voici un moyen simple et pratique d'utiliser quelque chose de similaire à la carte java:

var map= {
        'map_name_1': map_value_1,
        'map_name_2': map_value_2,
        'map_name_3': map_value_3,
        'map_name_4': map_value_4
        }

Et pour obtenir la valeur:

alert( map['map_name_1'] );    // fives the value of map_value_1

......  etc  .....
Miloš
la source
2
Cela fonctionne uniquement pour les clés de chaîne. Je pense que l'OP souhaitait utiliser des clés de tout type.
fractor
26

Selon ECMAScript 2015 (ES6), le javascript standard a une implémentation de carte. Plus d'informations sur ce qui peut être trouvé ici

Utilisation de base:

var myMap = new Map();
var keyString = "a string",
    keyObj = {},
    keyFunc = function () {};

// setting the values
myMap.set(keyString, "value associated with 'a string'");
myMap.set(keyObj, "value associated with keyObj");
myMap.set(keyFunc, "value associated with keyFunc");

myMap.size; // 3

// getting the values
myMap.get(keyString);    // "value associated with 'a string'"
myMap.get(keyObj);       // "value associated with keyObj"
myMap.get(keyFunc);      // "value associated with keyFunc"
Riyafa Abdul Hameed
la source
21

Vous pouvez utiliser ES6 WeakMapou Map:

  • Les WeakMaps sont des cartes clé / valeur dans lesquelles les clés sont des objets.

  • Maples objets sont de simples cartes clé / valeur. Toute valeur (à la fois des objets et des valeurs primitives) peut être utilisée comme clé ou comme valeur.

Sachez que ni l'un ni l'autre n'est largement pris en charge, mais vous pouvez utiliser ES6 Shim (nécessite natif ES5 ou ES5 Shim ) pour le prendre en charge Map, mais pas WeakMap( voir pourquoi ).

Oriol
la source
En 2019, ils sont très bien soutenus et ont des méthodes incroyables! developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
Juanma Menendez
13

Vous devez stocker dans certains couplets d'état interne des paires objet / valeur

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 utilisez-le 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 implémentation se situe également quelque part dans le sens de O (n). Les exemples d'Eugène ci-dessus sont le seul moyen d'obtenir un hachage qui fonctionne avec n'importe quelle vitesse que vous attendez d'un vrai hachage.

Mise à jour:

Une autre approche, dans le sens de la réponse d'Eugène, consiste à attacher en quelque sorte un ID unique à tous les objets. L'une de mes approches préférées consiste à prendre l'une des méthodes intégrées héritées de la superclasse Object, à la remplacer par un passage de fonction personnalisé et à attacher des propriétés à cet objet fonction. Si vous deviez réécrire ma méthode HashMap pour ce faire, cela ressemblerait à:

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 ne semble être que légèrement plus rapide, mais en théorie, elle sera considérablement plus rapide pour les grands ensembles de données.

viande en pot
la source
Un tableau associatif, c'est-à-dire un tableau de 2 tuples, est une carte, pas un HashMap; un HashMap est une carte qui utilise des hachages pour de meilleures performances.
Erik Kaplun
C'est vrai, mais pourquoi couper les cheveux sur le sujet? Il n'y a aucun moyen de créer une véritable carte de hachage en JavaScript car vous ne pouvez pas obtenir les adresses de mémoire d'objets. Et les paires clé / valeur d'objet intégrées de JavaScript (utilisées dans mon deuxième exemple) peuvent agir en tant que HashMaps, mais pas nécessairement, car il appartient au runtime utilisé dans le navigateur de savoir comment la recherche est implémentée.
viande en pot
11

Malheureusement, aucune des réponses ci-dessus n'était bonne pour mon cas: différents objets clés peuvent avoir le même code de hachage. Par conséquent, j'ai écrit une version HashMap simple de type Java:

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 clés doivent "implémenter" les méthodes hashCode () et equals ().

Michael Spector
la source
7
La préférence de new Array()plus []est d'assurer la ressemblance Java absolue de votre code? :)
Erik Kaplun
6

J'ai implémenté un HashMap JavaScript dont le code peut être obtenu à partir de http://github.com/lambder/HashMapJS/tree/master

Voici le code:

/*
 =====================================================================
 @license MIT
 @author Lambder
 @copyright 2009 Lambder.
 @end
 =====================================================================
 */
var HashMap = function() {
  this.initialize();
}

HashMap.prototype = {
  hashkey_prefix: "<#HashMapHashkeyPerfix>",
  hashcode_field: "<#HashMapHashkeyPerfix>",

  initialize: function() {
    this.backing_hash = {};
    this.code = 0;
  },
  /*
   maps value to key returning previous assocciation
   */
  put: function(key, value) {
    var prev;
    if (key && value) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        prev = this.backing_hash[hashCode];
      } else {
        this.code += 1;
        hashCode = this.hashkey_prefix + this.code;
        key[this.hashcode_field] = hashCode;
      }
      this.backing_hash[hashCode] = value;
    }
    return prev;
  },
  /*
   returns value associated with given key
   */
  get: function(key) {
    var value;
    if (key) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        value = this.backing_hash[hashCode];
      }
    }
    return value;
  },
  /*
   deletes association by given key.
   Returns true if the assocciation existed, false otherwise
   */
  del: function(key) {
    var success = false;
    if (key) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        var prev = this.backing_hash[hashCode];
        this.backing_hash[hashCode] = undefined;
        if(prev !== undefined)
          success = true;
      }
    }
    return success;
  }
}

//// Usage

// creation

var my_map = new HashMap();

// insertion

var a_key = {};
var a_value = {struct: "structA"};
var b_key = {};
var b_value = {struct: "structB"};
var c_key = {};
var c_value = {struct: "structC"};

my_map.put(a_key, a_value);
my_map.put(b_key, b_value);
var prev_b = my_map.put(b_key, c_value);

// retrieval

if(my_map.get(a_key) !== a_value){
  throw("fail1")
}
if(my_map.get(b_key) !== c_value){
  throw("fail2")
}
if(prev_b !== b_value){
  throw("fail3")
}

// deletion

var a_existed = my_map.del(a_key);
var c_existed = my_map.del(c_key);
var a2_existed = my_map.del(a_key);

if(a_existed !== true){
  throw("fail4")
}
if(c_existed !== false){
  throw("fail5")
}
if(a2_existed !== false){
  throw("fail6")
}
Lambder
la source
2
Votre code ne semble pas fonctionner avec la mise du même objet dans plusieurs HashMaps.
Erik Kaplun
5

Dans ECMA6, vous pouvez utiliser WeakMap

Exemple:

var wm1 = new WeakMap(),
    wm2 = new WeakMap(),
    wm3 = new WeakMap();
var o1 = {},
    o2 = function(){},
    o3 = window;

wm1.set(o1, 37);
wm1.set(o2, "azerty");
wm2.set(o1, o2); // a value can be anything, including an object or a function
wm2.set(o3, undefined);
wm2.set(wm1, wm2); // keys and values can be any objects. Even WeakMaps!

wm1.get(o2); // "azerty"
wm2.get(o2); // undefined, because there is no value for o2 on wm2
wm2.get(o3); // undefined, because that is the set value

wm1.has(o2); // true
wm2.has(o2); // false
wm2.has(o3); // true (even if the value itself is 'undefined')

wm3.set(o1, 37);
wm3.get(o1); // 37
wm3.clear();
wm3.get(o1); // undefined, because wm3 was cleared and there is no value for o1 anymore

wm1.has(o1);   // true
wm1.delete(o1);
wm1.has(o1);   // false

Mais:

Because of references being weak, WeakMap keys are not enumerable (i.e. there is no method giving you a list of the keys). 
Nox73
la source
oh louange jésus, ils ajoutent enfin des références faibles à javascript. il est temps ... +1 pour cela, mais ce serait en fait horrible à utiliser car les références sont faibles
Claudiu
2

Javascript ne construit pas Map / hashmap. Il doit être appelé tableau associatif .

hash["X"]est égal à hash.X, mais autorise "X" comme variable de chaîne. En d'autres termes, hash[x]est fonctionnellement égal àeval("hash."+x.toString())

Il est plus similaire à object.properties qu'à un mappage de valeurs-clés. Si vous cherchez un meilleur mappage clé / valeur en Javascript, veuillez utiliser l'objet Map que vous pouvez trouver sur le web.

Dennis C
la source
2

Essayez ma mise en œuvre de table de hachage JavaScript: http://www.timdown.co.uk/jshashtable

Il recherche une méthode hashCode () des objets clés, ou vous pouvez fournir une fonction de hachage lors de la création d'un objet Hashtable.

Tim Down
la source
2

Cela ressemble à une solution assez robuste: https://github.com/flesler/hashmap . Cela fonctionnera même bien pour les fonctions et les objets qui semblent identiques. Le seul hack qu'il utilise consiste à ajouter un membre obscur à un objet pour l'identifier. Si votre programme n'écrase pas cette variable obscure (c'est quelque chose comme hashid ), vous êtes en or.

BT
la source
2

Si les performances ne sont pas critiques (par exemple , la quantité de clés est relativement faible) et vous ne voulez pas polluer votre (ou peut - être pas votre) des objets avec des champs supplémentaires comme _hash, _id, etc., vous pourrez utiliser le fait que Array.prototype.indexOfemploie égalité stricte. Voici une implémentation simple:

var Dict = (function(){
    // IE 8 and earlier has no Array.prototype.indexOf
    function indexOfPolyfill(val) {
      for (var i = 0, l = this.length; i < l; ++i) {
        if (this[i] === val) {
          return i;
        }
      }
      return -1;
    }

    function Dict(){
      this.keys = [];
      this.values = [];
      if (!this.keys.indexOf) {
        this.keys.indexOf = indexOfPolyfill;
      }
    };

    Dict.prototype.has = function(key){
      return this.keys.indexOf(key) != -1;
    };

    Dict.prototype.get = function(key, defaultValue){
      var index = this.keys.indexOf(key);
      return index == -1 ? defaultValue : this.values[index];
    };

    Dict.prototype.set = function(key, value){
      var index = this.keys.indexOf(key);
      if (index == -1) {
        this.keys.push(key);
        this.values.push(value);
      } else {
        var prevValue = this.values[index];
        this.values[index] = value;
        return prevValue;
      }
    };

    Dict.prototype.delete = function(key){
      var index = this.keys.indexOf(key);
      if (index != -1) {
        this.keys.splice(index, 1);
        return this.values.splice(index, 1)[0];
      }
    };

    Dict.prototype.clear = function(){
      this.keys.splice(0, this.keys.length);
      this.values.splice(0, this.values.length);
    };

    return Dict;
})();

Exemple d'utilisation:

var a = {}, b = {},
    c = { toString: function(){ return '1'; } },
    d = 1, s = '1', u = undefined, n = null,
    dict = new Dict();

// keys and values can be anything
dict.set(a, 'a');
dict.set(b, 'b');
dict.set(c, 'c');
dict.set(d, 'd');
dict.set(s, 's');
dict.set(u, 'u');
dict.set(n, 'n');

dict.get(a); // 'a'
dict.get(b); // 'b'
dict.get(s); // 's'
dict.get(u); // 'u'
dict.get(n); // 'n'
// etc.

Par rapport à ES6 WeakMap, il a deux problèmes: le temps de recherche O (n) et la non-faiblesse (c'est-à-dire qu'il provoquera une fuite de mémoire si vous n'utilisez pas deleteou ne clearrelâchez pas les clés).

skozin
la source
2

My Map Implementation, dérivé de l'exemple de Christoph:

Exemple d'utilisation:

var map = new Map();  //creates an "in-memory" map
var map = new Map("storageId");  //creates a map that is loaded/persisted using html5 storage

function Map(storageId) {
    this.current = undefined;
    this.size = 0;
    this.storageId = storageId;
    if (this.storageId) {
        this.keys = new Array();
        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)];
    if (item === undefined) {
        if (this.storageId) {
            try {
                var itemStr = localStorage.getItem(this.storageId + key);
                if (itemStr && itemStr !== 'undefined') {
                    item = JSON.parse(itemStr);
                    this[this.hash(key)] = item;
                    this.keys.push(key);
                    ++this.size;
                }
            } catch (e) {
                console.log(e);
            }
        }
    }
    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;
    if (this.storageId) {
        this.keys.push(key);
        try {
            localStorage.setItem(this.storageId + key, JSON.stringify(this[hash]));
        } catch (e) {
            console.log(e);
        }
    }
    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];
    }
    if (this.storageId) {
        try {
            localStorage.setItem(this.storageId + key, undefined);
        } catch (e) {
            console.log(e);
        }
    }
    return this;
};

// only works if linked
Map.prototype.removeAll = function() {
    if (this.storageId) {
        for (var i=0; i<this.keys.length; i++) {
            this.remove(this.keys[i]);
        }
        this.keys.length = 0;
    } else {
        while(this.size)
            this.remove(this.key());
    }
    return this;
};

// --- linked list helper functions

Map.prototype.link = function(item) {
    if (this.storageId) {
        return;
    }
    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.storageId) {
        return;
    }
    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() {
    if (this.storageId) {
        return undefined;
    } else {
        return this.current.key;
    }
};

Map.prototype.value = function() {
    if (this.storageId) {
        return undefined;
    }
    return this.current.value;
};
g00dnatur3
la source
1

Ajout d'une autre solution: HashMapc'est à peu près la première classe que j'ai portée de Java vers Javascript. On pourrait dire qu'il y a beaucoup de surcharge, mais l'implémentation est presque 100% égale à l'implémentation de Java et inclut toutes les interfaces et sous-classes.

Le projet peut être trouvé ici: https://github.com/Airblader/jsava Je vais également attacher le code source (actuel) pour la classe HashMap, mais comme indiqué, cela dépend aussi de la super classe, etc. Le cadre OOP utilisé est qooxdoo.

Edit: Veuillez noter que ce code est déjà obsolète et se référer au projet github pour le travail en cours. Au moment de la rédaction de ce document, il existe également une ArrayListimplémentation.

qx.Class.define( 'jsava.util.HashMap', {
    extend: jsava.util.AbstractMap,
    implement: [jsava.util.Map, jsava.io.Serializable, jsava.lang.Cloneable],

    construct: function () {
        var args = Array.prototype.slice.call( arguments ),
            initialCapacity = this.self( arguments ).DEFAULT_INITIAL_CAPACITY,
            loadFactor = this.self( arguments ).DEFAULT_LOAD_FACTOR;

        switch( args.length ) {
            case 1:
                if( qx.Class.implementsInterface( args[0], jsava.util.Map ) ) {
                    initialCapacity = Math.max( ((args[0].size() / this.self( arguments ).DEFAULT_LOAD_FACTOR) | 0) + 1,
                        this.self( arguments ).DEFAULT_INITIAL_CAPACITY );
                    loadFactor = this.self( arguments ).DEFAULT_LOAD_FACTOR;
                } else {
                    initialCapacity = args[0];
                }
                break;
            case 2:
                initialCapacity = args[0];
                loadFactor = args[1];
                break;
        }

        if( initialCapacity < 0 ) {
            throw new jsava.lang.IllegalArgumentException( 'Illegal initial capacity: ' + initialCapacity );
        }
        if( initialCapacity > this.self( arguments ).MAXIMUM_CAPACITY ) {
            initialCapacity = this.self( arguments ).MAXIMUM_CAPACITY;
        }
        if( loadFactor <= 0 || isNaN( loadFactor ) ) {
            throw new jsava.lang.IllegalArgumentException( 'Illegal load factor: ' + loadFactor );
        }

        var capacity = 1;
        while( capacity < initialCapacity ) {
            capacity <<= 1;
        }

        this._loadFactor = loadFactor;
        this._threshold = (capacity * loadFactor) | 0;
        this._table = jsava.JsavaUtils.emptyArrayOfGivenSize( capacity, null );
        this._init();
    },

    statics: {
        serialVersionUID: 1,

        DEFAULT_INITIAL_CAPACITY: 16,
        MAXIMUM_CAPACITY: 1 << 30,
        DEFAULT_LOAD_FACTOR: 0.75,

        _hash: function (hash) {
            hash ^= (hash >>> 20) ^ (hash >>> 12);
            return hash ^ (hash >>> 7) ^ (hash >>> 4);
        },

        _indexFor: function (hashCode, length) {
            return hashCode & (length - 1);
        },

        Entry: qx.Class.define( 'jsava.util.HashMap.Entry', {
            extend: jsava.lang.Object,
            implement: [jsava.util.Map.Entry],

            construct: function (hash, key, value, nextEntry) {
                this._value = value;
                this._next = nextEntry;
                this._key = key;
                this._hash = hash;
            },

            members: {
                _key: null,
                _value: null,
                /** @type jsava.util.HashMap.Entry */
                _next: null,
                /** @type Number */
                _hash: 0,

                getKey: function () {
                    return this._key;
                },

                getValue: function () {
                    return this._value;
                },

                setValue: function (newValue) {
                    var oldValue = this._value;
                    this._value = newValue;
                    return oldValue;
                },

                equals: function (obj) {
                    if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.HashMap.Entry ) ) {
                        return false;
                    }

                    /** @type jsava.util.HashMap.Entry */
                    var entry = obj,
                        key1 = this.getKey(),
                        key2 = entry.getKey();
                    if( key1 === key2 || (key1 !== null && key1.equals( key2 )) ) {
                        var value1 = this.getValue(),
                            value2 = entry.getValue();
                        if( value1 === value2 || (value1 !== null && value1.equals( value2 )) ) {
                            return true;
                        }
                    }

                    return false;
                },

                hashCode: function () {
                    return (this._key === null ? 0 : this._key.hashCode()) ^
                        (this._value === null ? 0 : this._value.hashCode());
                },

                toString: function () {
                    return this.getKey() + '=' + this.getValue();
                },

                /**
                 * This method is invoked whenever the value in an entry is
                 * overwritten by an invocation of put(k,v) for a key k that's already
                 * in the HashMap.
                 */
                _recordAccess: function (map) {
                },

                /**
                 * This method is invoked whenever the entry is
                 * removed from the table.
                 */
                _recordRemoval: function (map) {
                }
            }
        } )
    },

    members: {
        /** @type jsava.util.HashMap.Entry[] */
        _table: null,
        /** @type Number */
        _size: 0,
        /** @type Number */
        _threshold: 0,
        /** @type Number */
        _loadFactor: 0,
        /** @type Number */
        _modCount: 0,
        /** @implements jsava.util.Set */
        __entrySet: null,

        /**
         * Initialization hook for subclasses. This method is called
         * in all constructors and pseudo-constructors (clone, readObject)
         * after HashMap has been initialized but before any entries have
         * been inserted.  (In the absence of this method, readObject would
         * require explicit knowledge of subclasses.)
         */
        _init: function () {
        },

        size: function () {
            return this._size;
        },

        isEmpty: function () {
            return this._size === 0;
        },

        get: function (key) {
            if( key === null ) {
                return this.__getForNullKey();
            }

            var hash = this.self( arguments )._hash( key.hashCode() );
            for( var entry = this._table[this.self( arguments )._indexFor( hash, this._table.length )];
                 entry !== null; entry = entry._next ) {
                /** @type jsava.lang.Object */
                var k;
                if( entry._hash === hash && ((k = entry._key) === key || key.equals( k )) ) {
                    return entry._value;
                }
            }

            return null;
        },

        __getForNullKey: function () {
            for( var entry = this._table[0]; entry !== null; entry = entry._next ) {
                if( entry._key === null ) {
                    return entry._value;
                }
            }

            return null;
        },

        containsKey: function (key) {
            return this._getEntry( key ) !== null;
        },

        _getEntry: function (key) {
            var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() );
            for( var entry = this._table[this.self( arguments )._indexFor( hash, this._table.length )];
                 entry !== null; entry = entry._next ) {
                /** @type jsava.lang.Object */
                var k;
                if( entry._hash === hash
                    && ( ( k = entry._key ) === key || ( key !== null && key.equals( k ) ) ) ) {
                    return entry;
                }
            }

            return null;
        },

        put: function (key, value) {
            if( key === null ) {
                return this.__putForNullKey( value );
            }

            var hash = this.self( arguments )._hash( key.hashCode() ),
                i = this.self( arguments )._indexFor( hash, this._table.length );
            for( var entry = this._table[i]; entry !== null; entry = entry._next ) {
                /** @type jsava.lang.Object */
                var k;
                if( entry._hash === hash && ( (k = entry._key) === key || key.equals( k ) ) ) {
                    var oldValue = entry._value;
                    entry._value = value;
                    entry._recordAccess( this );
                    return oldValue;
                }
            }

            this._modCount++;
            this._addEntry( hash, key, value, i );
            return null;
        },

        __putForNullKey: function (value) {
            for( var entry = this._table[0]; entry !== null; entry = entry._next ) {
                if( entry._key === null ) {
                    var oldValue = entry._value;
                    entry._value = value;
                    entry._recordAccess( this );
                    return oldValue;
                }
            }

            this._modCount++;
            this._addEntry( 0, null, value, 0 );
            return null;
        },

        __putForCreate: function (key, value) {
            var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
                i = this.self( arguments )._indexFor( hash, this._table.length );
            for( var entry = this._table[i]; entry !== null; entry = entry._next ) {
                /** @type jsava.lang.Object */
                var k;
                if( entry._hash === hash
                    && ( (k = entry._key) === key || ( key !== null && key.equals( k ) ) ) ) {
                    entry._value = value;
                    return;
                }
            }

            this._createEntry( hash, key, value, i );
        },

        __putAllForCreate: function (map) {
            var iterator = map.entrySet().iterator();
            while( iterator.hasNext() ) {
                var entry = iterator.next();
                this.__putForCreate( entry.getKey(), entry.getValue() );
            }
        },

        _resize: function (newCapacity) {
            var oldTable = this._table,
                oldCapacity = oldTable.length;
            if( oldCapacity === this.self( arguments ).MAXIMUM_CAPACITY ) {
                this._threshold = Number.MAX_VALUE;
                return;
            }

            var newTable = jsava.JsavaUtils.emptyArrayOfGivenSize( newCapacity, null );
            this._transfer( newTable );
            this._table = newTable;
            this._threshold = (newCapacity * this._loadFactor) | 0;
        },

        _transfer: function (newTable) {
            var src = this._table,
                newCapacity = newTable.length;
            for( var j = 0; j < src.length; j++ ) {
                var entry = src[j];
                if( entry !== null ) {
                    src[j] = null;
                    do {
                        var next = entry._next,
                            i = this.self( arguments )._indexFor( entry._hash, newCapacity );
                        entry._next = newTable[i];
                        newTable[i] = entry;
                        entry = next;
                    } while( entry !== null );
                }
            }
        },

        putAll: function (map) {
            var numKeyToBeAdded = map.size();
            if( numKeyToBeAdded === 0 ) {
                return;
            }

            if( numKeyToBeAdded > this._threshold ) {
                var targetCapacity = (numKeyToBeAdded / this._loadFactor + 1) | 0;
                if( targetCapacity > this.self( arguments ).MAXIMUM_CAPACITY ) {
                    targetCapacity = this.self( arguments ).MAXIMUM_CAPACITY;
                }

                var newCapacity = this._table.length;
                while( newCapacity < targetCapacity ) {
                    newCapacity <<= 1;
                }
                if( newCapacity > this._table.length ) {
                    this._resize( newCapacity );
                }
            }

            var iterator = map.entrySet().iterator();
            while( iterator.hasNext() ) {
                var entry = iterator.next();
                this.put( entry.getKey(), entry.getValue() );
            }
        },

        remove: function (key) {
            var entry = this._removeEntryForKey( key );
            return entry === null ? null : entry._value;
        },

        _removeEntryForKey: function (key) {
            var hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
                i = this.self( arguments )._indexFor( hash, this._table.length ),
                prev = this._table[i],
                entry = prev;

            while( entry !== null ) {
                var next = entry._next,
                    /** @type jsava.lang.Object */
                        k;
                if( entry._hash === hash
                    && ( (k = entry._key) === key || ( key !== null && key.equals( k ) ) ) ) {
                    this._modCount++;
                    this._size--;
                    if( prev === entry ) {
                        this._table[i] = next;
                    } else {
                        prev._next = next;
                    }
                    entry._recordRemoval( this );
                    return entry;
                }
                prev = entry;
                entry = next;
            }

            return entry;
        },

        _removeMapping: function (obj) {
            if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.Map.Entry ) ) {
                return null;
            }

            /** @implements jsava.util.Map.Entry */
            var entry = obj,
                key = entry.getKey(),
                hash = (key === null) ? 0 : this.self( arguments )._hash( key.hashCode() ),
                i = this.self( arguments )._indexFor( hash, this._table.length ),
                prev = this._table[i],
                e = prev;

            while( e !== null ) {
                var next = e._next;
                if( e._hash === hash && e.equals( entry ) ) {
                    this._modCount++;
                    this._size--;
                    if( prev === e ) {
                        this._table[i] = next;
                    } else {
                        prev._next = next;
                    }
                    e._recordRemoval( this );
                    return e;
                }
                prev = e;
                e = next;
            }

            return e;
        },

        clear: function () {
            this._modCount++;
            var table = this._table;
            for( var i = 0; i < table.length; i++ ) {
                table[i] = null;
            }
            this._size = 0;
        },

        containsValue: function (value) {
            if( value === null ) {
                return this.__containsNullValue();
            }

            var table = this._table;
            for( var i = 0; i < table.length; i++ ) {
                for( var entry = table[i]; entry !== null; entry = entry._next ) {
                    if( value.equals( entry._value ) ) {
                        return true;
                    }
                }
            }

            return false;
        },

        __containsNullValue: function () {
            var table = this._table;
            for( var i = 0; i < table.length; i++ ) {
                for( var entry = table[i]; entry !== null; entry = entry._next ) {
                    if( entry._value === null ) {
                        return true;
                    }
                }
            }

            return false;
        },

        clone: function () {
            /** @type jsava.util.HashMap */
            var result = null;
            try {
                result = this.base( arguments );
            } catch( e ) {
                if( !qx.Class.isSubClassOf( e.constructor, jsava.lang.CloneNotSupportedException ) ) {
                    throw e;
                }
            }

            result._table = jsava.JsavaUtils.emptyArrayOfGivenSize( this._table.length, null );
            result.__entrySet = null;
            result._modCount = 0;
            result._size = 0;
            result._init();
            result.__putAllForCreate( this );

            return result;
        },

        _addEntry: function (hash, key, value, bucketIndex) {
            var entry = this._table[bucketIndex];
            this._table[bucketIndex] = new (this.self( arguments ).Entry)( hash, key, value, entry );
            if( this._size++ >= this._threshold ) {
                this._resize( 2 * this._table.length );
            }
        },

        _createEntry: function (hash, key, value, bucketIndex) {
            var entry = this._table[bucketIndex];
            this._table[bucketIndex] = new (this.self( arguments ).Entry)( hash, key, value, entry );
            this._size++;
        },

        keySet: function () {
            var keySet = this._keySet;
            return keySet !== null ? keySet : ( this._keySet = new this.KeySet( this ) );
        },

        values: function () {
            var values = this._values;
            return values !== null ? values : ( this._values = new this.Values( this ) );
        },

        entrySet: function () {
            return this.__entrySet0();
        },

        __entrySet0: function () {
            var entrySet = this.__entrySet;
            return entrySet !== null ? entrySet : ( this.__entrySet = new this.EntrySet( this ) );
        },

        /** @private */
        HashIterator: qx.Class.define( 'jsava.util.HashMap.HashIterator', {
            extend: jsava.lang.Object,
            implement: [jsava.util.Iterator],

            type: 'abstract',

            /** @protected */
            construct: function (thisHashMap) {
                this.__thisHashMap = thisHashMap;
                this._expectedModCount = this.__thisHashMap._modCount;
                if( this.__thisHashMap._size > 0 ) {
                    var table = this.__thisHashMap._table;
                    while( this._index < table.length && ( this._next = table[this._index++] ) === null ) {
                        // do nothing
                    }
                }
            },

            members: {
                __thisHashMap: null,

                /** @type jsava.util.HashMap.Entry */
                _next: null,
                /** @type Number */
                _expectedModCount: 0,
                /** @type Number */
                _index: 0,
                /** @type jsava.util.HashMap.Entry */
                _current: null,

                hasNext: function () {
                    return this._next !== null;
                },

                _nextEntry: function () {
                    if( this.__thisHashMap._modCount !== this._expectedModCount ) {
                        throw new jsava.lang.ConcurrentModificationException();
                    }

                    var entry = this._next;
                    if( entry === null ) {
                        throw new jsava.lang.NoSuchElementException();
                    }

                    if( (this._next = entry._next) === null ) {
                        var table = this.__thisHashMap._table;
                        while( this._index < table.length && ( this._next = table[this._index++] ) === null ) {
                            // do nothing
                        }
                    }

                    this._current = entry;
                    return entry;
                },

                remove: function () {
                    if( this._current === null ) {
                        throw new jsava.lang.IllegalStateException();
                    }

                    if( this.__thisHashMap._modCount !== this._expectedModCount ) {
                        throw new jsava.lang.ConcurrentModificationException();
                    }

                    var key = this._current._key;
                    this._current = null;
                    this.__thisHashMap._removeEntryForKey( key );
                    this._expectedModCount = this.__thisHashMap._modCount;
                }
            }
        } ),

        _newKeyIterator: function () {
            return new this.KeyIterator( this );
        },

        _newValueIterator: function () {
            return new this.ValueIterator( this );
        },

        _newEntryIterator: function () {
            return new this.EntryIterator( this );
        },

        /** @private */
        ValueIterator: qx.Class.define( 'jsava.util.HashMap.ValueIterator', {
            extend: jsava.util.HashMap.HashIterator,

            construct: function (thisHashMap) {
                this.base( arguments, thisHashMap );
            },

            members: {
                next: function () {
                    return this._nextEntry()._value;
                }
            }
        } ),

        /** @private */
        KeyIterator: qx.Class.define( 'jsava.util.HashMap.KeyIterator', {
            extend: jsava.util.HashMap.HashIterator,

            construct: function (thisHashMap) {
                this.base( arguments, thisHashMap );
            },

            members: {
                next: function () {
                    return this._nextEntry().getKey();
                }
            }
        } ),

        /** @private */
        EntryIterator: qx.Class.define( 'jsava.util.HashMap.EntryIterator', {
            extend: jsava.util.HashMap.HashIterator,

            construct: function (thisHashMap) {
                this.base( arguments, thisHashMap );
            },

            members: {
                next: function () {
                    return this._nextEntry();
                }
            }
        } ),

        /** @private */
        KeySet: qx.Class.define( 'jsava.util.HashMap.KeySet', {
            extend: jsava.util.AbstractSet,

            construct: function (thisHashMap) {
                this.base( arguments );
                this.__thisHashMap = thisHashMap;
            },

            members: {
                __thisHashMap: null,

                iterator: function () {
                    return this.__thisHashMap._newKeyIterator();
                },

                size: function () {
                    return this.__thisHashMap._size;
                },

                contains: function (obj) {
                    return this.__thisHashMap.containsKey( obj );
                },

                remove: function (obj) {
                    return this.__thisHashMap._removeEntryForKey( obj ) !== null;
                },

                clear: function () {
                    this.__thisHashMap.clear();
                }
            }
        } ),

        /** @private */
        Values: qx.Class.define( 'jsava.util.HashMap.Values', {
            extend: jsava.util.AbstractCollection,

            construct: function (thisHashMap) {
                this.base( arguments );
                this.__thisHashMap = thisHashMap;
            },

            members: {
                __thisHashMap: null,

                iterator: function () {
                    return this.__thisHashMap._newValueIterator();
                },

                size: function () {
                    return this.__thisHashMap._size;
                },

                contains: function (obj) {
                    return this.__thisHashMap.containsValue( obj );
                },

                clear: function () {
                    this.__thisHashMap.clear();
                }
            }
        } ),

        /** @private */
        EntrySet: qx.Class.define( 'jsava.util.HashMap.EntrySet', {
            extend: jsava.util.AbstractSet,

            construct: function (thisHashMap) {
                this.base( arguments );
                this.__thisHashMap = thisHashMap;
            },

            members: {
                __thisHashMap: null,

                iterator: function () {
                    return this.__thisHashMap._newEntryIterator();
                },

                size: function () {
                    return this.__thisHashMap._size;
                },

                contains: function (obj) {
                    if( obj === null || !qx.Class.implementsInterface( obj, jsava.util.Map.Entry ) ) {
                        return false;
                    }

                    /** @implements jsava.util.Map.Entry */
                    var entry = obj,
                        candidate = this.__thisHashMap._getEntry( entry.getKey() );
                    return candidate !== null && candidate.equals( entry );
                },

                remove: function (obj) {
                    return this.__thisHashMap._removeMapping( obj ) !== null;
                },

                clear: function () {
                    this.__thisHashMap.clear();
                }
            }
        } )
    }
} );
Ingo Bürk
la source
Hmm approche intéressante .. avez-vous pensé à essayer une approche automatisée? c'est-à-dire, exécuter un compilateur Java vers javascript sur le code source de l'implémentation java actuelle?
Claudiu
Non :) C'est juste un projet amusant pour moi et il y avait pas mal de choses où je ne pouvais pas simplement "copier" du code. Je ne connais pas les compilateurs Java vers Javascript, même si je pense qu'ils existent. Je ne sais pas dans quelle mesure ils traduiraient cela. Je suis à peu près certain qu'ils ne produiraient pas de code de bonne qualité de toute façon.
Ingo Bürk du
Ah gotcha. Je pensais au compilateur de Google Web Toolkit , mais il semble qu'ils aient fini par faire ce que vous faites ici pour les bibliothèques de base: "Le compilateur GWT prend en charge la grande majorité du langage Java lui-même. La bibliothèque d'exécution GWT émule un sous-ensemble pertinent de la Bibliothèque d'exécution Java. ". Peut-être quelque chose à regarder pour voir comment d'autres ont résolu le même problème!
Claudiu
Ouais. Je suis sûr que la solution de Google est bien au-delà de la mienne, mais là encore, je m'amuse juste à jouer. Malheureusement, le code source semble avoir été révoqué (?), Au moins je ne peux pas le parcourir et les liens intéressants semblent morts. Dommage, j'aurais adoré le regarder.
Ingo Bürk
S'amuser en jouant est la meilleure façon d'apprendre =). merci pour le partage
Claudiu
0

Encore une autre implémentation de carte par moi. Avec randomiseur, 'génériques' et 'itérateur' =)

var HashMap = function (TKey, TValue) {
    var db = [];
    var keyType, valueType;

    (function () {
        keyType = TKey;
        valueType = TValue;
    })();

    var getIndexOfKey = function (key) {
        if (typeof key !== keyType)
            throw new Error('Type of key should be ' + keyType);
        for (var i = 0; i < db.length; i++) {
            if (db[i][0] == key)
                return i;
        }
        return -1;
    }

    this.add = function (key, value) {
        if (typeof key !== keyType) {
            throw new Error('Type of key should be ' + keyType);
        } else if (typeof value !== valueType) {
            throw new Error('Type of value should be ' + valueType);
        }
        var index = getIndexOfKey(key);
        if (index === -1)
            db.push([key, value]);
        else
            db[index][1] = value;
        return this;
    }

    this.get = function (key) {
        if (typeof key !== keyType || db.length === 0)
            return null;
        for (var i = 0; i < db.length; i++) {
            if (db[i][0] == key)
                return db[i][1];
        }
        return null;
    }

    this.size = function () {
        return db.length;
    }

    this.keys = function () {
        if (db.length === 0)
            return [];
        var result = [];
        for (var i = 0; i < db.length; i++) {
            result.push(db[i][0]);
        }
        return result;
    }

    this.values = function () {
        if (db.length === 0)
            return [];
        var result = [];
        for (var i = 0; i < db.length; i++) {
            result.push(db[i][1]);
        }
        return result;
    }

    this.randomize = function () {
        if (db.length === 0)
            return this;
        var currentIndex = db.length, temporaryValue, randomIndex;
        while (0 !== currentIndex) {
            randomIndex = Math.floor(Math.random() * currentIndex);
            currentIndex--;
            temporaryValue = db[currentIndex];
            db[currentIndex] = db[randomIndex];
            db[randomIndex] = temporaryValue;
        }
        return this;
    }

    this.iterate = function (callback) {
        if (db.length === 0)
            return false;
        for (var i = 0; i < db.length; i++) {
            callback(db[i][0], db[i][1]);
        }
        return true;
    }
}

Exemple:

var a = new HashMap("string", "number");
a.add('test', 1132)
 .add('test14', 666)
 .add('1421test14', 12312666)
 .iterate(function (key, value) {console.log('a['+key+']='+value)});
/*
a[test]=1132
a[test14]=666
a[1421test14]=12312666 
*/
a.randomize();
/*
a[1421test14]=12312666
a[test]=1132
a[test14]=666
*/
ovnie
la source