arrays - 配列以外のランダムアクセスをサポートする他のデータ構造は何ですか?

Question

ランダムアクセスをサポートする他のデータ構造があるかどうかを考えようとしています(つまり、一定時間の複雑さ)。配列のみがこの方法で構築されているように見えます。

注: 配列の上にデータ構造を構築することはできません

Answer 1

ハッシュ テーブルは、キーを指定したランダム アクセスも可能にします。したがって、配列とは対照的に、それらはキーベースであり、インデックスベースではありませんが、特定の要素への O(1) アクセスを許可します。

Answer 2

最終的には、「配列」の意味によって異なります。RAMはバイトの大きな配列です（技術的にはバイトの大きな配列に加えて、それらを1、2、（ほとんど常に）4、（場合によっては）8バイトのブロックで読み取るためのオーバーロードされたメソッドであり、常に機能するとは限りませんその番号と「整列していない」バイトから読み込もうとすると、うまくいきます（または完全に機能しません）。したがって、すべてが配列の上に構築されます。

「配列」とは、「私が使用している言語が配列を呼び出す構造と、その配列に基づくその言語のすべての構造」のみを意味する場合、単純に (C コードで)mallocメモリのスラブを使用することができます。配列に似た方法 (そしておそらくその上にハッシュテーブルを構築します)。キーワードは「似ている」です。

コンピューターの MMU を使用してハッシュ テーブルをエミュレートするためVirtualAllocに (Windows では、 Linux では)使用できる十分な仮想アドレス空間が与えられます。mmapそれは非常に高価で役に立たないでしょう:-)そして、私はそれを別の名前の配列（「スパース」配列）であるとまだ考えています。

Answer 3

リストや辞書が思い浮かびます。辞書はキーと値のペアであるため、「より」ランダム アクセスに適しています。