objective-c - NSOrderedSet を実装するために使用される基本的なデータ構造

Question

NSOrderedSet は、オブジェクトの順序付けのようなハッシュ テーブルと配列の O(1) ルックアップ速度を提供できるようですか? これを達成するために使用されるデータ構造は何ですか? たとえば、ハッシュテーブルと、インデックス i がハッシュテーブル内のオブジェクトに対応するキーを持つ個別の配列の 2 つの組み合わせですか?

Answer 1

Apple がこのデータ構造の実装をどのように選択したかはわかりません。発見する唯一の方法は、財団のフレームワークをリバース エンジニアリングすることです。しかし、これは有用なことではありません。Apple は、更新ごとに実装と基礎となるデータ構造を変更する可能性があります。したがって、本番アプリでこれに依存することは、いつでもアプリを壊す可能性があるため、非常に愚かです.

これを自分で実装したい場合は、ハッシュ テーブルと配列を使用したアプローチが機能します。最善の方法は、オブジェクトを配列に格納し、ハッシュ マップにオブジェクトをキーとする配列インデックスを格納させることです。

もちろん、これをさまざまなパフォーマンス特性で実装する方法は他にもあります。これは、containsObject: テスト O(n) を作成する単なる配列である場合もあれば、objectAtIndex: 操作 O(n) を作成する (オブジェクトをキーとして、インデックスを値として持つ) ハッシュ テーブルである場合もあります。