使用"in"属性检查对象中是否存在某个键的时间复杂度

Question

使用in属性检查对象中是否存在一个键的时间复杂度是多少：

示例：

var obj = {
    "key1": "value1",
    "key2": "value2",
    "key3": "value3",
    ...
}

if("key1" in obj)

- aRvi

---

平均 O(1)，这是一个哈希表。唯一可能出现的问题是在哈希冲突攻击下，但这并不是日常情况，除非你正在处理金融核心代码例程。 - ASDFGerte

Answer 1

这是来自V8设计文档。

大多数JavaScript引擎使用类似字典的数据结构作为对象属性的存储方式 - 每次属性访问都需要动态查找以解析属性在内存中的位置。这种方法使得在JavaScript中访问属性通常比在Java和Smalltalk等编程语言中访问实例变量要慢得多。在这些语言中，实例变量位于由编译器确定的固定偏移量上，因为对象的类定义了固定的对象布局。访问只是一个内存加载或存储的问题，通常只需要一条指令。

为了减少访问JavaScript属性所需的时间，V8不使用动态查找来访问属性。相反，V8在幕后动态创建隐藏类。[...] 在V8中，当添加新属性时，对象会更改其隐藏类。

因此，基本上即使JavaScript引擎使用类似字典的数据结构，检查对象中的键也将具有O(1)的时间复杂度，因为在字典中平均访问一个键的时间复杂度也是O(1)。

- Saar Davidson