CFDictionary的计算复杂度

Question

我在调查核心基金会和CFDictionary，在苹果文档中我发现了这个，

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

令我惊讶的是，在CFDictionary源，我发现了这个

对于当前和未来的任何实现，字典中的值的访问时间在最坏的情况下都是O(N)，但通常是O(1) (恒定时间)。插入或删除操作通常也是恒定时间，但在某些实现中最坏的情况是O(N*N)。通过键访问值比直接访问值更快(如果存在这样的操作)。字典将倾向于比具有相同值的数组使用更多的内存。

为什么会有这么大的差别？还是我找错地方了？

编辑:在苹果OpenSource浏览器中，为什么有那么多文件夹看起来像不同版本的Core，是吗？其中哪一个是最新的/相关的？

Answer 1

“在某些实现中”因为您有源代码，所以您可以轻松地检查实现的最坏情况是什么。对于最坏的情况，假设字典中的每个对象都返回0 :-)的哈希值。)

顺便说一下。最坏的情况将发生在哈希表满并被完全重建时。这就是为什么您在摊销时间使用，而不是在最坏的时间，除非最坏的时间，一个插入是重要的。