Javascript HashTable use Object key

I want to create a hash table with Object keys that are not converted into 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 answer for full solution

10 thoughts on “Javascript HashTable use Object key”

  1. Here is a simple Map implementation that will work with any type of key, including object references, and it will not mutate the key in any way:

    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 indexOf function is implemented by the JavaScript engine and is highly optimized.

    Reply
  2. Inspired by @florian, here’s a way where the id doesn’t need 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];
      }
    
    };
    
    Reply
  3. I took @Florian Margaine’s suggestion to higher level and came up with this:

    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
    
    Reply
  4. Based on Peters answer, but with proper class design (not abusing closures), so the values are debuggable. Renamed from Map to ObjectMap, because Map is a builtin function. Also added the exists method:

    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)
    */
    
    Reply
  5. 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

    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];
           }
       };
    }
    
    Reply
  6. I know I’m late, but here’s a simple HashMap implementation:

    Function.prototype.toJSON = Function.prototype.toString;
    //taken from https://stackoverflow.com/questions/1249531/how-to-get-a-javascript-objects-class
    function getNativeClass(obj) {
        if (typeof obj === "undefined") return "undefined";
        if (obj === null) return "null";
        return Object.prototype.toString.call(obj).match(/^\[object\s(.*)\]$/)[1];
    }
    function globals() {
        if (typeof global === "object") //node
            return global;
        return this;
    }
    
    function lookup(x) {
        return globals()[x];
    }
    
    function getAnyClass(obj) {
        if (typeof obj === "undefined") return "undefined";
        if (obj === null) return "null";
        return obj.constructor.name;
    }
    
    //taken from https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Errors/Cyclic_object_value#examples
    var getCircularReplacer = () => {
        const seen = new WeakSet();
        return (key, value) => {
            if (typeof value === "object" && value !== null) {
                if (seen.has(value)) {
                    return "[Circular]";
                }
                seen.add(value);
            }
            return value;
        };
    };
    
    
    
    function encode(x) {
        if (typeof x === "object" && x !== null) {
            var y = myClone(x);
            x = Object.getPrototypeOf(x);
            for (var i = 0; i < Object.getOwnPropertyNames(y).length; i++) { //Make enumerable
                x[Object.getOwnPropertyNames(y)[i]] = y[Object.getOwnPropertyNames(y)[i]];
            }
        }
    
        return getAnyClass(x) + " " + JSON.stringify(x, getCircularReplacer());
    }
    
    function decode(x) {
        var a = x.split(" ").slice(1).join(" "); //OBJECT
        if (typeof lookup(x.split(" ")[0])) {
            return new (lookup(x.split(" ")[0]))(JSON.parse(a))
        } else {
            return JSON.parse(a);
        }
    }
    
    
    //taken from https://github.com/feross/fromentries/blob/master/index.js
    /*! fromentries. MIT License. Feross Aboukhadijeh <https://feross.org/opensource> */
    function fromEntries(iterable) {
        return [...iterable].reduce((obj, [key, val]) => {
            obj[key] = val
            return obj
        }, {})
    }
    
    
    var toEnumerable = (obj) => {
        return fromEntries(
            Object.getOwnPropertyNames(obj).map(prop => [prop, obj[prop]])
        );
    };
    
    
    //taken from https://stackoverflow.com/questions/41474986/how-to-clone-a-javascript-es6-class-instance
    function myClone(instanceOfBlah) {
        if (typeof instanceOfBlah !== "object" || !instanceOfBlah) { return instanceOfBlah; }
        const clone = Object.assign({}, toEnumerable(instanceOfBlah));
        const Blah = instanceOfBlah.constructor;
        Object.setPrototypeOf(clone, Blah.prototype);
        return clone;
    }
    
    function HashMap(a) {
        if (typeof a === "undefined") {
            a = [];
        }
    
        a = Array.from(a);
    
        a = a.map((e) => [encode(e[0]), e[1]]);
    
        this.a = a;
    }
    
    
    HashMap.from = function (a) {
        var temp = myClone(a);
        //convert to array
        a = [];
        for (var i = 0; i < Object.getOwnPropertyNames(temp).length; i++) {
            a.push([Object.getOwnPropertyNames(temp)[i], temp[Object.getOwnPropertyNames(temp)[i]]]);
        }
        return new HashMap(a);
    }
    
    HashMap.prototype.put = function (x, y) {
        this.a.push([encode(x), y]);
    }
    
    HashMap.prototype.get = function (x) {
        var t1 = this.a.map((e) => e[0]);
        return this.a[t1.indexOf(encode(x))][1];
    }
    
    HashMap.prototype.length = function () {
        return this.a.length;
    }
    
    HashMap.prototype.toString = function () {
        var result = [];
        for (var i = 0; i < this.length(); i++) {
            result.push(JSON.stringify(decode(this.a[i][0]), getCircularReplacer()) + " => " + this.a[i][1]);
        }
    
    
        return "HashMap {" + result + "}";
    }
    
    
    
    var foo = new HashMap();
    foo.put("SQRT3", Math.sqrt(3));
    foo.put({}, "bar");
    
    console.log(foo.get({}));
    console.log(foo.toString());

    Note that it is ordered.
    Methods:

    • put: Adds an item
    • get: Access an item
    • from (static): Convert from a JavaScript object
    • toString: Convert to string

    Minified and without the test:

    function getNativeClass(t){return void 0===t?"undefined":null===t?"null":Object.prototype.toString.call(t).match(/^\[object\s(.*)\]$/)[1]}function globals(){return"object"==typeof global?global:this}function lookup(t){return globals()[t]}function getAnyClass(t){return void 0===t?"undefined":null===t?"null":t.constructor.name}Function.prototype.toJSON=Function.prototype.toString;var getCircularReplacer=()=>{const t=new WeakSet;return(e,r)=>{if("object"==typeof r&&null!==r){if(t.has(r))return"[Circular]";t.add(r)}return r}};function encode(t){if("object"==typeof t&&null!==t){var e=myClone(t);t=Object.getPrototypeOf(t);for(var r=0;r<Object.getOwnPropertyNames(e).length;r++)t[Object.getOwnPropertyNames(e)[r]]=e[Object.getOwnPropertyNames(e)[r]]}return getAnyClass(t)+" "+JSON.stringify(t,getCircularReplacer())}function decode(t){var e=t.split(" ").slice(1).join(" ");return lookup(t.split(" ")[0]),new(lookup(t.split(" ")[0]))(JSON.parse(e))}function fromEntries(t){return[...t].reduce((t,[e,r])=>(t[e]=r,t),{})}var toEnumerable=t=>fromEntries(Object.getOwnPropertyNames(t).map(e=>[e,t[e]]));function myClone(t){if("object"!=typeof t||!t)return t;const e=Object.assign({},toEnumerable(t)),r=t.constructor;return Object.setPrototypeOf(e,r.prototype),e}function HashMap(t){void 0===t&&(t=[]),t=(t=Array.from(t)).map(t=>[encode(t[0]),t[1]]),this.a=t}HashMap.from=function(t){var e=myClone(t);t=[];for(var r=0;r<Object.getOwnPropertyNames(e).length;r++)t.push([Object.getOwnPropertyNames(e)[r],e[Object.getOwnPropertyNames(e)[r]]]);return new HashMap(t)},HashMap.prototype.put=function(t,e){this.a.push([encode(t),e])},HashMap.prototype.get=function(t){var e=this.a.map(t=>t[0]);return this.a[e.indexOf(encode(t))][1]},HashMap.prototype.length=function(){return this.a.length},HashMap.prototype.toString=function(){for(var t=[],e=0;e<this.length();e++)t.push(JSON.stringify(decode(this.a[e][0]),getCircularReplacer())+" => "+this.a[e][1]);return"HashMap {"+t+"}"};
    

    Also, you can customize the encoder and decoder by changing encode and decode functions.

    As in florian’s answer, you can’t play with the reference in js however (so two empty objects will look like the same to the hashtable).

    Reply
  7. 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:

    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:

    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:

    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()  ];
        }
    };
    
    Reply
  8. 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 HashTable class.

    Reply
  9. Here is a proposal, combining @Florian’s solution with @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;
                }
            }
        }
    };
    

    It wont change your object in any way and it doesn’t rely on JSON.stringify.

    Reply
  10. The best solution is to use WeakMap when you can (i.e. when you target browsers supporting it)

    Otherwise you can use the following workaround (Typescript written and collision safe):

    // 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];
        };
    }
    

    Then you can simply get a unique number for any object in your code (like if would have been for pointer address)

    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"
    
    Reply

Leave a Comment