Swift字典键值的查找时间复杂度

SEO

Swift Dictionary Keys lookup time complexity contains O(1) O(n) constant time

太长不看

先说结论，下面两种访问字典键值/查找一个键值是否存在于字典中的方法，时间复杂度同为amortized O(1)。

if d["key"] != nil {
    // ...
}
if d.keys.contains("key") {
    // ...
}

细节

在Swift 4.0也就是大约2019年以前，使用第二种方法时，查找字典键值的时间复杂度为O(n)。因为当时 Dictionary.Keys 只是一个普通的符合 Collection 协议的集合。大家发现语言里存在这个问题，会导致下标访问和 contains 的时间复杂度不同，不符合预期，因此提出了如下提议

• 0154 - Provide Custom Collections for Dictionary Keys and Values

这个提议的具体内容就是用自定义的类型 Keys 和 Values 代替默认生成的符合 Collection 协议的集合，从而实现一些自定方法，以提高随机查找的效率。

由于字典、集合等（哈希）散列数据结构的实现，多采用“不够就再扩容”的思想，因此这个方法的最坏时间复杂度并非常数时间O(1)，而是线性时间 n ；但均摊分析amortized下的时间复杂度仍是O(1)。

⚠️ 需要注意的是，如果嵌套了以前 cocoa 中的 NSDictionary 类型，则时间复杂度不再是一个确定的值。

参考资料

• https://forums.swift.org/t/does-dictionary-keys-contains-have-o-1-time-complexity/21647/14
• https://stackoverflow.com/questions/28129401
• https://github.com/apple/swift/blob/main/stdlib/public/core/Dictionary.swift