辞書検索対アレイ検索;配列の位置と辞書の割り当て

Question

辞書構造 のルックアップ方法の背景は何ですか？私はそれがどのように実装されているのか？与えられたキーを使って、辞書の値を見つけます。

1）配列検索はO（1）操作であることがわかります。だから、辞書はどうですか？

2）両方が整数であるキー値のペアを格納している場合、そのようなデータとスペースの膨大な量があれば私の心配は好ましいでしょうか？配列または辞書？ たとえば、固定サイズの配列を割り当てることができます。しかし、キーの値のペアは配列全体を占めていない可能性があります。そのサイズは配列の半分であるかもしれません。しかし、特定のキーが現れるかどうかわからないので、配列の割り当ては最大サイズにする必要があります。 私に鍵、値のペア（10,1）、（20,2）、（30,3）があることを明らかにする。だから私は配列を使用する場合、私は3つのエントリを占めるだけで、[30] [2]としてそのサイズを宣言する必要があります。だから、辞書はこの場合より良いでしょう。 30人は100万人になることはできません。他のエントリは配列のメモリを占有しますか？

Answer 1

辞書は、通常、ハッシュマップまたはバイナリツリーという2つの方法で実装されます。

1：辞書がバイナリツリーの場合、検索時間はバイナリ検索であり、したがってO（log n）です。

辞書がハッシュマップの場合、検索時間はO（1）です。 （同じハッシュのキーでO（m）に増える可能性があります）

2：そうですが、この場合は辞書がスペースを使います。辞書検索の余分な時間コストは比較的低くなるでしょう。

ブルームフィルタのようなもので辞書を検索するとさらに改善できます（平均の場合は、ハッシュマップに存在しないオブジェクトです）。

Answer 2

用語dictionaryは非常に一般的であり、あらゆる種類のデータ構造を指すことができます。また、それが順序付けされた辞書であるのか、順不同であるのかは言わなかった。

配列が行く限り、まっすぐなフラット配列はまばらに配置されているとスペースを無駄にします。ただし、マルチレベル配列を実装できます。最初のいくつかのレベルはディレクトリであり、葉レベルだけが小さな配列を持っています。

仮想メモリページテーブルは、このようにしばしば実装されます。

したがって、（16進数）[0x123456]のような配列インデックスがビットマスク操作で[0x12] [0x34] [0x56]に分割される可能性があります。トップディレクトリを選択します。中間ディレクトリへのポインタの配列で、小さなテーブルへのポインタの配列を持ちます。 （実際には、コードはレベルを歩かなければならず、直接索引付けするのではなく、欠落しているディレクトリや表を見なければなりません！全体的な点です。ツリー全体をインスタンス化しないでください）。

正規表現エンジンのUnicode文字セットは、このように、さまざまな状況でいくつかの異なる深さの構造を使用します。

もちろんこれは通常のnew int[foo] C++配列とは関係ありません！もちろん、配列のように見えるクラスの背後に隠れることがあります。