javascript - 哈希表是如何在 JavaScript 中实现的

Question

一些语言实现了哈希表，它可以使用任何东西作为键，而不仅仅是字符串。在 JavaScript 中，您只能使用字符串和数字。这种实现的查找还是O(1)吗？有 JavaScript 的实现吗？

Answer 1

关于这个主题显然存在很多误解。在 JavaScript 中，对象的键实际上只是字符串(参见 §8.10 )。 任何 用作对象键的内容(包括数字)都将转换为字符串。因此，obj[1] 和 obj["1"] 是等价的。

在内部，许多 JS 实现使用某种哈希表来快速查找对象属性。 V8 实际上 generates hidden C++ classes允许查找在单个 CPU 指令中执行。无论哪种方式，都可以安全地假设对象属性访问很快并且接近 O(1)。

由于所有对象属性键都被转换为字符串，您只能使用转换为字符串的事物作为键。由于数字自然会转换为字符串，因此它们工作正常。 bool 值也一样。日期也有效，因为 Date 实例会转换为唯一的字符串(尽管需要注意一些边缘情况)。

但是，对象不会转换为有意义的字符串。例如:

var o = {};
o[{a:1}]='some value';

实际结果:

o = { '[object Object]': 'some value' }

因为 string conversion rules .由于每个对象都会转换为 [object Object]，因此将许多对象作为键添加到另一个对象将导致一个对象只有一个属性。

当然，仍然可以使用对象作为键。您只需覆盖 toString 的默认实现 — 实际上，创建您自己的哈希算法。例如，

function ComplexKey(a,b) {
    this.a = a;
    this.b = b;
}

ComplexKey.prototype.toString = function() {
    return this.a + ':' + this.b;
}

var o = {};
o[new ComplexKey(1,2)] = 'x';
o[new ComplexKey(3,4)] = 'y';

结果:

o = {
    '1:2': 'x',
    '3:4': 'y'
}