javascript - 对象字面量的搜索在多深时会变得比 O(1) 慢？

Question

代码：

var PhoneNumbers = {
    "J Smith": 7125551212,
    "A Johnson": 4023331212
}

alert(PhoneNumbers["J Smith"]); // 7125551212

此查找的速度为 O(1)。在什么深度，速度变得比 O(1) 慢？

例如：

var PhoneNumbers = {
    "J Smith": {
         age: 40,
         phoneNumber: 7125551212
    },
    "A Johnson": {
         age: 40,
         phoneNumber: 7125551212
    }
}

alert(PhoneNumbers["J Smith"]["phoneNumber"]); // 7125551212

第二个例子的速度是否比 O(1) 慢？

Answer 1

嵌套字典查找的复杂度是 O(N)，其中 N 是嵌套的深度。

任何特定查找操作（固定对象、固定键）的复杂性都是恒定的（即 O(1)）：它总是花费相同的时间。

至少在“典型”情况下，单个查找应该在 O(1) 中。字典通常以哈希表的形式实现，理论上，如果所有键具有相同的哈希值，它可以降级到 O(N)（其中 N 是字典中的键数）。