对于大 NSDictionary 来说，objectForKey 慢吗？

发布于 2024-12-15 09:42:44 字数 149 浏览 1 评论 0原文

假设我们有很大的NSDictionary，当我们要调用objectForKey方法时，它会在核心中进行大量操作来获取值吗？还是直接指向内存中的值？
它在核心中是如何工作的？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

鸩远一方 2024-12-22 09:42:44

核心基础的集合编程主题<的 CFDictionary 部分/a> （如果你想了解更多，你应该查看）指出：

字典（CFDictionary 类型的对象）是基于哈希的
用于访问其值的键是任意的集合，
程序定义的数据块（或指向数据的指针）。虽然关键
通常是一个字符串（或者，在 Core Foundation 中，是一个 CFString 对象），它
可以是任何可以容纳指针大小的东西——整数、
对 Core Foundation 对象的引用，甚至是指向数据的指针
结构（不太可能）。

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

理想情况下，哈希函数应将每个可能的键映射到唯一的
槽索引，但这种理想在实践中很少能实现（除非
哈希键是固定的；即新条目永远不会添加到表中
创建后）。相反，大多数哈希表设计都假设
哈希冲突（映射到相同哈希值的不同键）将
发生并且必须以某种方式进行调节。在维度良好的哈希中
表中，每次查找的平均成本（指令数）为
与表中存储的元素数量无关。许多散列
表设计还允许任意插入和删除
键值对，以恒定的平均（实际上是摊销）成本
操作。

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

编辑：

事实上，在进一步阅读核心基础的集合编程主题之后，苹果给出了您问题的答案：

CFDictionary 对象中的值的访问时间保证
对于任何实现来说，最坏的情况是 O(log N)，但通常是 O(1)
（恒定时间）。插入或删除操作通常在
时间也是恒定的，但在最坏的情况下是 O(N*log N)。这是
通过键访问值比直接访问它们更快。
字典往往比数组使用更多的内存
相同数量的值。

The CFDictionary section of the Collections Programming Topics for Core Foundation (which you should look into if you want to know more) states:

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).

This is what wikipedia has to say about hash tables:

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.

The performance therefore depends on the quality of the hash. If it is good then accessing elements should be an O(1) operation (i.e. not dependent on the number of elements).

EDIT:

In fact after reading further the Collections Programming Topics for Core Foundation, apple gives an answer to your question:

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.

回复收藏 0 原文