NSSet 实现
这个问题只是出于好奇，但是 NSSet 是如何实现的呢？它背后的数据结构是什么？添加和删除元素的访问时间是多少？如果我不得不猜测，我会说它是某种哈希表/字典数据结构，但在这种情况下为什么要区分 NSSet 和 NSMutableSet 呢？
This question is just out of curiosity but, how is NSSet implemented? What data structure is behind it and what are the access times for adding and removing elements? If I had to guess, I'd say it was some sort of hashtable/dictionary data structure, but in that case why differentiate between NSSet and NSMutableSet?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
好吧，正如 Bvarious 在评论中指出的那样，Apple 的实际 CoreFoundation 源代码是开放并可供您细读也。
NSSet是在CFSet< 之上实现的/a>，其代码是从哈希表模板生成的（与CFDictionary一样），使用CFBasicHash来完成这项工作。可变性和不变性之间的区别似乎是结构中标志的问题（<的第91行） code>CFBasicHash.h），从我目前的阅读来看，仅影响对诸如
CFBasicHashAddValue等函数的调用；有一个简单的可变性检查。然而，科巴尔关于两者之间的复制/保留行为的说法似乎是正确的（我只是还没有读到那么远）。以前：
当我想了解实现细节时，我发现偶尔仔细阅读 GNUstep 源代码既有趣又具有教育意义。当然，它们根本不能保证像苹果那样实施，但在某些情况下它们可能会有所帮助。他们的基金会版本： http://gnu.ethz.ch/debian/ gnustep/gnustep-base-1.20.0/Headers/Foundation/ （我希望这是最新版本。如果不是，请有人纠正我。）
Well, as Bavarious pointed out in a comment, Apple's actual CoreFoundation source is open and available for your perusal too.
NSSetis implemented on top ofCFSet, whose code is generated (as is that ofCFDictionary) from a hash table template, usingCFBasicHashto do the work.The difference between mutablility and immutability seems to be the matter of a flag in the structure (line 91 of
CFBasicHash.h), and from my reading so far just affects calls to functions such asCFBasicHashAddValue; there's a simple check for the mutability. It seems likely, however, that Cobbal is right about the copy/retain behavior between the two (I just haven't read that far yet).PREVIOUSLY:
I find it interesting and educational occasionally to peruse the GNUstep sources when I'm wondering about implementation details. They are, of course, not at all guaranteed to be implemented the way that Apple did it, but they can be helpful in some cases. Their version of Foundation: http://gnu.ethz.ch/debian/gnustep/gnustep-base-1.20.0/Headers/Foundation/ (I hope that's the most recent version. If not, someone please correct me.)
回答问题的后半部分：拥有不可变版本的一个好处是它允许一种非常快速的复制方法，只需调用retain。
To answer the second half of your question: one benefit of having a non-mutable version is that it allows for a very fast copy method that simply calls retain.
我发现此链接是您问题的有趣答案。 Apple 的数据结构（
NSArray、NSSet、NSDictionary等）并不是以简单且“标准的方式”实现的。在大多数情况下，它们的执行方式与任何其他集合的执行方式相同，但总的来说，它们会自动优化以获得最佳性能。所以，事实上，这很难说。虽然 Apple 在 CFArray.h（相当于 NSArray）中提供了有关数组效率的文档，但它没有提供有关集合效率的此类文档，尽管您可以自由选择浏览/System/Library/Frameworks/CoreFoundation.framework/Headers/以查看其他数据结构实现。此外，集合和它的可变对应物之间必须有区别，就像
NSString和NSMutableString、NSArray之间有区别一样。和NSMutableArray、NSDictionary和NSMutableDictionary（等等）。对于数据结构和字符串（以及少数其他类），Apple 提供类的“只读”版本以保留通用性，以及用于操作的标准“可变”对应项。这只是苹果公司的标准做法。I find this link to be an interesting answer to your question. Apple's data structures (
NSArray,NSSet,NSDictionary, etc.) are not implemented in a straightforward and "standard way." In most cases, they perform in the same way any other set would perform, but overall, they optimize automatically for the best performance. So, in truth, it's rather difficult to say. While Apple provides documentation on the efficiency of arrays inCFArray.h(equivalent forNSArrays), it offers no such documentation on the efficiency of sets, though you're free to poke around/System/Library/Frameworks/CoreFoundation.framework/Headers/to look through other data structure implementations.In addition, there has to be a distinction between a set and its mutable counterpart, just as there is a distinction between
NSStringandNSMutableString,NSArrayandNSMutableArray, andNSDictionaryandNSMutableDictionary(among others). For data structures and strings (and few other classes), Apple offers 'readonly' versions of classes to retain generality, along with standard 'mutable' counterparts for manipulation. It's simply Apple's standard practice.