是Swift词典的索引性能？即使是异国风情(UUID)？

概述我想构建一些将保留以便快速搜索的数组. 如果我使用这样的东西： let dictionary: [Int:Int] = [:]for i in 0 ..< 10000000 { dictionary[i] = 0} 请问查询： dictionary[n] == nil 在对数时间内执行？ 如果是,对其他类型是否相同：Float,Double,String. 最后,我需要它使用UUID类 我想构建一些将保留以便快速搜索的数组.
如果我使用这样的东西：

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

请问查询：

dictionary[n] == nil

在对数时间内执行？

如果是,对其他类型是否相同：float,Double,String.

最后,我需要它使用UUID类型,它会工作吗？

Swift的字典用 hash table实现,因此假设一个好的散列算法,查找通常在O(1)时间内完成.因此,在 @rmaddy says中,这意味着密钥的类型主要是无关紧要的 – 唯一真正重要的是它是否具有良好的 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.不幸的是,我找不到任何关于它如何实现的文档,尽管它的核心基础对应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

(听起来它使用平衡的二叉树来处理碰撞.)

总结

以上是内存溢出为你收集整理的是Swift词典的索引性能？即使是异国风情(UUID)？全部内容，希望文章能够帮你解决是Swift词典的索引性能？即使是异国风情(UUID)？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。