具有O（1）查找的对象的数据结构？

Question

假设我正在访问图形数据结构中的节点。当我访问每个节点时，我会将其添加到“已访问”列表中。希望有一个O（1）查找来验证我不会多次访问同一个节点。当然，如果每个节点都有一个关联的值，我可以使用常规的JavaScript对象（散列表）来存储我的“已访问”列表，但是假设我想知道节点是否可以评估为字符串或不。是否有支持O（1）查找对象的JavaScript数据结构？我怎么能实现一个？

Answer 1

您可以使用Set或WeakMap在ES2015都增加。

而且您不需要等待浏览器支持，因为像babel这样的转换器具有符合标准的polyfills。

Answer 2

要做O（1）查找，您需要使用哈希集。本地javascript中没有哈希集，但是有一个哈希映射（纯文本对象）。您可以通过检查对象是否包含密钥来模拟哈希集合。您的价值需要实施toString方法。

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