Я хочу создать хеш-таблицу, которая получает мой объект как его ключ, не преобразовывая его в String.
Что-то вроде этого:
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
РЕДАКТИРОВАТЬ: См. мой ответ для полного решения
Вот предложение:
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 ) ];
}
};
API точно так же, как показано в вашем вопросе.
Однако вы не можете играть со ссылкой в js (так что два пустых объекта будут похожи на хэш-таблицу), потому что у вас нет способа его получить. См. Этот ответ для получения более подробной информации: Как получить ссылки на объекты javascript или количество ссылок?
Jsfiddle demo: http://jsfiddle.net/HKz3e/
Однако для уникальной стороны вещей вы могли бы играть с оригинальными объектами, например, следующим образом:
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/
Это означает, что ваши объекты должны иметь свойство с именем id, которое вы не будете использовать в другом месте. Если вы хотите, чтобы это свойство не было перечислимым, я предлагаю вам взглянуть на defineProperty (однако это не кросс-браузер, даже с ES5-Shim, он не работает в IE7).
Это также означает, что вы ограничены количеством элементов, которые вы можете сохранить в этой хеш-таблице. Ограничено 2 53, то есть.
И теперь решение "это не сработает": используйте ES6 WeakMaps. Они выполняются именно для этой цели: наличие объектов в качестве ключей. Я предлагаю вам прочитать MDN для получения дополнительной информации: https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/WeakMap
Он немного отличается от вашего 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 с помощью слайд-карты: http://jsfiddle.net/Ralt/HKz3e/9/
Однако слабые карты реализованы в FF и Chrome ( только, если вы включили флаг "Экспериментальные функции javascript" в Chrome). Имеются прокладки, как этот: https://gist.github.com/1269991. Используйте на свой страх и риск.
Вы также можете использовать Maps, они могут больше соответствовать вашим потребностям, так как вам также нужно хранить примитивные значения (строки) в качестве ключей. Doc, Shim.
Вот простая реализация 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)];
}
};
}
Хотя это дает ту же функциональность, что и хэш-таблица, она фактически не реализуется с использованием хеш-функции, так как она выполняет итерацию по массивам и имеет худшую производительность O (n). Однако для подавляющего большинства разумных вариантов использования это не должно быть проблемой вообще. Функция indexOf реализована механизмом JavaScript и оптимизирована.
Я взял предложение @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();
};
Использование
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
Вот предложение, объединяющее решение @Florian с @Laurent's.
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;
}
}
}
};
Это не изменит ваш объект каким-либо образом, и он не полагается на JSON.stringify.
Просто используйте оператор строгого равенства при поиске объекта: ===
var objects = [];
objects.push(object1);
objects.push(object2);
objects[0] === object1; // true
objects[1] === object1; // false
Реализация будет зависеть от того, как вы храните объекты в классе HashTable.
Я знаю, что я опаздываю на год, но для всех остальных, которые наткнулись на эту нить, я написал упорядоченный объект, строящий JSON, который решает вышеупомянутую дилемму: http://stamat.wordpress.com/javascript-object-ordered-property-stringify/
Также я играл с пользовательскими реализациями хеш-таблицы, которые также связаны с темой: 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(','))+']';
}
Использование JSON.stringify() для меня совершенно неудобно и дает клиенту никакого реального контроля над тем, как их ключи уникально идентифицированы. Объекты, которые используются как ключи, должны иметь функцию хэширования, но я предполагаю, что в большинстве случаев переопределение метода toString(), чтобы они возвращали уникальные строки, будет работать нормально:
var myMap = {};
var myKey = { toString: function(){ return '12345' }};
var myValue = 6;
// same as myMap['12345']
myMap[myKey] = myValue;
Очевидно, что toString() должно сделать что-то значимое для свойств объекта для создания уникальной строки. Если вы хотите, чтобы ваши ключи были действительными, вы можете создать обертку и в методах get() и put(), добавьте проверку как:
if(!key.hasOwnProperty('toString')){
throw(new Error('keys must override toString()'));
}
Но если вы собираетесь пройти эту работу, вы можете использовать что-то другое, кроме 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() ];
}
};
Вдохновленный @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];
}
};
Я принял решение @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];
}
};
}
Typescript версия one и безопасность при столкновении:
// Run this in the beginning of your app (or put it into a file you just import)
(enableObjectID)();
const uniqueId: symbol = Symbol('The unique id of an object');
function enableObjectID(): void {
if (typeof Object['id'] !== 'undefined') {
return;
}
let id: number = 0;
Object['id'] = (object: any) => {
const hasUniqueId: boolean = !!object[uniqueId];
if (!hasUniqueId) {
object[uniqueId] = ++id;
}
return object[uniqueId];
};
}
Затем вы можете просто получить уникальный номер для любого объекта в вашем коде (например, если бы это был адрес указателя)
let objectA = {};
let objectB = {};
let dico = {};
dico[(<any>Object).id(objectA)] = "value1";
// or
dico[Object['id'](objectA);] = "value1";
// If you are not using typescript you don't need the casting
dico[Object.id(objectA)] = "value1"