對於大型NSDictionary，objectForKey是否緩慢？

Question

1. 假設我們有非常大的的NSDictionary，當我們要調用objectForKey方法，它將使在覈心地段操作來獲得價值？或者它會直接指向內存中的值？
2. 它是如何工作在覈心？

Answer 1

的Collections Programming Topics for Core Foundation（你應該看看，如果你想知道更多）的CFDictionary款規定：

一個字典的該CFDictionary的對象類型是基於散列的 集合，其鍵用於訪問它的值是任意的，程序定義的數據片段（或指向數據的指針）是 。雖然密鑰 通常是一個字符串（或者在Core Foundation中是一個CFString對象），但它可以是任何可以放入指針大小的東西 - 一個整數，一個對Core Foundation對象的引用，甚至一個指針到數據 結構（不太可能如此）。

這是維基百科不得不說的哈希表：

理想情況下，哈希函數應該映射每個可能的密鑰，以獨特的 插槽指數，但這個理想在實踐中很少能夠實現（除非 散列鍵是固定的;也就是說，新條目在創建之後從不添加到表 ）。相反，大多數散列表設計假設散列衝突 - 映射到相同散列值的不同鍵 - 將會發生並且必須以某種方式適應。在尺寸良好的散列表 表中，每次查找的平均成本（指令數）爲 ，與表中存儲的元素數無關。許多散列表設計還允許以每 操作的恆定平均（實際上，攤銷）成本任意插入和刪除 鍵值對。

因此，性能取決於散列的質量。如果它是好的，那麼訪問元素應該是O（1）操作（即不依賴於元素的數量）。

編輯：

事實上進一步閱讀的集合編程的核心基礎課題後，蘋果給出了一個回答你的問題：

在一個CFDictionary對象的值的訪問時間肯定 對於任何實現都是最差O（logN），但通常是O（1） （恆定時間）。插入或刪除操作通常也在 恆定時間，但在最壞的情況下是O（N * log N）。通過密鑰訪問值的速度比直接訪問值要快 。 字典傾向於使用比具有相同數量值的數組更多的內存。

Answer 2

NSDictionary本質上是一個哈希表結構，因此查找的Big-O是O（1）。但是，爲了避免重新分配（並且要實現O（1））的複雜性，您應該使用dictionaryWithCapacity:創建一個與您的數據集的大小相適應的新字典。