Swift字典是否为性能编入索引？即使是外来类型（UUID）？ [英] Is Swift dictionary of indexed for performance? Even for exotic types (UUID)?

问题描述

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

I want to construct some arrays that will remain in order to get fast searches. If I use something like this:

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

查询：

dictionary[n] == nil

是在对数时间内执行吗？

be performed in logarithmic time?

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

If yes, is it the same for other types: Float, Double, String.

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

And finally, I need it to work with the UUID type, will it work?

推荐答案

Swift的字典是通过哈希实现的表，因此，假设使用良好的哈希算法，查找通常会在O（1）时间完成。正如 @rmaddy所说的，因此这意味着键的 type 主要是不相关的–真正重要的是它是否具有 hashValue ，对于标准库，您完全不必担心

Swift's Dictionary is implemented with a hash table, therefore lookups will typically be done in O(1) time, assuming a good hashing algorithm. As @rmaddy says, this therefore means that the type of key is mainly irrelevant – the only thing that really matters is whether it has a good implementation of hashValue, which you shouldn't have to worry about at all for standard library types.

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

The worst case time complexity for a hash table lookup (assuming maximal hash collisions) depends on how the hash table resolves the collisions. In the case of Dictionary, two storage schemes can be used, native or Cocoa.

来自 HashedCollections.swift.gyb ：

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

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），就好像每个元素都具有相同的哈希值一样，可能必须搜索每个元素以确定在给定元素中是否存在给定元素。

Therefore the worst case lookup time complexity is O(n), as if each element has the same hash, potentially every element will have to be searched through in order to determine if a given element exists in the table.

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

For Cocoa storage, a _CocoaDictionaryBuffer wrapper is used in order to wrap an NSDictionary. Unfortunately, I cannot find any documentation on how it's implemented, although it's Core Foundation counterpart CFDictionary's header file states that:

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

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

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

(Which sounds like it uses a balanced binary tree in order to handle collisions.)

这篇关于Swift字典是否为性能编入索引？即使是外来类型（UUID）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！