Swift中的DictionaryIndex有什么作用？

Question

根据Swift中Dictionary的头部文档说明:

Key到Value实例的基于哈希的映射。同时也是一个包含键值对但没有定义顺序的集合。

特别需要注意- 没有定义顺序.

有了这个理解，我对这些计算变量(以及相关方法)的理解还不够：

// The position of the first element in a non-empty dictionary.  
var startIndex: DictionaryIndex<Key, Value> { get }

// The collection's "past the end" position.
var endIndex: DictionaryIndex<Key, Value> { get }

这里的“index”是指一个“DictionaryIndex”。然而，关于“DictionaryIndex”的文档有点循环定义：

用于访问“Dictionary ”实例中的键值对。

那么，“DictionaryIndex”的目的究竟是什么？

- JRG-Developer

---

我不确定，“没有定义的顺序”并不意味着随机排序。NSDictionary 对于键有一个定义好的顺序，只是苹果没有记录它是什么，并且将来可能会更改。键按照使字典访问最快的顺序排序（或在NSMutableDictionary的情况下，使修改字典最快的顺序）。 - Abhi Beckert

@AbhiBeckert，你提出了一个有趣的观点。我可以看到按哈希排序可能会使二分查找成为可能。也许幕后还有其他魔法正在发生？对于DictionaryIndex仍然不确定，但感谢您的意见！ :) - JRG-Developer

你可以使用DictionaryIndex对字典进行下标操作（我认为这就是Amit89在刚才被删除的答案中所指的）。例如：if let index = d.indexForKey("key") { let (k, v) = d[index] ; println((k, v)) }。 - Martin R

这里有一个略微相关的问题，关于键和值的顺序（有两个相反的答案 :)）：http://stackoverflow.com/questions/27353434/dictionary-key-value-order。 - Martin R

Answer 1

我们知道，一个Dictionary由键和值组成。每个键都映射到一个值，该值基于一些内部计算。在这里，用于此目的的机制是哈希。 来自维基百科：

哈希表使用哈希函数计算出一个索引，该索引指向存储桶或插槽的数组，从中可以找到正确的值。

考虑一个Dictionary是一个哈希表，它使用某个哈希函数并返回一个类型为DictionaryIndex的对象 - 使用它，您可以直接访问字典中的特定对象。

如果我有错误，请纠正我！

- NightFury

---

我想你的意思是，“每个键都基于一些内部计算映射到一个索引”，对吗？ - JRG-Developer

是的，我想我明白你的意思 - 加上@AbhiBeckert的评论，我认为它是这样工作的：DictionaryIndex表示Dictionary中给定键的基础索引。这允许二进制查找和其他技巧，也许？ :) - JRG-Developer

不是的。在字典中，一个键总是根据某个哈希值（这里是“DictionaryIndex”）映射到一个值。 - NightFury

是的，我同意你上一条评论。我认为这可能是正在发生的事情。 - NightFury

我想内部实现接近于答案/评论中描述的内容。只是我的个人看法：DictionaryIndex 存在是因为 Dictionary 符合 CollectionType 协议，该协议定义了它。此外，没有二进制查找。所有 Dictionary 操作都在 O(1) 中运行（除非它在内部桥接到 NSDictionary）。 - Jakub Vano