Javascript HashTable 使用对象键
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10892322/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Javascript HashTable use Object key
提问by Ilya Gazman
I want to create a hash table that gets my Object as his key without converting it to String.
我想创建一个哈希表，将我的对象作为他的键，而不将其转换为字符串。
Some thing like this:
像这样的事情：
var object1 = new Object();
var object2 = new Object();
var myHash = new HashTable();
myHash.put(object1, "value1");
myHash.put(object2, "value2");
alert(myHash.get(object1), myHash.get(object2)); // I wish that it will print value1 value2
EDIT:See my answerfor full solution
采纳答案by Florian Margaine
Here is a proposal:
这是一个提议：
function HashTable() {
this.hashes = {};
}
HashTable.prototype = {
constructor: HashTable,
put: function( key, value ) {
this.hashes[ JSON.stringify( key ) ] = value;
},
get: function( key ) {
return this.hashes[ JSON.stringify( key ) ];
}
};
The API is exactly as shown in your question.
API 与您的问题中显示的完全相同。
You can't play with the reference in js however (so two empty objects will look like the same to the hashtable), because you have no way to get it. See this answer for more details: How to get javascript object references or reference count?
然而，你不能在 js 中使用引用（所以两个空对象对于哈希表看起来是一样的），因为你没有办法得到它。有关更多详细信息，请参阅此答案：如何获取 javascript 对象引用或引用计数？
Jsfiddle demo: http://jsfiddle.net/HKz3e/
jsfiddle 演示：http: //jsfiddle.net/HKz3e/
However, for the unique side of things, you could play with the original objects, like in this way:
但是，对于事物的独特方面，您可以使用原始对象，如下所示：
function HashTable() {
this.hashes = {},
this.id = 0;
}
HashTable.prototype = {
constructor: HashTable,
put: function( obj, value ) {
obj.id = this.id;
this.hashes[ this.id ] = value;
this.id++;
},
get: function( obj ) {
return this.hashes[ obj.id ];
}
};
Jsfiddle demo: http://jsfiddle.net/HKz3e/2/
jsfiddle 演示：http: //jsfiddle.net/HKz3e/2/
This means that your objects need to have a property named idthat you won't use elsewhere. If you want to have this property as non-enumerable, I suggest you take a look at defineProperty(it's not cross-browser however, even with ES5-Shim, it doesn't work in IE7).
这意味着你的对象需要有一个id你不会在其他地方使用的命名属性。如果您想将此属性设为不可枚举，我建议您查看defineProperty（它不是跨浏览器的，但是即使使用 ES5-Shim，它在 IE7 中也不起作用）。
It also means you are limited on the number of items you can store in this hashtable. Limited to 253, that is.
这也意味着您可以在此哈希表中存储的项目数量受到限制。限制为2 53，即。
And now, the "it's not going to work anywhere" solution: use ES6 WeakMaps. They are done exactly for this purpose: having objects as keys. I suggest you read MDN for more information: https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/WeakMap
现在，“它不会在任何地方工作”的解决方案：使用 ES6 WeakMaps。它们正是为此目的而完成的：将对象作为键。我建议您阅读 MDN 以获取更多信息：https: //developer.mozilla.org/en/JavaScript/Reference/Global_Objects/WeakMap
It slightly differs from your API though (it's setand not put):
虽然它与您的 API 略有不同（它是set和不是put）：
var myMap = new WeakMap(),
object1 = {},
object2 = {};
myMap.set( object1, 'value1' );
myMap.set( object2, 'value2' );
console.log( myMap.get( object1 ) ); // "value1"
console.log( myMap.get( object2 ) ); // "value2"
Jsfiddle demo with a weakmap shim: http://jsfiddle.net/Ralt/HKz3e/9/
带有弱图垫片的 Jsfiddle 演示：http: //jsfiddle.net/Ralt/HKz3e/9/
However, weakmaps are implemented in FF and Chrome (onlyif you enable the "Experimental javascript features" flag in chrome however). There are shims available, like this one: https://gist.github.com/1269991. Use at your own risk.
然而，weakmaps在FF和Chrome执行（仅当您启用“实验性JavaScript功能”，在镀铬标志不过）。有可用的垫片，例如：https: //gist.github.com/1269991。使用风险自负。
You can also use Maps, they may more suit your needs, since you also need to store primitive values (strings) as keys. Doc, Shim.
回答by Peter
Here is a simple Mapimplementation that will work with any type of key, including object references, and it will not mutate the key in any way:
这是一个简单的Map实现，适用于任何类型的键，包括对象引用，并且不会以任何方式改变键：
function Map() {
var keys = [], values = [];
return {
put: function (key, value) {
var index = keys.indexOf(key);
if(index == -1) {
keys.push(key);
values.push(value);
}
else {
values[index] = value;
}
},
get: function (key) {
return values[keys.indexOf(key)];
}
};
}
While this yields the same functionality as a hash table, it's not actually implemented using a hash function since it iterates over arrays and has a worst case performance of O(n). However, for the vast majority of sensible use cases this shouldn't be a problem at all. The indexOffunction is implemented by the JavaScript engine and is highly optimized.
虽然这产生了与哈希表相同的功能，但它实际上并没有使用哈希函数来实现，因为它遍历数组并且具有 O(n) 的最坏情况性能。然而，对于绝大多数合理的用例来说，这根本不应该是一个问题。该indexOf功能由 JavaScript 引擎实现，并经过高度优化。
回答by Ilya Gazman
I took @Florian Margaine's suggestion to higher level and came up with this:
我将@Florian Margaine 的建议提升到了更高的水平，并提出了以下建议：
function HashTable(){
var hash = new Object();
this.put = function(key, value){
if(typeof key === "string"){
hash[key] = value;
}
else{
if(key._hashtableUniqueId == undefined){
key._hashtableUniqueId = UniqueId.prototype.generateId();
}
hash[key._hashtableUniqueId] = value;
}
};
this.get = function(key){
if(typeof key === "string"){
return hash[key];
}
if(key._hashtableUniqueId == undefined){
return undefined;
}
return hash[key._hashtableUniqueId];
};
}
function UniqueId(){
}
UniqueId.prototype._id = 0;
UniqueId.prototype.generateId = function(){
return (++UniqueId.prototype._id).toString();
};
Usage
用法
var map = new HashTable();
var object1 = new Object();
map.put(object1, "Cocakola");
alert(map.get(object1)); // Cocakola
//Overriding
map.put(object1, "Cocakola 2");
alert(map.get(object1)); // Cocakola 2
// String key is used as String
map.put("myKey", "MyValue");
alert(map.get("myKey")); // MyValue
alert(map.get("my".concat("Key"))); // MyValue
// Invalid keys
alert(map.get("unknownKey")); // undefined
alert(map.get(new Object())); // undefined
回答by ipodppod
Here is a proposal, combining @Florian's solution with @Laurent's.
这是一个提案，将@Florian 的解决方案与@Laurent 的解决方案相结合。
function HashTable() {
this.hashes = [];
}
HashTable.prototype = {
constructor: HashTable,
put: function( key, value ) {
this.hashes.push({
key: key,
value: value
});
},
get: function( key ) {
for( var i = 0; i < this.hashes.length; i++ ){
if(this.hashes[i].key == key){
return this.hashes[i].value;
}
}
}
};
It wont change your object in any way and it doesn't rely on JSON.stringify.
它不会以任何方式更改您的对象，也不依赖于 JSON.stringify。
回答by lama12345
Based on Peters answer, but with proper class design (not abusing closures), so the values are debuggable. Renamed from Mapto ObjectMap, because Mapis a builtin function. Also added the existsmethod:
基于 Peters 的回答，但具有适当的类设计（不滥用闭包），因此这些值是可调试的。重命名为Mapto ObjectMap，因为Map是一个内置函数。还添加了exists方法：
ObjectMap = function() {
this.keys = [];
this.values = [];
}
ObjectMap.prototype.set = function(key, value) {
var index = this.keys.indexOf(key);
if (index == -1) {
this.keys.push(key);
this.values.push(value);
} else {
this.values[index] = value;
}
}
ObjectMap.prototype.get = function(key) {
return this.values[ this.keys.indexOf(key) ];
}
ObjectMap.prototype.exists = function(key) {
return this.keys.indexOf(key) != -1;
}
/*
TestObject = function() {}
testA = new TestObject()
testB = new TestObject()
om = new ObjectMap()
om.set(testA, true)
om.get(testB)
om.exists(testB)
om.exists(testA)
om.exists(testB)
*/
回答by stamat
I know that I am a year late, but for all others who stumble upon this thread, I've written the ordered object stringify to JSON, that solves the above noted dilemma: http://stamat.wordpress.com/javascript-object-ordered-property-stringify/
我知道我迟到了一年，但是对于所有其他偶然发现此线程的人，我已将有序对象字符串化写入 JSON，从而解决了上述难题：http: //stamat.wordpress.com/javascript-object -有序属性字符串化/
Also I was playing with custom hash table implementations which is also related to the topic: http://stamat.wordpress.com/javascript-quickly-find-very-large-objects-in-a-large-array/
我也在玩自定义哈希表实现，这也与该主题相关：http: //stamat.wordpress.com/javascript-quickly-find-very-large-objects-in-a-large-array/
//SORT WITH STRINGIFICATION
var orderedStringify = function(o, fn) {
var props = [];
var res = '{';
for(var i in o) {
props.push(i);
}
props = props.sort(fn);
for(var i = 0; i < props.length; i++) {
var val = o[props[i]];
var type = types[whatis(val)];
if(type === 3) {
val = orderedStringify(val, fn);
} else if(type === 2) {
val = arrayStringify(val, fn);
} else if(type === 1) {
val = '"'+val+'"';
}
if(type !== 4)
res += '"'+props[i]+'":'+ val+',';
}
return res.substring(res, res.lastIndexOf(','))+'}';
};
//orderedStringify for array containing objects
var arrayStringify = function(a, fn) {
var res = '[';
for(var i = 0; i < a.length; i++) {
var val = a[i];
var type = types[whatis(val)];
if(type === 3) {
val = orderedStringify(val, fn);
} else if(type === 2) {
val = arrayStringify(val);
} else if(type === 1) {
val = '"'+val+'"';
}
if(type !== 4)
res += ''+ val+',';
}
return res.substring(res, res.lastIndexOf(','))+']';
}
回答by laurent
Just use the strict equality operator when looking up the object: ===
查找对象时只需使用严格相等运算符： ===
var objects = [];
objects.push(object1);
objects.push(object2);
objects[0] === object1; // true
objects[1] === object1; // false
The implementation will depend on how you store the objects in the HashTableclass.
实现将取决于您如何在HashTable类中存储对象。
回答by sethro
Using JSON.stringify()is completely awkward to me, and gives the client no real control over how their keys are uniquely identified. The objects that are used as keys should have a hashing function, but my guess is that in most cases overriding the toString()method, so that they will return unique strings, will work fine:
使用JSON.stringify()对我来说是完全尴尬的，并且让客户无法真正控制如何唯一标识他们的密钥。用作键的对象应该有一个散列函数，但我的猜测是在大多数情况下覆盖该toString()方法，以便它们返回唯一的字符串，可以正常工作：
var myMap = {};
var myKey = { toString: function(){ return '12345' }};
var myValue = 6;
// same as myMap['12345']
myMap[myKey] = myValue;
Obviously, toString()should do something meaningful with the object's properties to create a unique string. If you want to enforce that your keys are valid, you can create a wrapper and in the get()and put()methods, add a check like:
显然，toString()应该对对象的属性做一些有意义的事情来创建一个唯一的字符串。如果您想强制您的密钥有效，您可以创建一个包装器，并在get()和put()方法中添加如下检查：
if(!key.hasOwnProperty('toString')){
throw(new Error('keys must override toString()'));
}
But if you are going to go thru that much work, you may as well use something other than toString(); something that makes your intent more clear.
So a very simple proposal would be:
但是，如果您要完成那么多工作，则最好使用除toString(); 使您的意图更加清晰的东西。所以一个非常简单的建议是：
function HashTable() {
this.hashes = {};
}
HashTable.prototype = {
constructor: HashTable,
put: function( key, value ) {
// check that the key is meaningful,
// also will cause an error if primitive type
if( !key.hasOwnProperty( 'hashString' ) ){
throw( new Error( 'keys must implement hashString()' ) );
}
// use .hashString() because it makes the intent of the code clear
this.hashes[ key.hashString() ] = value;
},
get: function( key ) {
// check that the key is meaningful,
// also will cause an error if primitive type
if( !key.hasOwnProperty( 'hashString' ) ){
throw( new Error( 'keys must implement hashString()' ) );
}
// use .hashString() because it make the intent of the code clear
return this.hashes[ key.hashString() ];
}
};
回答by webjay
Inspired by @florian, here's a way where the id doesn't need JSON.stringify:
受到@florian 的启发，这里有一种不需要 id 的方法JSON.stringify：
'use strict';
module.exports = HashTable;
function HashTable () {
this.index = [];
this.table = [];
}
HashTable.prototype = {
constructor: HashTable,
set: function (id, key, value) {
var index = this.index.indexOf(id);
if (index === -1) {
index = this.index.length;
this.index.push(id);
this.table[index] = {};
}
this.table[index][key] = value;
},
get: function (id, key) {
var index = this.index.indexOf(id);
if (index === -1) {
return undefined;
}
return this.table[index][key];
}
};
回答by edrian
I took @Ilya_Gazman solution and improved it by setting '_hashtableUniqueId' as a not enumerable property (it won't appear in JSON requests neither will be listed in for loops). Also removed UniqueId object, since it is enough using only HastTable function closure. For usage details please see Ilya_Gazman post
我采用了@Ilya_Gazman 解决方案并通过将 '_hashtableUniqueId' 设置为不可枚举的属性来改进它（它不会出现在 JSON 请求中，也不会在 for 循环中列出）。还删除了 UniqueId 对象，因为仅使用 HastTable 函数闭包就足够了。有关使用详情，请参阅 Ilya_Gazman 帖子
function HashTable() {
var hash = new Object();
return {
put: function (key, value) {
if(!HashTable.uid){
HashTable.uid = 0;
}
if (typeof key === "string") {
hash[key] = value;
} else {
if (key._hashtableUniqueId === undefined) {
Object.defineProperty(key, '_hashtableUniqueId', {
enumerable: false,
value: HashTable.uid++
});
}
hash[key._hashtableUniqueId] = value;
}
},
get: function (key) {
if (typeof key === "string") {
return hash[key];
}
if (key._hashtableUniqueId === undefined) {
return undefined;
}
return hash[key._hashtableUniqueId];
}
};
}
