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 WeakMap或Map ：
-
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时间和非弱点（即，如果不使用delete或clear来释放密钥，会导致内存泄漏）。
我的地图实施，源自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 */
