I've even seen implementations that compare objects using
JSON.stringify.
I would expect a memoizer and most hash code/table implementations to treat { foo: "bar", baz: "quux" } and { baz: "quux", foo: "bar" } as equivalent, but many implementations use JSON.stringify, which doesn't guarantee this:
$ node
> JSON.stringify({ foo: "bar", baz: "quux" })
'{"foo":"bar","baz":"quux"}'
> JSON.stringify({ baz: "quux", foo: "bar" })
'{"baz":"quux","foo":"bar"}'
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.
https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/JSON/stringify
- Document the fact that these implementations only support JSON-serializable values (e.g. not regular expressions or functions[1][2]), and use a canonical JSON serializer e.g:
Or 2) use a more general-purpose object-graph hashing/digest solution:
- ???
A failed lookup because of a different JSON representation is (potentially) a bug in a hashtable, but may be merely non-optimal in a memoizer.
A collision is potentially a serious bug in both.
Map-style implementations (e.g. using indexOf or find) have worst-case O(n) complexity (for search/insert/delete), where n is the number of keys.
WeakMap-style implementations (tagging objects with a non-enumerable property) cannot (use this technique to) support frozen objects.
A general-purpose hash code function potentially needs to track/tag every object passed to it.
A hash table only needs to identify/tag its members.
Support for circular references is often missing.
- addyosmani/memoize.js
- caiogondim/fast-memoize.js
- flesler/hashmap
- planttheidea/hash-it
- puleos/object-hash
- https://github.com/jashkenas/underscore/blob/bb4a6061fd285b5367289219102e47619c929be3/underscore.js#L1090-L1185
- https://github.com/jordangarcia/object-hasher
- nodejs/node-v0.x-archive#7161
- https://github.com/Polymer/WeakMap
- https://github.com/skerit/json-dry
- https://www.npmjs.com/package/hashify
- https://www.npmjs.com/package/jseq
- https://www.npmjs.com/package/tosource
Hello. Anything changed since then? I can see flesler/hashmap#15 topic and seems like nothing had change.
Do you recommend any existing HashMap implementation? Collisions are obviously serious malicious flaws.