Is there a dictionary implementation in JavaScript?
How can I implement an array with an indexer in JavaScript? Is there something like a dictionary in .Net?开发者_开发百科
Technically not, but you can use a regular JavaScript object like a dictionary:
var a = {"a":"wohoo", 2:"hello2", "d":"hello"};
alert(a["a"]);
alert(a[2]);
alert(a["d"]);
John Resig (author of jQuery) posted recently on dictionary lookups in javascript.
His solution is to assign the dictionary values as properties of an object. Code pasted verbatim from above article:
// 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();
}
}
In my last project, I was tasked with creating a browser client application that would read 10 of thousands of rows of data, then group and aggregate the data for display in grids and for charting. The target technologies were HTML 5, CSS 3 and EMCS 5.(modern browser in Jun 2013). Because older browser compatibility was not a concern the external libraries were limited to D3 (no JQuery).
I needed to build a data model. I had built one before in C# and relied on custom dictionary objects to quickly access the data, groups, and aggregates. I had not worked in JavaScript in years so I started searching for a dictionary. I found JavaScript still did not have a true native dictionary. I found a few sample implementations but nothing that really met my expectation. So I built one.
As I mentioned, I had not worked in JavaScript for years. The advancements (or maybe just the web availability of information) were quite impressive. All my previous work was with class based languages so the prototype base language took some time to get used to (and I still have a long way to go).
This project, like most, was due before it started so I learned as I went making many of the newb mistakes that would be expected when transitioning from a class based to a prototype based language. The dictionary created was functional but after a time, I realized some improvements I could make by making it less newbish. The project ran out of funding before I had time to rework the dictionary. Oh, and my position lost funding at the same time (amazing how that can happen). So I decide to recreate the dictionary using what I had learned and determine if the dictionary was actually a performance improvement over an array.
/*
* 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;
}
One of the epiphanies I had while trying to mentally reconcile class vs. prototype objects is that the prototype is basically a v-table for the created objects. Additionally functions in an enclosure can also act like v-table entries. As the project progressed, I started using Object Factories where a top level object contained common functions for the object type and included a “this.New(args)” method that was used to create the actual objects used in the solution. This is the style I used for the dictionary.
The core of the dictionary is an Array, an Object and a KeyValuePair object. The “addOrUpdate” method takes a key and a value and:
- Creates a KeyValuePair
- Adds a new property to the object using the key as the property name and the array length as the property value
- Add the KeyValuePair to the Array, making the object new property value the index in the array
NOTE: I read the object property names can start with “almost any” Unicode character. The project would be dealing with customer data which can start with “any” Unicode character. To ensure the dictionary did not blowup due to an invalid property name, I prefix an underscore (_) to the key and strip off that underscore when returning keys external to the dictionary.
For the dictionary to be functional, the internal Array and Object must be kept in sync. To ensure this neither the Array nor the Object are exposed externally. I wanted to avoid accidental changes such as those that can happen when a “If” test has only one equal sign and the left have value is set by mistake.
If(dict.KeyObj[“SomeKey”] = “oops”) { alert(“good luck tracing this down:-)”); }
This typical error with the dictionary might be very hard to track down when bugs (the symptoms) start showing up in calculation, display, etc. Consequently the “this” property would not have access to either one. This protectionism is one of the reasons I did not dig more into prototypes. It had crossed my mind to use an internal object with the Array and Object exposed and pass that internal object when using the “call” or “apply” methods and I may look at that later as I’m still not sure I wouldn’t have to expose that internal object which would defeat the purpose of protecting the core Array and Object.
I fixed some of the newb mistakes I made with the first dictionary object I created.
- The "Dict()" function contains most of the working code for each
dictionary object. The criteria I used to determine whether an
enclosed function should be used vs. functionality in the actual
dictionary object:
- More than one line of code
- Used by other enclosed functions
- May be subject to change causing growth as I discover bugs/issues
- Used Array method and property names where it made sense. Coming from C# I did things that made my dictionary less usable as using "Count" instead of "length" or "ForEach" instead of "forEach". By using Array names, the dictionary can now be use as an Array in most cases. Unfortunately I was not able to find a way to create a bracket accessor (e.g. val = dict[key]) and that may be a good thing anyway. When thinking about it I had difficulty being sure that things like val = dict[12] worked correctly. The number 12 could easily have been used as a key so I could not think of a good way of knowing the "intention" of such a call.
- Fully enclosed the underscore prefix handling. In the project I was working, I had this spread out and repeated in various data model objects. It was ugly!
In JS, {"index":anyValue} is just a dictionary. Your can also refer to definition of JSON (http://www.json.org/)
ECMAScript 6 (aka the 2015 JavaScript spec), specifies a dictionary interface, named Map. It supports arbitrary keys of any type, has a read-only size property, is not cluttered with prototypes related stuff like objects, and can be iterated over using the new for...of... construct or Map.forEach. Check the documentation on the MDN here, and the browser compatibility table here.
The nearest implementation that I have used to a .Net dictionary in Javascript is a hash object (see link: http://www.mojavelinux.com/articles/javascript_hashes.html). It implements an array under the hood and has similarly named methods to those of a .Net dictionary.
Use an object as other people write. If you are storing something other than strings as key then just jsonize them. See this blog post for performance considurations of different dictionary implementations in javascript.
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));
I have this implementation running. The first adding of key value pair makes it kind of key type safe. It works fine and is independent of Map:
Git (is always updated)
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;
},
};
This is how you use it:
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();
加载中,请稍侯......
精彩评论