NSSet实现

Question

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

Answer 1

正如巴伐利亚在一条评论中指出的那样，苹果CoreFoundation的真正来源也是open and available for your perusal。NSSet是在CFSet之上实现的，它的代码是从一个哈希表模板生成的(与CFDictionary一样)，使用CFBasicHash来完成这项工作。

易变性和不可变性之间的区别似乎是结构中的标志问题(CFBasicHash.h的第91行)，根据我的理解，到目前为止只影响对CFBasicHashAddValue等函数的调用；有一个简单的可变性检查。然而，关于两者之间的复制/保留行为，Cobbal似乎是正确的(我只是还没有读到这一点)。

之前：

当我想知道实现细节时，我发现偶尔细读GNUstep源代码是很有趣的，也是很有教育意义的。当然，它们根本不能保证像苹果那样实现，但在某些情况下它们可能是有帮助的。他们的基础版本：http://gnu.ethz.ch/debian/gnustep/gnustep-base-1.20.0/Headers/Foundation/ (我希望这是最新的版本。如果没有，请有人纠正我。)

Answer 2

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

Answer 3

我发现this link是你问题的一个有趣的答案。苹果的数据结构(NSArray、NSSet、NSDictionary等)不是以直接和“标准的方式”实现的。在大多数情况下，它们的执行方式与任何其他set的执行方式相同，但总的来说，它们会自动优化以获得最佳性能。所以，事实上，很难说。虽然苹果提供了关于CFArray.h (相当于NSArray)中数组效率的文档，但它没有提供关于集合效率的文档，尽管您可以自由地浏览/System/Library/Frameworks/CoreFoundation.framework/Headers/以查看其他数据结构实现。

此外，必须区分set和它的可变对应物，就像区分NSString和NSMutableString、NSArray和NSMutableArray以及NSDictionary和NSMutableDictionary (等等)一样。对于数据结构和字符串(以及少数其他类)，Apple提供了类的“只读”版本以保持通用性，以及用于操作的标准“可变”副本。这只是苹果的标准做法。