objective-c - NSSet 实现

Question

这个问题只是出于好奇，但是，NSSet 是如何实现的？它背后的数据结构是什么，添加和删除元素的访问时间是多少？如果我不得不猜测，我会说它是某种哈希表/字典数据结构，但在那种情况下，为什么要区分 NSSet 和 NSMutableSet？

Answer 1

好吧，正如 Bavarious 在评论中指出的那样，Apple 的实际 CoreFoundation 源代码是开放的，也可供您阅读。NSSet是在 之上实现的CFSet，其代码是CFDictionary从哈希表模板生成的（与 的代码一样），CFBasicHash用于完成工作。

可变性和不变性之间的区别似乎是结构中的一个标志（第 91 行CFBasicHash.h），从我目前的阅读来看，它只会影响对函数的调用，例如CFBasicHashAddValue; 对可变性有一个简单的检查。然而，Cobbal 关于两者之间的复制/保留行为似乎是正确的（我还没有读到那么远）。

以前：当我想知道实现细节时，我发现偶尔细读GNUstep
源代码 很有趣且很有教育意义。当然，它们完全不能保证以 Apple 的方式实现，但在某些情况下它们可能会有所帮助。他们的 Foundation 版本：http: //gnu.ethz.ch/debian/gnustep/gnustep-base-1.20.0/Headers/Foundation/（我希望这是最新版本。如果不是，请有人纠正我。）

Answer 2

回答你问题的后半部分：拥有非可变版本的一个好处是它允许一种非常快速的复制方法，只需调用保留。

Answer 3

我发现此链接是您问题的有趣答案。Apple 的数据结构（NSArray、NSSet、NSDictionary等）不是以直接和“标准的方式”实现的。在大多数情况下，它们的执行方式与任何其他集合的执行方式相同，但总体而言，它们会自动优化以获得最佳性能。所以说实话，还是挺难的。CFArray.h虽然 Apple 提供了关于（等效于s）中数组效率的文档NSArray，但它没有提供关于集合效率的此类文档，尽管您可以随意/System/Library/Frameworks/CoreFoundation.framework/Headers/浏览其他数据结构实现。

此外，集合与其可变对应物之间必须有区别，就像NSStringand NSMutableString、NSArrayandNSMutableArray和NSDictionaryand NSMutableDictionary（以及其他）之间存在区别一样。对于数据结构和字符串（以及少数其他类），Apple 提供了类的“只读”版本以保持通用性，以及用于操作的标准“可变”对应物。这只是 Apple 的标准做法。