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

Question

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

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

查询：

dictionary[n] == nil

以对数时间执行？

如果是，其他类型是否相同：Float、Double、String。

最后，我需要它与 UUID 类型一起工作，它会工作吗？

score 21 · Accepted Answer

SwiftDictionary是用一个哈希表实现的，因此假设一个好的哈希算法，查找通常会在 O(1) 时间内完成。正如@rmaddy 所说，这意味着密钥的类型主要是无关紧要的——唯一真正重要的是它是否具有良好的实现hashValue，对于标准库类型，您根本不必担心。

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

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

[...]

本机存储是一个具有开放寻址和线性探测的哈希表。桶数组形成一个逻辑环（例如，一条链可以环绕桶数组的末端到它的开头）。

因此，最坏情况的查找时间复杂度是 O(n)，就好像每个元素都具有相同的散列一样，可能必须搜索每个元素以确定表中是否存在给定元素。

对于 Cocoa 存储，使用_CocoaDictionaryBuffer包装器来包装NSDictionary. 不幸的是，我找不到任何关于它是如何实现的文档，尽管它的 Core Foundation 对应CFDictionary的头文件指出：

对于当前和未来的任何实现，字典中值的访问时间保证在最坏情况下为 O(lg N)

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

score 1 · Accepted Answer

字典和数组是不同的。您谈论数组，但您的代码正在使用字典。您可以设置一组可选的 Int 值并使用您建议的代码。

使用现有代码，您正在从字典中查找键/值对。字典使用散列进行查找，我相信字典查找是在恒定时间内完成的，尽管在快速搜索后我无法确认。

编辑：

检查此链接：

也就是说，数组和字典都可能与O(n•log(n))性能一样糟糕，但通常给出 O(1)。