古典的な O(1) ランダム アクセス データ構造は配列です。ただし、配列は、使用されているプログラミング言語に依存しており、保証された連続メモリ割り当てをサポートしています (配列は、ベースの単純なオフセットを取得して任意の要素を見つけることができることに依存しているため)。
これは、これを実装の詳細として残すのではなく、言語がメモリが連続しているかどうかに関するセマンティクスを持たなければならないことを意味します。したがって、O(1) のランダム アクセスを持ちながら、継続的なストレージに依存しないデータ構造を持つことが望ましい場合があります。
そのようなことはありますか？
キーの長さが定数 K に制限されているトライはどうでしょうか (たとえば、32 ビット整数をインデックスとして使用できるように 4 バイト)。その場合、ルックアップ時間は O(K) になります。つまり、非連続メモリでは O(1) になります。私には合理的に思えます。
複雑さのクラスを思い出して、すべての big-O には定数係数、つまり O(n) + C があることを忘れないでください。このアプローチでは、C は実際の配列よりもはるかに大きくなります。
編集：実際、今考えてみると、Aが「アルファベット」のサイズであるO（K * A）です。各ノードには、最大 A 個の子ノードのリストが必要です。これは、リンクされたリストである必要があり、実装を非連続に保つ必要があります。しかし、A は依然として一定であるため、O(1) のままです。
実際には、連続したストレージを使用する小さなデータセットの場合は問題ありません。大きなデータセットの場合、O(log(n)) は O(1) と同じくらい優れています。一定の要因はむしろ重要です。
実際、非常に大きなデータセットの場合、O(root3(n)) ランダム アクセスは、3 次元の物理宇宙で得られる最高のものです。
編集: log10 と O(log(n)) アルゴリズムが O(1) の 100 万要素の 2 倍の速さであると仮定すると、それらが均等になるには 1 兆要素が必要であり、O(1 ) アルゴリズムは 2 倍高速になり、地球上で最大のデータベースよりも高速になります。
現在および予測可能なすべてのストレージ テクノロジでは、データの各要素を格納するために特定の物理領域 (v と呼びましょう) が必要です。3 次元宇宙では、これは n 要素の場合、要素の少なくとも一部とルックアップを行う場所との間に root3(n*v*3/4/pi) の最小距離があることを意味します。ボリューム n*v の球。そして、光の速度は、これらの要素へのアクセス時間に root3(n*v*3/4/pi)/c の物理的な下限を与えます - そしてそれは O(root3(n)) です。あなたが使う。
ハッシュ表？
編集:は単なるシンタックス シュガーであるO(1)ため、配列はルックアップです。言い換えると、 を取得するには、すべての要素への直接ポインタまたは簡単に計算できるポインタが必要です (検索しようとしているメモリがプログラム用であるという感覚が必要です)。すべての要素へのポインターがない場合、連続したメモリがなければ、簡単に計算できるポインターを持つことはできません (そして、メモリが予約されていることがわかります)。a[i]*(a+i)O(1)
もちろん、各ルックアップのメモリアドレスが単に*(a + hash(i))配列で行われていない、つまり、そのような制御がある場合、指定されたメモリ位置で動的に作成されている Hashtable 実装を持つことは (ひどい場合) もっともらしいです..ポイントは最も効率的な実装は基になる配列になりますが、一定時間のルックアップを取得する WTF 実装を実行するために、他の場所でヒットすることは確かにもっともらしいです。
Edit2:私のポイントは、配列は構文糖衣であるため、連続したメモリに依存しているということですが、Hashtable は、必要なためではなく、最適な実装方法であるため、配列を選択します。もちろん、DailyWTF を読みすぎているに違いありません。C++ の配列インデックス演算子をオーバーロードして、同じ方法で連続したメモリなしでそれを行うことを想像しているためです..
ハッシュテーブルとは別に、2 レベルの配列の配列を使用できます。
したがって、O(1) のランダム アクセスを持ちながら、継続的なストレージに依存しないデータ構造を持つことが望ましい場合があります。
そのようなことはありますか？
いいえ、ありません。証拠のスケッチ:
連続ブロック サイズに制限がある場合は、データ項目に到達するために間接参照を使用する必要があることは明らかです。ブロックサイズが制限された固定の間接深度では、固定サイズのグラフのみが得られます (ただし、そのサイズは深度に応じて指数関数的に増加します)。そのため、データセットが成長するにつれて、間接深度は増加します (対数的にのみ、O(1) ではありません)。 ）。
他の人が指摘した有限の深さへの明らかなネストされた構造は別として、私はあなたが説明したプロパティを持つデータ構造を認識していません。適切に設計された対数データ構造を使用すると、メイン メモリに収まる任意のデータへの高速アクセス時間で非連続メモリを使用できるという他の意見を共有します。
私は興味深い、密接に関連したデータ構造を認識しています:
このデータ構造は、それを使用して大きなファイルの内容全体を表すことができるほど効率的であり、実装は必要でない限りディスク上にビットを保持するのに十分賢いです。
確かに、ここで話しているのは、連続したメモリストレージ自体ではなく、含まれているデータ構造にインデックスを付ける機能です。動的配列またはリストを、メモリ内の他の場所にある各要素の実際の内容を持つポインターの配列として内部的に実装するのが一般的です。これを行う理由はいくつかあります。特に、各エントリを異なるサイズにできるようにするためです。他の人が指摘しているように、ほとんどのハッシュテーブルの実装もインデックス作成に依存しています。インデックス作成に依存しない O(1) アルゴリズムを実装する方法は思いつきませんが、これは少なくともインデックスの連続したメモリを意味します。
ちょっとした好奇心:ハッシュ トライは、たまたま衝突しないトライ ノードのキー配列をメモリにインターリーブすることでスペースを節約します。つまり、たとえば、ノード 1 にキー A、B、D があり、ノード 2 にキー C、X、Y、Z がある場合、両方のノードに同じ連続したストレージを同時に使用できます。さまざまなオフセットと任意の数のノードに一般化されています。Knuth は、 Literate Programmingの最も一般的な単語プログラムでこれを使用しました。
したがって、これにより、すべてのノードに連続ストレージをまとめて使用するにもかかわらず、連続ストレージを予約することなく、任意のノードのキーに O(1) アクセスできます。
分散ハッシュ マップには、このようなプロパティがあります。実際には、完全ではありませんが、基本的にハッシュ関数は、検索するストレージ バケットを示します。そこでは、おそらく従来のハッシュ マップに依存する必要があります。ストレージ領域/ノードを含むリスト(分散シナリオ)は、通常、ハッシュマップ(本質的にハッシュテーブルのハッシュテーブルにする)であるため、要件を完全にカバーするわけではありませんが、他のものを使用することもできますたとえば、ストレージ領域の数がわかっている場合などです。
編集:
少し忘れて、おそらく異なるレベルに異なるハッシュ関数を使用したいと思うでしょう。そうしないと、各ストレージ領域内に多くの同様のハッシュ値が作成されます。
データ全体ではなく、データへの参照配列のみにメモリ ブロックを割り当てることができます。これにより、必要な連続メモリの長さが劇的に減少します。
別のオプションとして、要素をキーで識別でき、これらのキーを使用可能なメモリ位置に一意にマップできる場合、すべてのオブジェクトを連続して配置せず、オブジェクト間にスペースを残すことができます。これには、メモリ割り当てを制御する必要があるため、1 番目の優先順位のオブジェクトにそのメモリの場所を使用する必要がある場合でも、空きメモリを配布し、2 番目の優先順位のオブジェクトを別の場所に再配置できます。ただし、サブディメンションではまだ連続しています。
あなたの質問に答える一般的なデータ構造に名前を付けることができますか? いいえ。