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 的时间复杂度不同，不符合预期，因此提出了如下提议
这个提议的具体内容就是用自定义的类型 Keys 和 Values 代替默认生成的符合 Collection 协议的集合，从而实现一些自定方法，以提高随机查找的效率。
由于字典、集合等（哈希）散列数据结构的实现，多采用“不够就再扩容”的思想，因此这个方法的最坏时间复杂度并非常数时间O(1)，而是线性时间 n ；但均摊分析amortized下的时间复杂度仍是O(1)。
⚠️ 需要注意的是，如果嵌套了以前 cocoa 中的 NSDictionary 类型，则时间复杂度不再是一个确定的值。
Top comments (0)