ふと気になったので調べてみたところ、以下のリンクを見つけた。
どうやら実装としてはハッシュテーブルらしい。だから、要素の挿入、削除、検索が一定時間でできる。
なんでそんなことがわかるかというと、NSSet のC言語実装である CFSet が CFHashTable というハッシュテーブルを使って書かれているから。
実は CoreFoundation のソースコードは公開されていて、その一部である CFSet のソースコードも見ることができる。
CFSet のメソッドを見ていると、NSSet のどのメソッドと対応しているか、それとなくわかる。気になる実装を軽く眺めてみるだけでも楽しいかも。