Javascript HashTable use Object key

Question

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

Solution 1

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.

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?

Jsfiddle demo: 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/

This means that your objects need to have a property named id that 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).

It also means you are limited on the number of items you can store in this hashtable. Limited to 2⁵³, that is.

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

It slightly differs from your API though (it's set and not 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/

However, weakmaps are implemented in FF and Chrome (only if 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.

You can also use Maps, they may more suit your needs, since you also need to store primitive values (strings) as keys. Doc, Shim.

Solution 2

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.

Solution 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

Solution 4

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.

Solution 5

When you say you don't want your Object keys converted into Strings, I'm going to assume it's because you just don't want the entire code contents of your Objects being used as keys. This, of course, makes perfect sense.

While there is no "hash table" in Javascript per-se, you can accomplish what you're looking for by simply overriding your Object's prototype.toString and returning a valid key value that will be unique to each instance. One way to do this is with Symbol():

function Obj () {
    this.symbol = Symbol() // Guaranteed to be unique to each instance
}

Obj.prototype.toString = function () {
    return this.symbol // Return the unique Symbol, instead of Obj's stringified code
}

let a = new Obj()
let b = new Obj()

let table = {}

table[a] = 'A'
table[b] = 'B'

console.log(table)      // {Symbol(): 'A', Symbol(): 'B'}
console.log(table[a])   // A
console.log(table[b])   // B

View more solutions

Comments

[Anna B]

In ES6, you can use WeakMap for this purpose.

[neaumusic]

WeakMap

[Koray Tugay]

Both links above are dead, recent one: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…

[Ilya Gazman]

This is not hashtable, this is bad practis of array list with efficiency of O(n). It's not what I am looking

[laurent]

There is no built-in hash table in JavaScript so, if you don't want to convert the object to a string, you need to use an array and loop through it. How much data will your table store?

[Ilya Gazman]

thousandths,I need to find a solution some how. Converting to string not promise me a unique key.

[Ilya Gazman]

This is a solution indeed, I am just wondering how heavy is that JSON.stringify

[laurent]

@Babibu, it depends on the size of the object. The bigger it is, the longer it will take to stringify it. If storing objects in a simple array is overkill for you, then stringifying your thousands of objects will probably be too.

[Florian Margaine]

JSON.stringify is cheap. Really. This is not going to be the bottleneck of your application.

[Florian Margaine]

But beware that it doesn't exactly fill in your original needs: a unique key for every object. As said in the answer, you can't do that.

[Florian Margaine]

@Babibu I edited to add a solution to work around this, and it's "cheaper" than JSON.stringify, although it has a little drawback: you need a special property.

[Ilya Gazman]

Yeah I think it will do the job. The only problem with your solution is that you manage the id inside HashTable witch is wrong. It need to be in some place that is unique to the application, so I be able to have more then just one HashTable

[Florian Margaine]

Why? Each HashTable has unique object/values in itself, what's wrong about it?

[laurent]

@Babidu, you write "The only problem with your solution is that you manage the id inside HashTable". So why don't you manage it outside the class? Just define some kind of global variable. It seems you are looking for someone to write a ready-made solution for you. Florian Margaine provided a good start which just needs to be tweaked for your need.

[Ilya Gazman]

@FlorianMargaine After working a bit I posted a complete solution

[Florian Margaine]

Glad you got it sorted out :)

[Florian Margaine]

@Babibu just for the sake of completeness, I added a last method, the one that should be used, using WeakMaps. They're not supported everywhere however.

[Peter V. Mørch]

This is wrong. You cannot rely on the ordering of keys in JSON.stringify(). To different objects with the same keys and values are not guaranteed to return the same string with JSON.stringify() (even though they do "most of the time"). See javascript - Is there a deterministic equivalent of JSON.stringify? for a better (but not-trivial-JSON.stringify()) string for an object.

[Florian Margaine]

@Peter in reality, JSON.stringify is deterministic on the same implemebtation, as the answer you linked to says. If you really want deterministic order across implementations (which is not needed there), it's trivial to implement.

[Peter V. Mørch]

@FlorianMargaine I didn't read anywhere in that question that it should be deterministic on the same implementation. That seems to be the case, though. I did however read that MDN's stringify page says "Properties of non-array objects are not guaranteed to be stringified in any particular order. Do not rely on ordering of properties within the same object within the stringification." Even though it works today, there are no guarantees for tomorrow.

[stamat]

As Peter claimed objects in JavaScript are unordered, that is true. But I guess 'for var i in obj' might not always return the correct order of properties as they were put in object. And I guess stringify uses the same iteration. So why not make a recursive function that reorders the properties alphabetically. And then use stringify?, or if it is not reliable make your own function that writes json!? I've thought about this a lot... And I've tried a similar solution, check it out: stamat.wordpress.com/…

[sethro]

The problem with this, is it is not a "Hash" table; there is no hashing going on. You just created a misleading wrapper for an array. Also, because of your use of "==", you will get unexpected results when using mixed types as keys informit.com/articles/article.aspx?p=1997934&seqNum=5.

[sethro]

This requires that you always keep a reference to the object you used as a key, when calling put(). If you are going to do that, why map the values in the first place; why not just keep references to the values instead? Have you considered what will happen if you have two objects that are equivalent, but not the same object (!==) ? They should hash to the same value, but the get() method will fail you for any valid key that is not the exact object used in put() since you only added the ._hashtableUniqueId property to one of them.

[sethro]

the .id addition creates a meaningless hashtable. It requires you to always keep a reference to the exact object you were using as a key when you called put(). The purpose of the map is defeated; if you always have a reference to the same object, you should never have to "look it up". You'd be better of keeping a reference to the value you are trying to map. You need the functionality that allows two objects, that are not the same object in memory, to be equivalent. Because that is missing, get() will fail for any meaningful use case. I hope that makes sense.

[edrian]

Nice solution!! I've improved this solution by adding _hashtableUniqueId to key using Object.defineProperty and configuring it as not enumerable, so it won't appear in, for example, json requests. Also UniqueID object is not necessary. You can look at my answer for details.

[Ilya Gazman]

What if I map one item in two different HashTable maps? You will get duplicated ids... To avoid this I used the UniqueId object. Good one with jsons.

[edrian]

@Ilya_Gazman thanks for noticing that!, fixed the code above. Didn't have that problem in my AngularJS implementation because there was an extra closure in factory method.

[Ilya Gazman]

No @ShawnMoore it will be fine. you will get "101"._hashtableUniqueId equals to some random number

[Sasha Chedygov]

To future readers: Note that Map is no longer a good name for this since it conflicts with the built-in Map type.

[rebelzach]

Its 2018 and WeakMaps have much better support now.

[Florian Margaine]

Indeed, much better than in 2012 :)

[Peter]

I used a closure to enforce encapsulation—we are creating an abstraction. The underlying data structure should only be mutable using our explicit public interface. This reduces the likelihood of bugs/errors/misuse in application code. We can still debug the internals in the debugger, or add additional convenience methods such as hasKey() or size().

[kungfooman]

@Peter it just obfuscates understanding by now allowing new developers to actually understand the internals via F12/devtools. You only think you do something good, but actually it prevents understanding and hence THAT leads to bugs.

[Peter]

The whole idea behind abstraction is that it allows us to reason about the problem we are trying to solve at a higher level. The Map defines a contract and allows us to offload a certain amount of mental load. Think of this like any other JS engine builtin. Software systems are all about building abstractions upon abstractions until we can express in terms of “what” we want instead of “how”. This really is the only thing that prevents large projects (with hundreds of contributors) from collapsing.

[kungfooman]

Oh really? I work with a large WebGL/PBR/Game engine on GitHub and it exposes everything for debugging purposes. And guess what, it's doing great, far from collapsing. Just don't merge shitty Pull Requests until they fixed the code...

[Peter]

Sorry, didn’t mean to get personal. You are right—things like core libraries, game engines, kernels, device drivers, etc. all make these kind of trade offs—and for good reason—to maximize performance. This is possible with a highly skilled and disciplined team. What I am talking about is risk mitigation, when you can.

[Nirvana]

if you to define variable without var keyword, it will not work in strict mode

[Nirvana]

Why do objects need to implement "hashString()" method themselves? couldn't you just define one yourself? see this: how-to-reliably-hash-javascript-objects

[Qtax]

Is this better than WeakMap somehow?