私は宿題として、次のようなアルゴリズム入門演習を与えられました。11.1-3
格納された要素のキーを区別する必要がなく、要素がサテライト データを持つことができる直接アクセス テーブルを実装する方法を提案してください。3 つの辞書操作 (挿入、削除、検索) はすべて O(1) 時間で実行する必要があります。Delete は、キーではなく、削除するオブジェクトへのポインタを引数として取ることを忘れないでください。
Insert は問題ありません。テーブル内の適切な場所にリンク リストを作成し (存在しない場合)、それに要素を追加するだけです。キーが与えられた検索は、キーに一致する要素のいずれかを返すことができるため、テーブル内の一致するリストの先頭を返す必要があることを意味します。
私の問題は削除操作にあります。リンクされたリスト内のノードへのポインターを追加するようにオブジェクトを変更すると、O(1)で削除できますが、オブジェクトを変更できるかどうかはわかりません。指定されたオブジェクトを変更せずにこれを行う方法はありますか?
これはコーメンの本からの質問ですか？私が理解しているように、その本の前の段落を読んで、直接アクセス テーブルに保存するオブジェクトは「あなたの」オブジェクトです。したがって、あなたが示唆するように、各リスト要素がユーザーのオブジェクトへのポインターを持つテーブルに、二重にリンクされたリストへのポインターを格納できます。次に、ディクショナリの SEARCH 操作によってリスト要素が返されます。ユーザーは、オブジェクトを取得するためにさらに手順を実行する必要があります。同様に、DELETE 操作は、リスト要素へのポインタを取ります。
それは理にかなっていますか？宿題を台無しにしたくない！
衛星データを利用して、マッピングすることができると思います。次に、それは一種の2レベルのハッシュテーブルです。DELETE操作に関しては、最初に主キーを使用します。また、主キーが重複している場合は、二次キーを使用してオブジェクトを取得します。したがって、合計時間はまだO（1）です。
ハッシュテーブルは、特定のポイントまで機能します。衝突が発生し始めると、O(1+k/n) になります。ここで、k はキーの数、n はテーブル サイズです。スケジュールされたハッシュのサイズ変更と再ハッシュを行うと、これを回避できる場合があります。挿入、削除、または検索中には発生しないため、効率の評価に影響するかどうかはわかりません。
オブジェクトを変更しないことによる削除は、ハッシュ参照ポインターを null に設定するだけで実現できます。オブジェクトへの直接の変更は行われませんが、オブジェクト コンテナーへの変更が行われます。
あなたが与えている制限のほとんどについて、それらを回避するために特定の方法でハッシュテーブルを実装できると思います。ハッシュ テーブルの実装方法の詳細については、http://en.wikipedia.org/wiki/Hash_table#Performance_analysisを参照してください。
最も重要な部分..「格納された要素のキーを区別する必要がない直接アクセス テーブルの実装」と「O(1) 時間での辞書操作」。
要素が等しい場合、O（1）時間では挿入もできません（Qが要素を区別する必要はないと言っているように）。
部分を削除するには、特定のオブジェクトに到達するためのキーとオブジェクトを取得し、特定のオブジェクトに到達するために衛星データからもキーを想定する必要があります。
上記の 2 つのアイデアだけが O(1) 時間に意味があると思います。