如何在JavaScript中实现哈希表

Question

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

Answer 1

围绕这个问题显然存在很多误解.在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'
}

Answer 2

JavaScript没有"哈希表".

它有字典,它是键/值对的集合,具有Key必须唯一的限制.区别在于Dictionary的实现并不意味着哈希,尽管出于性能原因,Hash表可能会被实现内部使用.

JavaScript中的所有对象都充当字典(这种被排除的原始类型,如string和number).通常,空对象用于通用"哈希表":

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

但是,重要的是:所有属性/键值首先转换为字符串.

因此以下是相同的:

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

通过ECMAScript后面有点令人困惑,但是"知道"属性名称都是字符串的关键部分可以在属性描述符中找到:

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