JavaScript哈希表等效

正如在这个答案的更新3中所表明的那样:

var hash = {}; hash[X] 

实际上并不散列对象X ; 它实际上只是将X转换为一个string(如果它是一个对象,则通过.toString()或其他一些内置的对各种基本types的转换),然后在“ hash ”中查找该string,而不用散列。 对象相等也不被检查 – 如果两个不同的对象具有相同的string转换,它们将只是相互覆盖。

鉴于此 – 在JavaScript中has hasps有效的实现吗? (例如,对于任何操作, javascript hashmap的第二个Google结果都会产生一个O(n)的实现。其他各种结果忽略了具有等效string表示的不同对象相互覆盖的事实。

为什么不手动散列对象,并将结果string用作常规JavaScript字典的键? 毕竟,你是在最好的位置知道什么使你的对象独特。 我就是做这个的。

例:

 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; 

通过这种方式,您可以控制由JavaScript完成的索引,而不会导致内存分配和溢出处理。

当然,如果你真的想要“工业级的解决scheme”,你可以build立一个类的参数化的关键function,并与容器的所有必要的API,但是…我们使用JavaScript,并试图简单和轻量级,所以这个function解决scheme简单快捷。

关键function可以像select对象的正确属性一样简单,例如,已经唯一的关键字或关键字集合,关键字的组合,这些关键字的组合是唯一的,或者像使用一些密码散列一样复杂在DojoX编码或DojoX UUID中 。 虽然后面的解决scheme可能会产生独特的钥匙,但我个人尽量避免使用这些钥匙,特别是如果我知道是什么让我的物品变得独特。

2014年更新:在2008年回答这个简单的解决scheme仍然需要更多的解释。 让我以问答forms澄清这个想法。

您的解决scheme没有真正的散列。 它在哪里???

JavaScript是一种高级语言。 它的基本原始( 对象 )包括一个哈希表来保持属性。 这个哈希表通常是用低级语言编写的,以提高效率。 使用带有string键的简单对象,我们使用一个高效实现的散列表,而我们没有努力。

你怎么知道他们使用散列?

有三种主要的方法来保持对一个键的对象集合:

  • 无序。 在这种情况下,通过键来检索一个对象,当我们find它时,我们必须检查所有的键。 平均而言,将需要n / 2比较。
  • 有序。
    • 示例#1:一个sorting数组 – 进行二分search,我们将在〜log2(n)比较平均之后find我们的密钥。 好多了。
    • 示例#2:一棵树。 再次,这将是〜log(n)的尝试。
  • 哈希表。 平均来说,它需要一个固定的时间。 比较:O(n)与O(log n)对O(1)。 繁荣。

很明显,JavaScript对象以某种forms使用散列表来处理一般情况。

浏览器供应商真的使用散列表吗?

真。

  • Chrome / node.js / V8 : JSObject 。 在objects.cc和objects-inl.h中查找NameDictionary和NameDictionaryShape的相关细节。
  • Firefox / Gecko : JSObject , NativeObject和PlainObject ,在jsobj.cpp和vm / NativeObject.cpp中有相关的细节。

他们处理碰撞?

是。 往上看。 如果您在不相等的string上发现了冲突,请立即向供应商提交错误报告。

那么你的想法是什么?

如果你想散列一个对象,找出是什么使它唯一,并将其​​用作关键。 不要尝试计算真正的哈希或模拟哈希表 – 它已经被底层JavaScript对象有效地处理了。

在JavaScript Object使用此键可利用其内置哈希表,同时避免使用默认属性造成可能的冲突。

例子让你开始:

  • 如果你的对象包含一个唯一的用户名 – 用它作为一个键。
  • 如果它包含一个唯一的客户号码 – 将其用作关键字。
    • 如果它包含政府颁发的唯一号码,例如SSN或护照号码,而且您的系统不允许重复,则将其用作关键字。
  • 如果字段的组合是唯一的 – 将其用作关键字。
    • 国家简称+驾驶执照号码是一个很好的关键。
    • 国家简称+护照号码也是一个很好的关键。
  • 字段上的某些函数或整个对象可以返回一个唯一的值 – 将其用作关键字。

我用你的build议,并使用用户名caching所有的对象。 但有些聪明的人被命名为“toString”,这是一个内置的财产! 我现在应该怎么做?

显然,如果所产生的密钥完全由拉丁字符组成,那么你应该做一些相关的事情。 例如,在开始或结尾添加任何您喜欢的非拉丁Unicode字符,以便与默认属性“#toString”,“#MarySmith”进行非冲突。 如果使用复合键,则使用某种非拉丁分隔符(“name,city,state”)分隔关键组件。

一般来说,这是我们必须具有创造性的地方,并select具有一定限制(唯一性,与默认属性的潜在冲突)的最简单的键。

注意:唯一键不会按定义冲突,而潜在的哈希冲突将由底层Object处理。

你为什么不喜欢工业解决scheme?

恕我直言,最好的代码根本没有代码:它没有错误,不需要维护,易于理解,并且即时执行。 我看到的所有“JavaScript中的哈希表”是> 100行的代码,并涉及多个对象。 将其与: dict[key] = value

还有一点:用JavaScript和原始对象来实现已经实现的东西,甚至有可能击败用低级语言编写的原始对象的performance。

我仍然想散列我的对象没有任何键!

我们很幸运:ECMAScript 6(定于2015年中期发布,在此之后的1 – 2年广为stream传)定义了地图和集合 。

通过定义来判断,可以将对象的地址作为关键字,使得对象在没有人工键的情况下立即可见。 OTOH,两个不同但相同的对象,将被映射为不同的。

问题描述

JavaScript没有内置的通用映射types(有时称为关联数组字典 ),它允许通过任意键访问任意值。 JavaScript的基本数据结构是对象 ,一种特殊types的映射,它只接受string作为键,并具有特殊的语义,如原型inheritance,getter和setter以及一些进一步的巫术。

将对象用作映射时,必须记住,通过toString()将键转换为string值,从而将5'5'映射为相同的值,并且所有不覆盖toString()方法转换为由'[object Object]'索引的值。 如果你不检查hasOwnProperty()你也可能不由自主地访问它的inheritance属性。

JavaScript的内置数组types并没有什么帮助:JavaScript数组不是关联数组,而只是具有更多特殊属性的对象。 如果你想知道为什么他们不能用作地图, 看看这里 。

尤金的解决scheme

Eugene Lazutkin已经描述了使用自定义哈希函数生成唯一string的基本思想,该string可以用来查找关联值作为字典对象的属性。 这很可能是最快的解决scheme,因为对象在内部被实现为哈希表

  • 注:哈希表(有时称为哈希映射 )是使用支持数组和通过数字哈希值查找的映射概念的特定实现。 运行时环境可能使用其他结构(如search树跳过列表 )来实现JavaScript对象,但由于对象是基本的数据结构,因此应该对其进行充分优化。

为了获得任意对象的唯一散列值,一种可能性是使用全局计数器并将散列值caching在对象本身中(例如,在名为__hash的属性中)。

这样做的散列函数适用于原始值和对象:

 function hash(value) { return (typeof value) + ' ' + (value instanceof Object ? (value.__hash || (value.__hash = ++arguments.callee.current)) : value.toString()); } hash.current = 0; 

这个function可以像Eugene所描述的那样使用。 为了方便起见,我们将进一步将其包装在一个Map类中。

我的Map实施

下面的实现将另外将键值对存储在一个双向链表中,以便快速迭代键和值。 要提供自己的散列函数,可以在创build后覆盖实例的hash()方法。

 // linking the key-value-pairs is optional // if no argument is provided, linkItems === undefined, ie !== 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, ie == 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; }; 

以下脚本

 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()); 

生成这个输出:

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

进一步考虑

PEZbuild议覆盖toString()方法,推测是用我们的散列函数。 这是不可行的,因为它不适用于原始值(改变toString()的原语是一个非常糟糕的主意)。 如果我们想要toString()为任意对象返回有意义的值,我们将不得不修改Object.prototype ,这是一些人(我自己不包括在内)认为是verboten


编辑:我的Map实施的当前版本以及其他JavaScript的好东西可以从这里获得 。

我知道这个问题是相当古老的,但是现在有一些非常棒的解决scheme与外部库。

  • collections.js
  • 一成不变

JavaScript也提供了语言提供的Map

  • 地图

这里使用类似于java map的简单方便的方法:

 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 } 

并获得价值:

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

您可以使用ES6 WeakMapMap

  • WeakMaps是键是对象的键/值映射。

  • Map对象是简单的键/值映射。 任何值(对象和原始值)都可以用作键或值。

请注意,这两者都不被广泛支持,但是您可以使用ES6 Shim (需要原生ES5或ES5 Shim )来支持Map ,但不支持WeakMap ( 请参阅原因 )。

你必须存储一些内部对象/值对的状态对

 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]; } } 

并使用它:

 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)); 

当然,这个实现也是沿着O(n)的某个地方。 Eugene上面的例子是得到一个散列的唯一方法,这个散列可以用你希望从一个真正的散列中获得的任何速度工作。

更新:

另一种方法,尤金的回答是以某种方式给所有对象附加一个唯一的ID。 我最喜欢的方法之一是从Object超类inheritance的内置方法之一,将其replace为自定义函数传递并将属性附加到该函数对象。 如果你要重写我的HashMap方法来做到这一点,它会看起来像:

 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]; } 

这个版本似乎只是稍微快一点,但理论上大数据集的速度会更快。

不幸的是,上面的答案都不适合我的情况:不同的密钥对象可能具有相同的哈希码。 因此,我写了一个简单的类似Java的HashMap版本:

 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; } 

注意:关键对象必须“实现”hashCode()和equals()方法。

根据ECMAScript 2015(ES6)标准,JavaScript有一个Map实现。 更多关于哪些可以在这里find

基本用法:

 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" 

我已经实现了一个JavaScript HashMap,其代码可以从http://github.com/lambder/HashMapJS/tree/master

这里是代码:

 /* ===================================================================== @license MIT @author Daniel Kwiecinski <daniel.kwiecinski@lambder.com> @copyright 2009 Daniel Kwiecinski. @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") } 

在ECMA6中,你可以使用WeakMap

例:

 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 

但:

 Because of references being weak, WeakMap keys are not enumerable (ie there is no method giving you a list of the keys). 

试试我的JavaScript哈希表实现: http : //www.timdown.co.uk/jshashtable

它查找关键对象的hashCode()方法,或者在创buildHashtable对象时可以提供散列函数。

这看起来像一个非常强大的解决scheme: https : //github.com/flesler/hashmap 。 对于看起来完全相同的function和对象,它甚至可以很好地工作 唯一的黑客使用是添加一个不起眼的成员到一个对象来识别它。 如果你的程序不覆盖那个模糊的variables(像hashid那样 ),那么你就是金。

如果性能不重要(例如键的数量相对较小),并且您不想用_hash_id等其他字段污染您的(或者可能不是您的)对象,那么您可以利用事实Array.prototype.indexOf采用严格的等式。 这是一个简单的实现:

 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; })(); 

使用示例:

 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. 

与ES6 WeakMap相比,它有两个问题:O(n)search时间和非弱点(即,如果不使用deleteclear来释放密钥,会导致内存泄漏)。

我的地图实施,源自Christoph的例子:

用法示例:

 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, ie == 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; }; 

Javascript does not build-in Map/hashmap. It should be called associative array .

hash["X"] is equals to hash.X , but allow "X" as a string variable. In other words, hash[x] is functionally equals to eval("hash."+x.toString())

It is more similar as object.properties rather then key-value mapping. If you are looking for a better Key/value mapping in Javascript, please use Map object which you can find on the web.

Adding yet another solution: HashMap is pretty much the first class I ported from Java to Javascript. You could say there is a lot of overhead, but the implementation is almost 100% equal to Java's implementation and includes all interfaces and subclasses.

The project can be found here: https://github.com/Airblader/jsava I'll also attach the (current) source code for the HashMap class, but as stated it also depends on the super class etc. The OOP framework used is qooxdoo.

Edit: Please note that this code is already out-dated and refer to the github project for the current work. As of writing this, there is also an ArrayList implementation.

 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(); } } } ) } } ); 

Yet another map implementation by me. With randomizer, 'generics' and 'iterator' =)

 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; } } 

例:

 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 */