小开

最佳答案

自己手动散列对象，并将结果字符串用作常规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控制索引，而不需要大量的内存分配和溢出处理。

当然，如果你真的想要“工业级的解决方案”，你可以通过键函数来参数化一个类，并使用容器的所有必要API，但是……我们使用JavaScript，并试图做到简单和轻量级，所以这个功能性的解决方案简单而快速。

key函数可以像选择对象的正确属性一样简单，例如，一个密钥或一组密钥，它们已经是唯一的，或者是密钥的组合，它们在一起是唯一的，或者像使用一些加密哈希一样复杂，比如DojoX编码或DojoX UUID。虽然后一种解决方案可能会产生唯一的键，但就我个人而言，我会尽量避免使用它们，特别是如果我知道是什么使我的对象唯一的话。

早在2008年，这个简单的解决方案仍然需要更多的解释。让我用问答形式来阐明这个观点。

你的解决方案并没有真正的哈希值。它在哪里??

JavaScript是一种高级语言。它的基本元素(对象)包括一个哈希表来保存属性。为了提高效率，这个哈希表通常是用低级语言编写的。使用一个简单的对象与字符串键，我们使用一个有效实现的哈希表，而不需要任何努力。

你怎么知道他们用了哈希?

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

无序。在这种情况下，通过键来检索对象，我们必须遍历所有在我们找到它时停止的键。平均需要n/2次比较。

例子#1:一个排序的数组——做一个二分搜索，我们将在平均~log2(n)比较后找到我们的键。好多了。
例2:一棵树。还是要尝试~log(n)次。

哈希表。平均来说，它需要常数时间。比较:O(n) vs O(log n) vs O(1)。繁荣。

显然，JavaScript对象以某种形式使用哈希表来处理一般情况。

浏览器厂商真的使用哈希表吗??

真的。

vm / NativeObject.cpp

他们处理碰撞吗?

是的。见上图。如果你发现不相等的字符串发生碰撞，请毫不犹豫地向供应商提交错误。

你的想法是什么?

如果您想对一个对象进行哈希，请找到使它唯一的原因并将其用作键。不要尝试计算真正的哈希或模拟哈希表——底层JavaScript对象已经有效地处理了。

将此键与JavaScript的Object一起使用，可以利用其内置哈希表，同时避免与默认属性发生冲突。

下面的例子让你开始学习:

如果您的对象包含一个唯一的用户名-使用它作为一个键。
如果它包含唯一的客户号码-将其用作密钥。
- 如果它包含唯一的政府颁发的号码，如US SSNs，或护照号码，而你的系统不允许重复-使用它作为密钥。
如果字段的组合是唯一的-使用它作为键。
- 美国州缩写+驾照号码是很好的钥匙。
- 国家缩写+护照号码也是一个很好的关键字。
字段或整个对象上的一些函数可以返回唯一的值—将其用作键。

我采用了您的建议，并使用用户名缓存所有对象。但是有些聪明的家伙被命名为“tostring”，这是一个内置属性!我现在该怎么办?

显然，如果产生的键完全由拉丁字符组成的可能性很小，那么您应该采取一些措施。例如，在开头或结尾添加任何您喜欢的非拉丁Unicode字符以消除与默认属性的冲突:"#toString"， "#MarySmith"如果使用复合键，则使用某种非拉丁分隔符分隔键组件:"name,city,state"

一般来说，这是我们必须发挥创意的地方，在给定的限制(唯一性，与默认属性的潜在冲突)下选择最简单的键。

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

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

恕我直言，最好的代码根本就是没有代码:它没有错误，不需要维护，易于理解，并且可以立即执行。所有“javascript散列表”;我看到了100行代码，涉及多个对象。与:dict[key] = value进行比较。

另一点:使用JavaScript和相同的原始对象来实现已经实现的内容，是否有可能击败用低级语言编写的原始对象的性能?

我仍然想在没有任何键的情况下散列我的对象!

我们很幸运:ECMAScript 6(2015年6月发布)定义了地图和集。

根据定义判断，它们可以使用对象的地址作为键，这使得对象在没有人工键的情况下立即区别开来。OTOH，两个不同但完全相同的对象，将被映射为不同的对象。

中数的比较分解:

对象与映射相似，都允许你设置值的键，检索这些值，删除键，并检测是否存在某些内容存储在一个键上。正因为如此(也因为没有内置的 )，对象在历史上被用作地图;然而, 有一些重要的区别，使得使用Map更可取某些情况下:< / p >

对象的键是字符串和符号，而Map的键可以是任何值，包括函数、对象和任何原语。

Map中的键是有序的，而添加到object中的键不是有序的。因此，当对其进行迭代时，Map对象将按顺序返回键李插入。< / >
您可以使用size属性轻松地获取Map的大小，而对象中的属性数量必须手动确定。
Map是可迭代对象，因此可以直接迭代，而遍历Object则需要以某种方式获取它的键然后对它们进行迭代一个对象有一个原型，所以在映射中有默认键，如果你不小心，它们可能会与你的键发生冲突。从ES5开始就可以了可以通过使用map = Object.create(null)来绕过，但这种情况很少李做。< / >
在涉及频繁添加和删除密钥对的场景中，Map可能执行得更好。

小开

你必须在某些内部状态下存储对象/值对:

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超类继承的内置方法之一，将其替换为自定义函数传递，并将属性附加到该函数对象。如果你重写我的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];
}

这个版本看起来只是稍微快一点，但在理论上，对于大数据集来说，它会快得多。

小开

问题描述

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

当使用对象作为映射时，你必须记住键将通过toString()转换为字符串值，这将导致将5和'5'映射到相同的值，并将所有未覆盖toString()方法的对象映射到由'[object Object]'索引的值。如果你不勾选hasOwnProperty()，你也可能会不由自主地访问它继承的属性。

JavaScript内置的数组类型一点帮助都没有:JavaScript数组不是关联数组，而只是具有一些特殊属性的对象。如果你想知道为什么它们不能被用作地图，看这里。

尤金的解决方案

尤金·拉祖特金已经描述过了使用自定义哈希函数生成唯一字符串的基本思想，该字符串可用于作为字典对象的属性查找相关值。这很可能是最快的解决方案，因为对象在内部实现为哈希表。

注意:哈希表(有时称为散列映射)是映射概念的一个特殊实现，它使用一个支持数组，并通过数值哈希值进行查找。运行时环境可能使用其他结构(如搜索树或跳跃表)来实现JavaScript对象，但由于对象是基本数据结构，因此应该充分优化它们。

为了获得任意对象的唯一哈希值，一种可能是使用全局计数器并在对象本身中缓存哈希值(例如，在名为__hash的属性中)。

这样做的哈希函数是并且对基本值和对象都有效:

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


hash.current = 0;

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

我的`Map`实现

下面的实现将额外地将键-值对存储在双链表中，以便对键和值进行快速迭代。为了提供你自己的哈希函数，你可以在创建后覆盖实例的hash()方法。

// Linking the key-value-pairs is optional.
// If no argument is provided, linkItems === undefined, i.e. !== false
// --> linking will be enabled
function Map(linkItems) {
this.current = undefined;
this.size = 0;


if(linkItems === false)
this.disableLinking();
}


Map.noop = function() {
return this;
};


Map.illegal = function() {
throw new Error("illegal operation for maps without linking");
};


// Map initialisation from an existing object
// doesn't add inherited properties if not explicitly instructed to:
// omitting foreignKeys means foreignKeys === undefined, i.e. == false
// --> inherited properties won't be added
Map.from = function(obj, foreignKeys) {
var map = new Map;


for(var prop in obj) {
if(foreignKeys || obj.hasOwnProperty(prop))
map.put(prop, obj[prop]);
}


return map;
};


Map.prototype.disableLinking = function() {
this.link = Map.noop;
this.unlink = Map.noop;
this.disableLinking = Map.noop;
this.next = Map.illegal;
this.key = Map.illegal;
this.value = Map.illegal;
this.removeAll = Map.illegal;


return this;
};


// Overwrite in Map instance if necessary
Map.prototype.hash = function(value) {
return (typeof value) + ' ' + (value instanceof Object ?
(value.__hash || (value.__hash = ++arguments.callee.current)) :
value.toString());
};


Map.prototype.hash.current = 0;


// --- Mapping functions


Map.prototype.get = function(key) {
var item = this[this.hash(key)];
return item === undefined ? undefined : item.value;
};


Map.prototype.put = function(key, value) {
var hash = this.hash(key);


if(this[hash] === undefined) {
var item = { key : key, value : value };
this[hash] = item;


this.link(item);
++this.size;
}
else this[hash].value = value;


return this;
};


Map.prototype.remove = function(key) {
var hash = this.hash(key);
var item = this[hash];


if(item !== undefined) {
--this.size;
this.unlink(item);


delete this[hash];
}


return this;
};


// Only works if linked
Map.prototype.removeAll = function() {
while(this.size)
this.remove(this.key());


return this;
};


// --- Linked list helper functions


Map.prototype.link = function(item) {
if(this.size == 0) {
item.prev = item;
item.next = item;
this.current = item;
}
else {
item.prev = this.current.prev;
item.prev.next = item;
item.next = this.current;
this.current.prev = item;
}
};


Map.prototype.unlink = function(item) {
if(this.size == 0)
this.current = undefined;
else {
item.prev.next = item.next;
item.next.prev = item.prev;
if(item === this.current)
this.current = item.next;
}
};


// --- Iterator functions - only work if map is linked


Map.prototype.next = function() {
this.current = this.current.next;
};


Map.prototype.key = function() {
return this.current.key;
};


Map.prototype.value = function() {
return this.current.value;
};

例子

下面的脚本，

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

进一步的考虑

派司建议重写toString()方法，假设使用我们的哈希函数。这是不可行的，因为它不适用于原语值(为原语更改toString()是一个非常的坏主意)。如果我们想要toString()为任意对象返回有意义的值，我们必须修改Object.prototype，有些人(不包括我自己)认为这是禁止的。

我的Map实现的当前版本以及其他JavaScript好东西能从这里得到什么。

小开

JavaScript没有内置的map/hashmap。它应该被称为关联数组。

hash["X"]等于hash.X，但是允许"X"作为字符串变量。换句话说，hash[x]函数上等于eval("hash."+x.toString()).

它更类似于object。属性而不是键值映射。如果你在JavaScript中寻找更好的键/值映射，请使用Map对象.

小开

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

它查找关键对象的hashCode()方法，或者您可以在创建Hashtable对象时提供哈希函数。

小开

我已经实现了一个JavaScript HashMap，它的代码可以从http://github.com/lambder/HashMapJS/tree/master获得

代码如下:

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


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


initialize: function() {
this.backing_hash = {};
this.code = 0;
},
/*
Maps value to key returning previous association
*/
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 association 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")
}

小开

不幸的是，之前的答案都不适合我的情况:不同的键对象可能具有相同的散列代码。因此，我写了一个简单的类似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()方法。

小开

我的'Map'实现，派生自克里斯托弗的例子:

使用示例:

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 an existing object
// doesn't add inherited properties if not explicitly instructed to:
// omitting foreignKeys means foreignKeys === undefined, i.e. == false
// --> inherited properties won't be added
Map.from = function(obj, foreignKeys) {
var map = new Map;
for(var prop in obj) {
if(foreignKeys || obj.hasOwnProperty(prop))
map.put(prop, obj[prop]);
}
return map;
};


Map.prototype.disableLinking = function() {
this.link = Map.noop;
this.unlink = Map.noop;
this.disableLinking = Map.noop;


this.next = Map.illegal;
this.key = Map.illegal;
this.value = Map.illegal;
//    this.removeAll = Map.illegal;




return this;
};


// Overwrite in Map instance if necessary
Map.prototype.hash = function(value) {
return (typeof value) + ' ' + (value instanceof Object ?
(value.__hash || (value.__hash = ++arguments.callee.current)) :
value.toString());
};


Map.prototype.hash.current = 0;


// --- Mapping functions


Map.prototype.get = function(key) {
var item = this[this.hash(key)];
if (item === undefined) {
if (this.storageId) {
try {
var itemStr = localStorage.getItem(this.storageId + key);
if (itemStr && itemStr !== 'undefined') {
item = JSON.parse(itemStr);
this[this.hash(key)] = item;
this.keys.push(key);
++this.size;
}
} catch (e) {
console.log(e);
}
}
}
return item === undefined ? undefined : item.value;
};


Map.prototype.put = function(key, value) {
var hash = this.hash(key);


if(this[hash] === undefined) {
var item = { key : key, value : value };
this[hash] = item;


this.link(item);
++this.size;
}
else this[hash].value = value;
if (this.storageId) {
this.keys.push(key);
try {
localStorage.setItem(this.storageId + key, JSON.stringify(this[hash]));
} catch (e) {
console.log(e);
}
}
return this;
};


Map.prototype.remove = function(key) {
var hash = this.hash(key);
var item = this[hash];
if(item !== undefined) {
--this.size;
this.unlink(item);


delete this[hash];
}
if (this.storageId) {
try {
localStorage.setItem(this.storageId + key, undefined);
} catch (e) {
console.log(e);
}
}
return this;
};


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


// --- Linked list helper functions


Map.prototype.link = function(item) {
if (this.storageId) {
return;
}
if(this.size == 0) {
item.prev = item;
item.next = item;
this.current = item;
}
else {
item.prev = this.current.prev;
item.prev.next = item;
item.next = this.current;
this.current.prev = item;
}
};


Map.prototype.unlink = function(item) {
if (this.storageId) {
return;
}
if(this.size == 0)
this.current = undefined;
else {
item.prev.next = item.next;
item.next.prev = item.prev;
if(item === this.current)
this.current = item.next;
}
};


// --- Iterator functions - only work if map is linked


Map.prototype.next = function() {
this.current = this.current.next;
};


Map.prototype.key = function() {
if (this.storageId) {
return undefined;
} else {
return this.current.key;
}
};


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

小开

下面是一种使用类似Java映射的简单而方便的方法:

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

为了得到值:

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


... etc. ...

小开

添加另一个解决方案:HashMap几乎是我从Java移植到JavaScript的第一个类。可以说有很多开销，但是实现几乎100%等于Java的实现，并且包含了所有的接口和子类。

该项目可以在这里找到:https://github.com/Airblader/jsava 我还将附加HashMap类的(当前)源代码，但正如前面所述，它还取决于超类等。所使用的面向对象框架是qooxdoo.

请注意，这段代码已经过时，请参考GitHub项目了解当前的工作。在撰写本文时，还有一个ArrayList实现。

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

小开

这看起来非常稳健解决方案:https://github.com/flesler/hashmap < / p >

它甚至可以很好地用于看起来相同的函数和对象。它使用的唯一hack是向对象添加一个模糊成员来标识它。如果你的程序没有覆盖那个模糊的变量(它类似哈希德)，你就很好了。

小开

在ECMAScript 6中，你可以使用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

但是:

因为引用是弱的，WeakMap键是不可枚举的(也就是说，没有方法给你一个键的列表)。

小开

如果性能不是很关键(例如，键的数量相对较小)，并且你不想用额外的字段(如_hash， _id等)污染你的(或可能不是你的)对象，那么你可以利用Array.prototype.indexOf采用严格相等的事实。下面是一个简单的实现:

var Dict = (function(){
// Internet Explorer 8 and earlier does not have any 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.

与ECMAScript 6 WeakMap相比，它有两个问题:O(n)搜索时间和非弱点(即，如果不使用delete或clear释放键，它将导致内存泄漏)。

小开

你可以使用ECMAScript 6 WeakMap或Map:

< blockquote >
weakmap是键/值映射，其中键是对象。

Map对象是简单的键/值映射。任何值(包括对象和基本值)都可以用作键或值。

< / p > < /引用>

请注意，这两种方法都不被广泛支持，但你可以使用ECMAScript 6 Shim(需要原生ECMAScript 5或ECMAScript 5 Shim)来支持Map，但不能使用WeakMap (明白为什么)。

小开

这是我的另一个地图实现。使用randomizer， 'generics'和'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
*/

小开

现在有一些非常好的外部库解决方案:

collections.js .js
< a href = " https://facebook.github。io / immutable-js noreferrer“rel = > Immutable.js < / >

JavaScript也有它的语言提供的Map。

Map

小开

根据ECMAScript 2015 (ES6)，标准JavaScript有一个Map实现。关于它的更多信息可以在在这里中找到。

基本用法:

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等价

问题描述

尤金的解决方案

我的Map实现

例子

进一步的考虑

我的`Map`实现