Existe-t-il une implémentation de dictionnaire en JavaScript?

Comment puis-je implémenter un tableau avec un indexeur en JavaScript? Y a-t-il quelque chose comme un dictionnaire dans. Net?

53
demandé sur R. Martinho Fernandes 2011-04-08 16:11:18

10 réponses

Techniquement non, mais vous pouvez utiliser un objet JavaScript régulier comme un dictionnaire:

var a = {"a":"wohoo", 2:"hello2", "d":"hello"};
alert(a["a"]);
alert(a[2]);
alert(a["d"]);
89
répondu shahkalpesh 2013-11-28 17:42:10

John Resig (auteur de jQuery) Posté récemment sur les recherches de dictionnaire en javascript.

Sa solution consiste à attribuer les valeurs du dictionnaire en tant que propriétés d'un objet. Code collé verbatim de l'article ci-dessus:

// The dictionary lookup object
var dict = {};
// Do a jQuery Ajax request for the text dictionary
$.get( "dict/dict.txt", function( txt ) {
  // Get an array of all the words
  var words = txt.split( "\n" );

  // And add them as properties to the dictionary lookup
  // This will allow for fast lookups later
  for ( var i = 0; i < words.length; i++ ) {
    dict[ words[i] ] = true;
  }

  // The game would start after the dictionary was loaded
  // startGame();
});

// Takes in an array of letters and finds the longest
// possible word at the front of the letters
function findWord( letters ) {
  // Clone the array for manipulation
  var curLetters = letters.slice( 0 ), word = "";

  // Make sure the word is at least 3 letters long
  while ( curLetters.length > 2 ) {
    // Get a word out of the existing letters
    word = curLetters.join("");

    // And see if it's in the dictionary
    if ( dict[ word ] ) {
      // If it is, return that word
      return word;
    }

    // Otherwise remove another letter from the end
    curLetters.pop();
  }
}
10
répondu Andy 2011-04-08 12:12:48

Vous pouvez essayer buckets , est une bibliothèque de structure de données javascript, il vous permet d'utiliser n'importe quel type d'objet dans un dictionnaire.

9
répondu Daniel 2012-09-29 04:18:17

Dans mon dernier projet, j'ai été chargé de créer une application client de navigateur qui lirait 10 de milliers de lignes de données, puis regrouperait et agrégerait les données pour les afficher dans les grilles et les graphiques. Les technologies cibles étaient HTML 5, CSS 3 et EMCS 5.(navigateur moderne en Juin 2013). Parce que l'ancienne compatibilité du navigateur n'était pas un problème, les bibliothèques externes étaient limitées à D3 (pas de JQuery).

J'avais besoin de construire un modèle de données. J'en avais déjà construit un en C# et je me suis appuyé sur la coutume objets de dictionnaire pour accéder rapidement aux données, aux groupes et aux agrégats. Je n'avais pas travaillé en JavaScript depuis des années, alors j'ai commencé à chercher un dictionnaire. J'ai trouvé que JavaScript n'avait toujours pas de véritable dictionnaire natif. J'ai trouvé quelques exemples d'implémentations mais rien qui réponde vraiment à mes attentes. J'ai donc créé une.

Comme je l'ai mentionné, je n'avais pas travaillé en JavaScript depuis des années. Les progrès (ou peut-être simplement la disponibilité de l'information sur le web) étaient assez impressionnants. Tout mon travail précédent était avec les langages basés sur les classes, le langage de base prototype a pris un certain temps pour s'y habituer (et j'ai encore un long chemin à parcourir).

Ce projet, comme la plupart, était dû avant de commencer, donc j'ai appris en faisant beaucoup des erreurs newb qui seraient attendues lors de la transition d'une classe à un langage basé sur un prototype. Le dictionnaire créé était fonctionnel mais après un certain temps, j'ai réalisé quelques améliorations que je pouvais faire en le rendant moins newbish. Le projet a manqué de financement avant J'ai eu le temps de retravailler le dictionnaire. Oh, Et ma position a perdu du financement en même temps (incroyable comment cela peut arriver). Je décide donc de recréer le dictionnaire en utilisant ce que j'avais appris et de déterminer si le dictionnaire était en fait une amélioration des performances par rapport à un tableau.

/*
* Dictionary Factory Object
* Holds common object functions. similar to V-Table
* this.New() used to create new dictionary objects
* Uses Object.defineProperties so won't work on older browsers.
* Browser Compatibility (https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/defineProperties)
*      Firefox (Gecko) 4.0 (2), Chrome 5, IE 9, Opera 11.60, Safari 5
*/
function Dict() {

    /*
    * Create a new Dictionary
    */
    this.New = function () {
        return new dict();
    };

    /*
    * Return argument f if it is a function otherwise return undefined
    */
    function ensureF(f) {
        if (isFunct(f)) {
            return f;
        }
    }

    function isFunct(f) {
        return (typeof f == "function");
    }

    /*
    * Add a "_" as first character just to be sure valid property name
    */
    function makeKey(k) {
        return "_" + k;
    };

    /*
    * Key Value Pair object - held in array
    */
    function newkvp(key, value) {
        return {
            key: key,
            value: value,
            toString: function () { return this.key; },
            valueOf: function () { return this.key; }
        };
    };

    /*
    * Return the current set of keys. 
    */
    function keys(a) {
        // remove the leading "-" character from the keys
        return a.map(function (e) { return e.key.substr(1); });
        // Alternative: Requires Opera 12 vs. 11.60
        // -- Must pass the internal object instead of the array
        // -- Still need to remove the leading "-" to return user key values
        //    Object.keys(o).map(function (e) { return e.key.substr(1); });
    };

    /*
    * Return the current set of values. 
    */
    function values(a) {
        return a.map(function(e) { return e.value; } );
    };

    /*
    * Return the current set of key value pairs. 
    */
    function kvPs(a) {
        // remove the leading "-" character from the keys
        return a.map(function (e) { return newkvp(e.key.substr(1), e.value); });
    }

    /*
    * Returns true if key exists in the dictionary.
    * k - Key to check (with the leading "_" character) 
    */
    function exists(k, o) {
        return o.hasOwnProperty(k);
    }

    /*
    * Array Map implementation
    */
    function map(a, f) {
        if (!isFunct(f)) { return; }
        return a.map(function (e, i) { return f(e.value, i); });
    }

    /*
    * Array Every implementation
    */
    function every(a, f) {
        if (!isFunct(f)) { return; }
        return a.every(function (e, i) { return f(e.value, i) });
    }

    /*
    * Returns subset of "values" where function "f" returns true for the "value"
    */
    function filter(a, f) {
        if (!isFunct(f)) {return; }
        var ret = a.filter(function (e, i) { return f(e.value, i); });
        // if anything returned by array.filter, then get the "values" from the key value pairs
        if (ret && ret.length > 0) {
            ret = values(ret);
        }
        return ret;
    }

    /*
    * Array Reverse implementation
    */
    function reverse(a, o) {
        a.reverse();
        reindex(a, o, 0);
    }

    /**
    * Randomize array element order in-place.
    * Using Fisher-Yates shuffle algorithm.
    * (Added just because:-)
    */
    function shuffle(a, o) {
        var j, t;
        for (var i = a.length - 1; i > 0; i--) {
            j = Math.floor(Math.random() * (i + 1));
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        reindex(a, o, 0);
        return a;
    }
    /*
    * Array Some implementation
    */
    function some(a, f) {
        if (!isFunct(f)) { return; }
        return a.some(function (e, i) { return f(e.value, i) });
    }

    /*
    * Sort the dictionary. Sorts the array and reindexes the object.
    * a - dictionary array
    * o - dictionary object
    * sf - dictionary default sort function (can be undefined)
    * f - sort method sort function argument (can be undefined)
    */
    function sort(a, o, sf, f) {
        var sf1 = f || sf; // sort function  method used if not undefined
        // if there is a customer sort function, use it
        if (isFunct(sf1)) {
            a.sort(function (e1, e2) { return sf1(e1.value, e2.value); });
        }
        else {
            // sort by key values
            a.sort();
        }
        // reindex - adds O(n) to perf
        reindex(a, o, 0);
        // return sorted values (not entire array)
        // adds O(n) to perf
        return values(a);
    };

    /*
    * forEach iteration of "values"
    *   uses "for" loop to allow exiting iteration when function returns true 
    */
    function forEach(a, f) {
        if (!isFunct(f)) { return; }
        // use for loop to allow exiting early and not iterating all items
        for(var i = 0; i < a.length; i++) {
            if (f(a[i].value, i)) { break; }
        }
    };

    /*
    * forEachR iteration of "values" in reverse order
    *   uses "for" loop to allow exiting iteration when function returns true 
    */
    function forEachR(a, f) {
        if (!isFunct(f)) { return; }
        // use for loop to allow exiting early and not iterating all items
        for (var i = a.length - 1; i > -1; i--) {
            if (f(a[i].value, i)) { break; }
        }
    }

    /*
    * Add a new Key Value Pair, or update the value of an existing key value pair
    */
    function add(key, value, a, o, resort, sf) {
        var k = makeKey(key);
        // Update value if key exists
        if (exists(k, o)) {
            a[o[k]].value = value;
        }
        else {
            // Add a new Key value Pair
            var kvp = newkvp(k, value);
            o[kvp.key] = a.length;
            a.push(kvp);
        }
        // resort if requested
        if (resort) { sort(a, o, sf); }
    };

    /*
    * Removes an existing key value pair and returns the "value" If the key does not exists, returns undefined
    */
    function remove(key, a, o) {
        var k = makeKey(key);
        // return undefined if the key does not exist
        if (!exists(k, o)) { return; }
        // get the array index
        var i = o[k];
        // get the key value pair
        var ret = a[i];
        // remove the array element
        a.splice(i, 1);
        // remove the object property
        delete o[k];
        // reindex the object properties from the remove element to end of the array
        reindex(a, o, i);
        // return the removed value
        return ret.value;
    };

    /*
    * Returns true if key exists in the dictionary.
    * k - Key to check (without the leading "_" character) 
    */
    function keyExists(k, o) {
        return exists(makeKey(k), o);
    };

    /*
    * Returns value assocated with "key". Returns undefined if key not found
    */
    function item(key, a, o) {
        var k = makeKey(key);
        if (exists(k, o)) {
            return a[o[k]].value;
        }
    }

    /*
    * changes index values held by object properties to match the array index location
    * Called after sorting or removing
    */
    function reindex(a, o, i){
        for (var j = i; j < a.length; j++) {
            o[a[j].key] = j;
        }
    }

    /*
    * The "real dictionary"
    */
    function dict() {
        var _a = [];
        var _o = {};
        var _sortF;

        Object.defineProperties(this, {
            "length": { get: function () { return _a.length; }, enumerable: true },
            "keys": { get: function() { return keys(_a); }, enumerable: true },
            "values": { get: function() { return values(_a); }, enumerable: true },
            "keyValuePairs": { get: function() { return kvPs(_a); }, enumerable: true},
            "sortFunction": { get: function() { return _sortF; }, set: function(funct) { _sortF = ensureF(funct); }, enumerable: true }
        });

        // Array Methods - Only modification to not pass the actual array to the callback function
        this.map = function(funct) { return map(_a, funct); };
        this.every = function(funct) { return every(_a, funct); };
        this.filter = function(funct) { return filter(_a, funct); };
        this.reverse = function() { reverse(_a, _o); };
        this.shuffle = function () { return shuffle(_a, _o); };
        this.some = function(funct) { return some(_a, funct); };
        this.sort = function(funct) { return sort(_a, _o, _sortF, funct); };

        // Array Methods - Modified aborts when funct returns true.
        this.forEach = function (funct) { forEach(_a, funct) };

        // forEach in reverse order
        this.forEachRev = function (funct) { forEachR(_a, funct) };

        // Dictionary Methods
        this.addOrUpdate = function(key, value, resort) { return add(key, value, _a, _o, resort, _sortF); };
        this.remove = function(key) { return remove(key, _a, _o); };
        this.exists = function(key) { return keyExists(key, _o); };
        this.item = function(key) { return item(key, _a, _o); };
        this.get = function (index) { if (index > -1 && index < _a.length) { return _a[index].value; } } ,
        this.clear = function() { _a = []; _o = {}; };

        return this;
    }


    return this;
}

L'une des épiphanies que j'ai eues en essayant de réconcilier mentalement classe vs objets prototypes est que le prototype est essentiellement une table en v pour les objets créés. En outre les fonctions dans une enceinte peuvent également agir comme les entrées V-table. Au fur et à mesure que le projet progressait, j'ai commencé à utiliser des usines D'objets où un objet de niveau supérieur contenait des fonctions communes pour le type d'objet et incluait un "Ceci.New (args)" méthode qui a été utilisée pour créer les objets réels utilisés dans la solution. C'est le style que j'ai utilisé pour le dictionnaire.

Le noyau du dictionnaire est un tableau, un objet et un objet KeyValuePair. La méthode "addOrUpdate" prend une clé et une valeur et:

  1. crée un KeyValuePair
  2. ajoute une nouvelle propriété à l'objet en utilisant la clé comme nom de propriété et la longueur du tableau comme valeur de propriété
  3. ajoutez le KeyValuePair au tableau, faisant de l'objet une nouvelle propriété valeur de l'index dans le tableau

NOTE: j'ai lu les noms de propriétés d'objet peuvent commencer par" presque n'importe quel " caractère Unicode. Le projet traiterait des données client qui peuvent commencer par "n'importe quel" caractère Unicode. Pour s'assurer que le dictionnaire n'a pas explosé en raison pour un nom de propriété non valide, Je préfixe un trait de soulignement ( _ ) à la clé et supprime ce trait de soulignement lors du retour de clés externes au dictionnaire.

Pour que le dictionnaire soit fonctionnel, le tableau interne et L'objet doivent être synchronisés. Pour ce faire, ni le tableau ni l'objet ne sont exposés à l'extérieur. Je voulais éviter les changements accidentels tels que ceux qui peuvent se produire lorsqu'un test" If " n'a qu'un seul signe égal et que la valeur left have est définie par erreur.

If(dict.KeyObj[“SomeKey”] = “oops”) { alert(“good luck tracing this down:-)”); }

Ce erreur typique avec le dictionnaire peut être très difficile à traquer lorsque les bugs (les symptômes) commencent à apparaître dans le calcul, l'affichage, etc. Par conséquent, la propriété "this" n'aurait pas accès à l'une ou l'autre. Ce protectionnisme est l'une des raisons pour lesquelles je n'ai pas creusé plus dans les prototypes. Il m'avait traversé l'esprit d'utiliser un objet interne avec le tableau et L'objet exposés et de passer cet objet interne lors de l'utilisation des méthodes" call "ou" apply " et je peux regarder cela plus tard car je ne suis toujours pas sûr que je n'aurait pas à exposer cet objet interne qui irait à l'encontre du but de protéger le tableau et L'objet de base.

J'ai corrigé Certaines des erreurs newb que j'ai faites avec le premier objet dictionnaire que j'ai créé.

  • la fonction" Dict () " contient la plupart du code de travail pour chaque dictionnaire de l'objet. Les critères que j'ai utilisés pour déterminer si un fonction fermée devrait être utilisé par rapport à la fonctionnalité dans le réel dictionnaire de l'objet:
    • Plus d'une ligne de code
    • utilisé par d'autres fonctions incluses
    • peut être sujet à changement provoquant la croissance que je découvre des bugs / problèmes
  • utilisé la méthode de tableau et les noms de propriétés où cela avait du sens. Venir de C# j'ai fait des choses qui ont rendu mon dictionnaire moins utilisable comme utilisation "Le comte" au lieu de "longueur" ou "ForEach" au lieu de "forEach". Par en utilisant des noms de tableau, le dictionnaire peut maintenant être utilisé comme un tableau dans la plupart des cas. Malheureusement, je n'ai pas pu trouver un moyen de créer un support accesseur (par exemple val = dict [key]) et cela peut être une bonne chose de toute façon. En y réfléchissant j'ai eu du mal à être sûr que des choses comme val = dict[12] a fonctionné correctement. Le nombre 12 aurait facilement pu être utilisé comme clé donc je ne pouvais pas penser à un bon moyen de connaître le "l'intention" d'un tel appel.
  • complètement fermé le traitement du préfixe de soulignement. Dans le projet, j'ai été en travaillant, j'ai eu ceci étalé et répété dans divers modèles de données objet. Il était laid!
7
répondu Dan Ricker 2013-11-19 20:55:02

Dans JS, {"index": anyValue} est juste un dictionnaire. Vous pouvez également vous référer à la définition de JSON (http://www.json.org/)

6
répondu Allen Hsu 2011-04-08 12:14:00

L'implémentation la plus proche que j'ai utilisée pour un dictionnaire. net en Javascript est un objet de hachage (voir Lien: http://www.mojavelinux.com/articles/javascript_hashes.html ). il implémente un tableau sous le capot et a des méthodes nommées de la même manière que celles d'un dictionnaire.Net.

2
répondu CarneyCode 2011-04-27 21:55:11

Utiliser un objet comme d'autres personnes écrivent. Si vous stockez autre chose que des chaînes en tant que clé, il suffit de les jsonize. Voir cet article de blog pour des considérations de performance de différentes implémentations de dictionnaire en javascript.

1
répondu Anders Rune Jensen 2012-05-31 19:24:00

ECMAScript 6 (alias la spécification JavaScript 2015), spécifie une interface de dictionnaire, nommée Map . Il prend en charge les clés arbitraires de tout type, a une propriété size en lecture seule, n'est pas encombré de prototypes liés à des objets comme des objets, et peut être itéré en utilisant la nouvelle construction for...of... ou Map.forEach. Vérifiez la documentation sur le MDN ici, et la table de compatibilité du navigateur ici.

1
répondu Hugo Wood 2014-08-19 09:00:55
var nDictionary = Object.create(null);

function setDictionary(index, value) {
    nDictionary[index] = value;
}

function getDictionary(index) {
    return nDictionary[index];
}

setDictionary(81403, "test 1");
setDictionary(81404, "test 2");
setDictionary(81405, "test 3");
setDictionary(81406, "test 4");
setDictionary(81407, "test 5");

alert(getDictionary(81403));
1
répondu Jason Williams 2014-10-27 20:34:57

J'ai cette implémentation en cours d'exécution. La première addition d'une paire de valeurs clés en fait un type de clé sûr. Il fonctionne bien et est indépendant de Map:

Git (est toujours mis à jour)

function Dictionary() {

  this.dictionary = [];  
  this.validateKey = function(key){
    if(typeof key == 'undefined' || key == null){
        return false;
    }
    if(this.dictionary.length){
        if (!this.hasOwnProperty(this.dictionary[0], "key")) {
            return false;
        }
        if(typeof this.dictionary[0].key != typeof key){
            return false;
        }
    }
    return true;
  };
  this.hasOwnProperty = function (obj, prop) {
    var proto = obj.__proto__ || obj.constructor.prototype;
    return (prop in obj) &&
        (!(prop in proto) || proto[prop] !== obj[prop]);
    };
}



Dictionary.prototype = {

   Add: function(key, value) {
     if(!this.validateKey(key)){       
            return false;
     }
     if(!this.ContainsKey(key)){
      this.dictionary.push({ key: key, value: value });
      return true;
     }
     return false;
   },
   Any: function() {
     return this.dictionary.length > 0;
   },
   ContainsKey: function(key) {
     if(!this.validateKey(key)){       
            return false;
     }
      for (var i = 0; i < this.dictionary.length; i++) {
         var keyValuePair = this.dictionary[i];
         if (typeof keyValuePair != "undefined" && keyValuePair != null) {
            if (this.hasOwnProperty(keyValuePair, "key")) {
               if (keyValuePair.key == key) {
                  return true;
               }
            }
         }
      }
      return false;
   },
   ContainsValue: function(value) {
      for (var i = 0; i < this.dictionary.length; i++) {
         var keyValuePair = this.dictionary[i];
         if(typeof keyValuePair != "undefined" && keyValuePair != null){
                if (this.hasOwnProperty(keyValuePair, "value")) {
              if(value == null && keyValuePair.value == null){
                return true;
              }
              if ((value != null && keyValuePair.value == null) ||
                    (value == null && keyValuePair.value != null)) {
                  continue;
              }
              // compare objects content over json.
              if(JSON.stringify(value) === JSON.stringify(keyValuePair.value)){
                return true;
              }
            }
         }
      }
      return false;
   },
   Count: function() {
     return this.dictionary.length;
   },
   GetValue: function(key){
     if(!this.validateKey(key)){       
            return null;
     }
        for (var i = 0; i < this.dictionary.length; i++) {
         var keyValuePair = this.dictionary[i];
         if (typeof keyValuePair != "undefined" && keyValuePair != null) {
            if (this.hasOwnProperty(keyValuePair, "key")) {
               if (keyValuePair.key == key) {
                  return keyValuePair.value;
               }
            }
         }
      }
      return null;
   },
   Keys: function(){
    var keys = [];
    for (var i = 0; i < this.dictionary.length; i++) {
      var keyValuePair = this.dictionary[i];
      if (typeof keyValuePair != "undefined" && keyValuePair != null) {
        if (this.hasOwnProperty(keyValuePair, "key")) {
          keys.push(keyValuePair.key);
        }
      }
    }
     return keys;
   },
   Remove: function(key){
    if(!this.validateKey(key)){       
            return;
    }
    for (var i = 0; i < this.dictionary.length; i++) {
         var keyValuePair = this.dictionary[i];
         if (typeof keyValuePair != "undefined" && keyValuePair != null) {
            if (this.hasOwnProperty(keyValuePair, "key")) {
               if (keyValuePair.key == key) {
                  this.dictionary.splice(i, 1);
                  return;                  
               }
            }
         }
      }
   },
   Values: function(){
    var values = [];
    for (var i = 0; i < this.dictionary.length; i++) {
      var keyValuePair = this.dictionary[i];
      if (typeof keyValuePair != "undefined" && keyValuePair != null) {
        if (this.hasOwnProperty(keyValuePair, "value")) {
          values.push(keyValuePair.value);
        }
      }
    }
     return values;
   },
};

Voici comment vous l'utilisez:

var dic = new Dictionary();

var success = dic.Add("test", 5);
success = dic.Add("test1", 4);
success = dic.Add("test2", 8);
success = dic.Add(3, 8);
var containsKey = dic.ContainsKey("test2");
containsKey = dic.ContainsKey(3);

var containsValue = dic.ContainsValue(8);

var value = dic.GetValue("test1");

var keys = dic.Keys();
var values = dic.Values();

dic.Remove("test1");

var keys = dic.Keys();
var values = dic.Values();
0
répondu Franki1986 2018-01-31 08:35:59