2

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

4

2 回答 2

14

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

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

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

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

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

实际上导致：

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

因为字符串转换规则。由于每个对象都转换为[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'
}
于 2012-09-02T19:58:25.907 回答
6

JavaScript 没有“哈希表”。

它的字典是键/值对的集合，但键必须是唯一的。不同之处在于字典的实现并不意味着哈希，尽管出于性能原因，实现内部可能会使用哈希表。

JavaScript 中的所有对象都用作字典（这不包括原始类型，例如string和number）。通常一个空对象用于一个通用的“散列表”：

var o = {};
o[propExpression] = valueExpression;

但是，重要的是：所有属性/键值首先转换为字符串。

因此以下是相同的：

o[true] = 1
o["true"] = 1

遵循 ECMAScript 有点令人困惑，但“知道”属性名称都是字符串的关键部分可以在Property Descriptors中找到：

属性标识符类型用于将属性名称与属性描述符相关联。Property Identifier 类型的值是 (name, descriptor) 形式的对，其中 name 是 String，descriptor 是 Property Descriptor 值。

于 2012-09-02T19:21:21.917 回答