javascript - Data structure for objects with O(1) lookup? - Stack Overflow

admin管理员组

文章数量:1399926

Suppose I'm visiting nodes in a graph data structure. As I visit each node, I would add it to a "visited" list. It would be desirable to have an O(1) lookup to verify that I don't visit the same node more than once.

Of course, if each node has an associated value, I could use a regular JavaScript object (hash table) to store my "visited" list, but suppose I want to be agnostic to whether the node can evaluate to a string or not. Is there a JavaScript data structure that would support O(1) lookups for objects? How could I implement one?

Suppose I'm visiting nodes in a graph data structure. As I visit each node, I would add it to a "visited" list. It would be desirable to have an O(1) lookup to verify that I don't visit the same node more than once.

Of course, if each node has an associated value, I could use a regular JavaScript object (hash table) to store my "visited" list, but suppose I want to be agnostic to whether the node can evaluate to a string or not. Is there a JavaScript data structure that would support O(1) lookups for objects? How could I implement one?

• javascript

Share Improve this question Follow asked Oct 16, 2015 at 21:21 BlackhawkBlackhawk 6,15044 gold badges2929 silver badges5959 bronze badges 8

• Then use ES2015 Set (or WeakMap whichever suits better) – zerkms Commented Oct 16, 2015 at 21:22
• you can push to an array and use array.indexOf to see if a node ref is in the list, but that's probably slow. you could also set an invisible prop on the node itself, which is fast, but might break things depending on setup. – dandavis Commented Oct 16, 2015 at 21:31
• @zerkms I just checked my pany-mandated browser against the patibility list here and cried a little bit :'( – Blackhawk Commented Oct 16, 2015 at 21:40
• @Blackhawk babeljs.io – zerkms Commented Oct 16, 2015 at 21:47
• @zerkms interesting... I'm going to take a look and see if I can figure out how they've implemented the functionality... – Blackhawk Commented Oct 16, 2015 at 21:53

 |  Show 3 more ments

2 Answers 2

Sorted by: Reset to default 7

You can either use the Set or WeakMap both added in ES2015.

And you don't need to wait for the browser support, since transpilers like babel have standard-pliant polyfills.

To do O(1) lookups, you need to use a hash set. There is no hash set in native javascript, but there is a hash map (plain object). You can emulate a hash set by checking if the object contains the key. Your value needs to implement the toString method.

var Set = function () {}
Set.prototype.contains = function (v) {
  return (v.toString() in this);
}
Set.prototype.add = function (v) {
  this[v.toString()] = true;
}
Set.prototype.remove = function (v) {
  delete this[v.toString()];
}

本文标签： javascriptData structure for objects with O(1) lookupStack Overflow