Hacker News Reader

Comment by vkjv | Hacker News Reader

Unless by "hash based" you mean just using `new Set()`, I'm not aware of a way to do this generically. Using a `{}` for this would only work for a set of strings and things that can be uniquely coerced into strings. Otherwise, looping over arrays is your only option.

Care to elaborate?

View on HN

Google Closure Library does this in goog.structs.Set with an interesting generic solution.

A string key for the underlying map is generated based on the data type of the element being added in the set. If you're adding an object into the set, the object is mutated so that it stores a unique ID. The object's unique ID is used to form the string key that will identify this object in the set.

Note how goog.structs.Set.getKey_ is used in the add() method: https://github.com/google/closure-library/blob/v20160125/clo...

This is how the library obtains the unique ID of an object: https://github.com/google/closure-library/blob/v20160125/clo...

I wonder if that's a problem with stuff like immutibleJS since the object itself is permanently mutated as part of being added to the set.

Also, if this was being done for ES5+ code, then either setting that property to non-enumerable or using something like Symbols would be cool since it would hopefully have a reduced impact on other code.

Depending on the implementation, yup. Since both of the most popular Immutable libraries that I know of (Immutable.js, mori) have their own API for setting properties via a `.set` method, it would not be unreasonable for them to use `Object.freeze` in order to make raw mutations throw an error.

Both libraries provide their own implementation of a Set though, so in practice you would just use the library provided one.

> Using a `{}` for this would only work for a set of strings and things that can be uniquely coerced into strings.

The code they use has the same limitation. It adds / removes / ensures the uniqueness of elements in the set by using Array.indexOf(...), which only works for strings and things that can be uniquely coerced into strings.

So, given this limitation, using an Object-based set would be vastly more performant.

  var set = []
  var foo = {foot: 1}
  var bar = {bart: 2}
  set.push(foo)
  set.indexOf(foo) //0
  set.indexOf(bar) //-1

"indexOf() compares searchElement to elements of the Array using strict equality (the same method used by the ===, or triple-equals, operator)."[0]

MDN has the link to the ES5 specification, but the key part is 9(c)(ii):

"Let same be the result of applying the Strict Equality Comparison Algorithm to searchElement and elementK."

[0] - https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

Hmm, and yet:

   var elem = {foo:"bar"}
   var set = [elem]
   set.indexOf(elem) // 0
   set.indexOf({foo:"bar"}) // -1

So I guess the strict equality comparison is using some kind of internal objectId rather than the property name and values of the objects? I guess depend on how you want to define "uniqueness" for your set...

Objects in JavaScript use referential equality when checking for strict equality, which indexOf uses. In your code, 'elem' and '{foo:"bar"}' are different objects which is why your code doesn't work as expected.

  var x = {foo:"bar"}
  var y = {foo:"bar"}
  var z = x
  x === y //false
  x === z //true

This is specified in the ES3 document[0] at 11.9.6(13):

"13. Return true if x and y refer to the same object or if they refer to objects joined to each other (see 13.1.2). Otherwise, return false."

[0] - http://www.ecma-international.org/publications/files/ECMA-ST...

Don't forget to mangle the strings, otherwise inserting things with names meaningful to Javascript ('hasOwnProperty', '__prototype__') can cause great suffering.

You can do it the way a lot of libraries do where you require that anything you want in a set implement an interface for hashing and equality testing. Then you use an object with hashes for keys and arrays for values.

Reply on news.ycombinator.com