ios - セット内の NSString を効率的に検索する

Question

NSStringメモリ内の何千ものオブジェクトのセットを考えてみましょう。

NSStringセット内の特定のものを検索する最も効率的な方法は何ですか? 使用するだけでNSDictionary十分ですか？それとも、NSSetの検索が O(1) であることが保証されていますか (そう言っているドキュメントが見つかりませんでした)?

そして、同じ戦略がNSDataオブジェクトに適用されるでしょうか?

Answer 1

このページには、セットに関する次の注意事項が表示されます。

注: セット内のオブジェクトに適切なハッシュ関数がある場合、要素へのアクセス、要素の設定、および要素の削除には一定の時間がかかります。貧弱なハッシュ関数 (ハッシュの衝突が頻繁に発生する関数) では、これらの操作に最大で線形時間がかかります。Foundation の一部である NSString などのクラスには、優れたハッシュ関数があります。

したがってNSString、上記に基づいて一定の時間を期待できます。

Answer 2

NSSet実装でハッシュ テーブルを使用し、ハッシュの衝突にあるすべての要素が等しいかどうかをテストします。したがって、パフォーマンスはその要素のハッシュ効率に直接関係しています。