正如在这个答案的更新3中所表明的那样,这种表示法:
var hash = {};
hash[X]
实际上并不散列对象X; 它实际上只是转换X为一个字符串(通过.toString()它是一个对象,或者是各种基本类型的一些其他内置转换),然后在" hash"中查找该字符串,而不对其进行散列.也不检查对象相等性 - 如果两个不同的对象具有相同的字符串转换,它们将仅相互覆盖.
鉴于此 - 在JavaScript中是否有任何有效的哈希映射实现？(例如,第二个Google结果javascript hashmap产生一个实现,对于任何操作都是O(n).各种其他结果忽略了具有等效字符串表示的不同对象相互覆盖的事实.
为什么不自己手动散列对象,并使用生成的字符串作为常规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,并尝试简单轻量级,所以这种功能解决方案简单快捷.
关键功能可以像选择对象的正确属性一样简单,例如,键或一组键,它们已经是唯一的,键的组合,它们是唯一的,或者像使用某些加密哈希一样复杂在DojoX编码或DojoX UUID中.虽然后面的解决方案可能会产生独特的密钥,但我个人试图不惜一切代价避免它们,特别是,如果我知道是什么让我的对象独特.
2014年更新: 2008年回答这个简单的解决方案仍需要更多解释.让我以问答形式澄清这个想法.
您的解决方案没有真正的哈希值.它在哪里？？？
JavaScript是一种高级语言.它的基本原语(Object)包含一个用于保存属性的哈希表.此哈希表通常以低级语言编写以提高效率.使用带有字符串键的简单对象,我们使用有效实现的哈希表而不需要我们的努力.
你怎么知道他们使用哈希？
有三种主要方法可以保存按键可以寻址的对象集合:
无序.在这种情况下,要通过其键检索对象,我们必须在找到它时检查所有键.平均而言,它将进行n/2次比较.
有序.
示例#1:排序数组 - 执行二进制搜索我们将在~log2(n)平均比较之后找到我们的密钥.好多了.
示例#2:一棵树.再次,这将是~log(n)次尝试.
哈希表.平均而言,它需要一个恒定的时间.比较:O(n)与O(log n)对比O(1).繁荣.
显然,JavaScript对象以某种形式使用哈希表来处理一般情况.
浏览器供应商真的使用哈希表???
真.
Chrome/node.js/V8: JSObject.查找 NameDictionary和 NameDictionaryShape以及objects.cc 和objects-inl.h中的相关详细信息.
火狐/ 壁虎: JSObject, NativeObject和 PlainObject与相关细节 jsobj.cpp和 VM/NativeObject.cpp.
他们处理碰撞了吗？
是.往上看.如果您发现不相等的字符串发生冲突,请不要犹豫,向供应商提交错误.
那么你的想法是什么？
如果要散列对象,请查找使其唯一的内容并将其用作键.不要尝试计算实际哈希值或模拟哈希表 - 它已经被底层JavaScript对象有效处理.
将此密钥与JavaScript一起使用Object可利用其内置哈希表,同时避免使用默认属性进行可能的冲突.
开始的示例:
如果您的对象包含唯一的用户名 - 请将其用作密钥.
如果它包含唯一的客户编号 - 将其用作密钥.
如果它包括政府颁发的唯一号码(如SSN或护照号码),并且您的系统不允许重复 - 请将其用作密钥.
如果字段组合是唯一的 - 将其用作键.
州名缩写+驾驶执照号码是一个很好的关键.
国家缩写+护照号码也是一个很好的关键.
字段或整个对象上的某些函数可以返回唯一值 - 将其用作键.
我使用了您的建议并使用用户名缓存了所有对象.但有些聪明人被命名为"toString",这是一个内置属性!我现在应该怎么做？
显然,如果生成的密钥完全由拉丁字符组成,甚至可能是远程可能的,那么你应该对它做些什么.例如,在开头或结尾添加您喜欢的任何非拉丁语Unicode字符,以与默认属性取消冲突:"#toString","#MarySmith".如果使用复合键,则使用某种非拉丁分隔符分隔关键组件:"名称,城市,州".
一般来说,这是我们必须具有创造性的地方,并选择具有给定限制的最简单的键(唯一性,与默认属性的潜在冲突).
注意:唯一键不会因定义而发生冲突,而潜在的哈希冲突将由底层处理Object.
你为什么不喜欢工业解决方案？
恕我直言,最好的代码根本就没有代码:它没有错误,不需要维护,易于理解,并且可以即时执行.我看到的所有"JavaScript中的哈希表"都是> 100行代码,涉及多个对象.比较它:dict[key] = value.
另一点:是否有可能击败用低级语言编写的原始对象的性能,使用JavaScript和完全相同的原始对象来实现已经实现的内容？
我仍然想要没有任何键哈希我的对象!
我们很幸运:ECMAScript 6(计划于2015年中期发布,在此之后提供或需要1到2年才能广泛使用)定义 地图和 设置.
从定义来看,他们可以使用对象的地址作为键,这使得对象在没有人工键的情况下立即变得明显.OTOH,两个不同但相同的对象将被映射为不同的.
MDN的比较细分:
对象类似于Maps,它们都允许您将键设置为值,检索这些值,删除键以及检测某些键是否存储在键中.正因为如此(并且因为没有内置替代品),所以对象在历史上被用作地图; 但是,在某些情况下,使用Map更为重要:
Object的键是字符串和符号,而它们可以是Map的任何值,包括函数,对象和任何基元.
Map中的键是按顺序排列的,而添加到对象的键则不是.因此,当迭代它时,Map对象按插入顺序返回键.
您可以使用size属性轻松获取Map的大小,而Object中的属性数必须手动确定.
Map是可迭代的,因此可以直接迭代,而迭代Object需要以某种方式获取其键并迭代它们.
一个对象有一个原型,所以如果你不小心,地图中的默认键可能会与你的键发生碰撞.从ES5开始,这可以通过使用map = Object.create(null)来绕过,但很少这样做.
在涉及频繁添加和删除密钥对的情况下,Map可能表现更好.
JavaScript没有内置的通用映射类型(有时称为关联数组或字典),它允许通过任意键访问任意值.JavaScript的基本数据结构是对象,一种特殊类型的映射,它只接受字符串作为键,并具有特殊的语义,如原型继承,getter和setter以及一些进一步的voodoo.
当使用对象作为映射时,您必须记住密钥将被转换为字符串值via toString(),这将导致映射5和'5'相同的值以及所有不会将toString()方法覆盖到索引值的对象'[object Object]'.如果不检查,您也可能会不自觉地访问其继承的属性hasOwnProperty().
JavaScript的内置数组类型没有任何帮助:JavaScript数组不是关联数组,而是具有更多特殊属性的对象.如果您想知道为什么它们不能用作地图,请查看此处.
尤金的解决方案Eugene Lazutkin已经描述了使用自定义散列函数生成唯一字符串的基本思想,该字符串可用于查找关联值作为字典对象的属性.这很可能是最快的解决方案,因为对象在内部实现为哈希表.
注意:哈希表(有时称为哈希映射)是使用后备数组和通过数字哈希值查找的地图概念的特定实现.运行时环境可能使用其他结构(例如搜索树或跳过列表)来实现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 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进一步考虑
PEZ建议toString()用我们的哈希函数覆盖该方法.这是不可行的,因为它不适用于原始值(更改toString()原语是一个非常糟糕的主意).如果我们想toString()为任意对象返回有意义的值,我们必须修改Object.prototype,有些人(我自己没有包括)认为是verboten.
编辑:我的Map实现的当前版本以及其他JavaScript好东西可以从这里获得.
我知道这个问题很古老,但现在有一些非常好的解决方案可以用于外部库.
collections.js
一成不变
JavaScript也提供了它的语言Map.
地图
这是一种使用类似于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'] ); // fives the value of map_value_1 ...... etc .....
根据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"
您可以使用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的例子是获得散列的唯一方法,散列适用于您从实际散列中获得的任何速度.
更新:
根据Eugene的回答,另一种方法是以某种方式将唯一ID附加到所有对象.我最喜欢的方法之一是采用从Object超类继承的一个内置方法,将其替换为自定义函数passthrough并将属性附加到该函数对象.如果您要重写我的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()方法.
我已经实现了一个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 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 (i.e. there is no method giving you a list of the keys).
京公网安备 11010802040832号 | 京ICP备19059560号-6 