Javascript HashTable использует ключ Object

Ответ 1

Вот предложение:

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 ⁵³, то есть.

И теперь решение "это не сработает": используйте 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.

Ответ 2

Вот простая реализация 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 и оптимизирована.

Ответ 3

Я взял предложение @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

Ответ 4

Вот предложение, объединяющее решение @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.

Ответ 5

Просто используйте оператор строгого равенства при поиске объекта: ===

var objects = [];
objects.push(object1);
objects.push(object2);

objects[0] === object1; // true
objects[1] === object1; // false

Реализация будет зависеть от того, как вы храните объекты в классе HashTable.

Ответ 6

Я знаю, что я опаздываю на год, но для всех остальных, которые наткнулись на эту нить, я написал упорядоченный объект, строящий 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(','))+']';
}

Ответ 7

Использование 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()  ];
    }
};

Ответ 8

Вдохновленный @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];
  }

};

Ответ 9

Я принял решение @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];
       }
   };
}

Ответ 10

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"