4 ms·

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 string

by vkjv 11y ago

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?

nkoren 11y ago
> 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.
- dsp1234 11y ago
  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/Reference/Global_Objects/Array/indexOf https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
  - nkoren 11y ago
    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...
    - dsp1234 11y ago
      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. So 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-ARCH/ECMA-262,%203rd%20edition,%20December%201999.pdf http://www.ecma-international.org/publications/files/ECMA-ST...
- tlb 11y ago
  Don't forget to mangle the strings, otherwise inserting things with names meaningful to Javascript ('hasOwnProperty', '__prototype__') can cause great suffering.
mistercow 11y ago
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.
aaco 11y ago
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/closure/goog/structs/set.js#L59 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/closure/goog/base.js#L1653 https://github.com/google/closure-library/blob/v20160125/clo...
- dsp1234 11y ago
  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.
  - dcherman 11y ago
    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.

by vkjv 11y ago

nkoren 11y ago

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

dsp1234 11y ago
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/Reference/Global_Objects/Array/indexOf https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- nkoren 11y ago
  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...
  - dsp1234 11y ago
    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. So 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-ARCH/ECMA-262,%203rd%20edition,%20December%201999.pdf http://www.ecma-international.org/publications/files/ECMA-ST...
tlb 11y ago
Don't forget to mangle the strings, otherwise inserting things with names meaningful to Javascript ('hasOwnProperty', '__prototype__') can cause great suffering.

mistercow 11y ago

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.

aaco 11y ago

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/closure/goog/structs/set.js#L59 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/closure/goog/base.js#L1653 https://github.com/google/closure-library/blob/v20160125/clo...

dsp1234 11y ago
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.
- dcherman 11y ago
  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.