ios - 大型 NSDictionary 的 objectForKey 是否慢？

Question

1. 假设我们有一个非常大的NSDictionary，当我们想调用objectForKey方法时，它会在核心中做很多操作来获取值吗？还是会直接指向内存中的值？
2. 它在核心中是如何运作的？

Answer 1

Collections Programming Topics for Core Foundation 的 CFDictionary 部分(如果您想了解更多信息，您应该查看)指出:

A dictionary—an object of the CFDictionary type—is a hashing-based collection whose keys for accessing its values are arbitrary, program-defined pieces of data (or pointers to data). Although the key is usually a string (or, in Core Foundation, a CFString object), it can be anything that can fit into the size of a pointer—an integer, a reference to a Core Foundation object, even a pointer to a data structure (unlikely as that might be).

这是维基百科关于哈希表的说法:

Ideally, the hash function should map each possible key to a unique slot index, but this ideal is rarely achievable in practice (unless the hash keys are fixed; i.e. new entries are never added to the table after it is created). Instead, most hash table designs assume that hash collisions—different keys that map to the same hash value—will occur and must be accommodated in some way. In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at constant average (indeed, amortized) cost per operation.

因此，性能取决于哈希的质量。如果它很好，那么访问元素应该是一个 O(1) 操作(即不依赖于元素的数量)。

编辑:

事实上，在进一步阅读了 Core Foundation 的 Collections Programming Topics 之后，apple 给出了您问题的答案:

The access time for a value in a CFDictionary object is guaranteed to be at worst O(log N) for any implementation, but is often O(1) (constant time). Insertion or deletion operations are typically in constant time as well, but are O(N*log N) in the worst cases. It is faster to access values through a key than accessing them directly. Dictionaries tend to use significantly more memory than an array with the same number of values.