Swift字典是否为性能编入索引？即使是外来类型（UUID）？

一尘不染

swift

我想构造一些数组，以便快速搜索。如果我使用这样的东西：

let dictionary: [Int:Int] = [:]
for i in 0 ..< 10000000 {
    dictionary[i] = 0
}

查询：

dictionary[n] == nil

在对数时间内执行？

如果是，其他类型是否相同：浮点，双精度，字符串。

最后，我需要它与UUID类型配合使用，是否可以使用？

阅读 222

2020-07-07

共1个答案

一尘不染

Swift的Dictionary实现是通过哈希表实现的，因此，假设哈希算法良好，查找通常会在O（1）时间内完成。正如@rmaddy所说，这意味着密钥的类型主要是无关紧要的-真正重要的是密钥是否具有的良好实现hashValue，对于标准库类型，您完全不必担心。

哈希表查找的最坏情况时间复杂度（假定最大
哈希冲突）取决于哈希表如何解决冲突。在的情况下Dictionary，可以使用两种存储方案，本机存储或可可存储。

在正常使用中，您可以期望Dictionary的后备存储为NativeStorage。

[…]

本机存储是具有开放式寻址和线性探测功能的哈希表。桶阵列形成一个逻辑环（例如，一条链可以绕着桶阵列的末端缠绕到其开头）。

因此，最坏情况下的查找时间复杂度为O（n），就好像每个元素都具有相同的哈希值一样，潜在地，必须搜索每个元素才能确定表中是否存在给定的元素。

对于可可存储，使用_CocoaDictionaryBuffer包装器来包装NSDictionary。不幸的是，尽管它是Core
Foundation的对应CFDictionary头文件指出：

对于当前和将来的任何实现，字典中的值的访问时间均保证为最差O（lg N）

（听起来好像它使用平衡的二叉树来处理冲突。）

2020-07-07