在多大深度上，对对象文字的搜索变得比O(1）慢

At What Depth Does The Search of An Object Literal Become Slower Than O(1)?

本文关键字：搜索 深度 文字 对象      更新时间：2023-09-26

代码：

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(慢？

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

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

一个单独的查找应该在O(1(中，至少在"典型"情况下是这样。字典通常被实现为哈希表，理论上，如果所有键都具有相同的哈希值，则哈希表可能降级为O(N((其中N是字典中的键数(。

相关文章：