CODEWITHSUNDEEP
javascript
Blackhawk
Blackhawk

Reputation: 6140

Data structure for objects with O(1) lookup?

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?

Upvotes: 2

Views: 6247

Answers (2)

zerkms
zerkms

Reputation: 255025

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

Upvotes: 7

twinlakes
twinlakes

Reputation: 10258

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()];
}

Upvotes: 0

Related Questions