NSSet implementation

问题:

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?

回答1:

Well, as Bavarious pointed out in a comment, Apple's actual CoreFoundation source is open and available for your perusal too. NSSet is implemented on top of CFSet, whose code is generated (as is that of CFDictionary) from a hash table template, using CFBasicHash to 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 as CFBasicHashAddValue; 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.)

回答2:

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.

回答3:

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 in CFArray.h (equivalent for NSArrays), 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 NSString and NSMutableString, NSArray and NSMutableArray, and NSDictionary and NSMutableDictionary (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.