ansaurus

Question

JavaScript implementation of a set data structure

Answer 1

+4 A:

You could build a simple wrapper around the keys of a hash table provided by my jshashtable. I have one knocking around somewhere that I will dig out later.

UPDATE

I have completed and tested an implementation of HashSet and uploaded it to the jshashtable project on Google Code. You can download it or view the source.

var s = new HashSet();
var o1 = {name: "One"}, o2 = {name: "Two"};
s.add(o1);
s.add(o2);
s.values(); // Array containing o1 and o2

Tim Down 2010-03-26 13:51:15

can you explain how your library calculates object hash codes?

stereofrog 2010-03-27 01:16:16

It's in the documentation, but in summary: the hash codes are strings, and you can provide a function to calculate hash codes to the `Hashtable` constructor (as well as a function that compares two object and decides if they're equal). Otherwise, it looks for a method called `hashCode()` on keys. As a last resort, it attempts to convert the key to a string using `toString()` or `String()`. If all your keys hash to the same value (e.g. "[object Object]") because you haven't used any of the above mechanisms then they'll all go into the same bucket and it has to use your simple linear search.

Tim Down 2010-03-27 11:27:53

thanks!........

stereofrog 2010-03-27 20:55:30

Answer 2

+1 A:

I don't think there's a way to work with object's hash code other than store it in the object itself. Strictly speaking, it's possible to create a set class without hashing, using simple linear search, but this would hardly be efficient.

stereofrog 2010-03-26 14:02:25

Indeed. There is no way to get an object's identity in JS other than to compare it with every other object.

bobince 2010-03-26 18:10:26

ansaurus

tags:

views:

answers:

JavaScript implementation of a set data structure

related questions