swift - Swift 字典是否为性能建立了索引？即使是外来类型(UUID)？

Question

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

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

请问:

dictionary[n] == nil

以对数时间执行？

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

最后，我需要它来处理 UUID 类型，它会起作用吗？

Answer 1

Swift 的 Dictionary 是用 hash table 实现的，因此假设一个好的散列算法，查找通常会在 O(1) 时间内完成。作为@rmaddy says ，因此这意味着 key 的类型主要是无关紧要的——唯一真正重要的是它是否很好地实现了hashValue。 ，对于标准库类型，您根本不必担心。

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

来自 HashedCollections.swift.gyb :

In normal usage, you can expect the backing storage of a Dictionary to be a NativeStorage.

[...]

Native storage is a hash table with open addressing and linear probing. The bucket array forms a logical ring (e.g., a chain can wrap around the end of buckets array to the beginning of it).

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

对于 Cocoa 存储，使用 _CocoaDictionaryBuffer 包装器来包装 NSDictionary。不幸的是，我找不到任何关于它是如何实现的文档，尽管它是 Core Foundation 对应的 CFDictionary's header file指出:

The access time for a value in the dictionary is guaranteed to be at worst O(lg N) for any implementation, current and future

(这听起来像是使用平衡二叉树来处理冲突。)