x (百万) 個の正の整数があり、それらの値は許容される最大値 (+2,147,483,647) にできます。それらが一意であると仮定すると、ルックアップ集中型プログラムのためにそれらを保存する最良の方法は何ですか.
これまでのところ、整数がマップされたデータ (名前) のキーであるバイナリ AVL ツリーまたはハッシュ テーブルを使用することを考えました。ただし、ハッシュテーブルを使用してそのような大きなキーを大量に実装できるかどうかはわかりません（衝突が発生しやすくなるだけでなく、0.8以上の負荷係数が発生しませんか？）
私の状況に適したデータ構造についてアドバイスをいただけますか
構造の選択は、使用可能なメモリの量に大きく依存します。説明に基づいて、ルックアップが必要であるが、それらをループしたり、最も近いものを見つけたり、その他の同様の操作を行ったりしないと想定しています。
おそらく、バケット化されたハッシュ テーブルが最適です。ハッシュ衝突をバケットに配置し、バケット内にキーと値の個別の配列を保持することで、適切なテーブルのサイズを縮小し、バケットを検索するときに CPU キャッシュの高速化を利用できます。バケット内の線形検索は、二分検索よりも高速になる可能性さえあります!
AVL ツリーは、読み取りが集中するが読み取り専用ではなく、順序付けられた列挙が必要で、最も近い操作や類似の操作を見つける必要があるデータ セットには適していますが、正しく実装するには面倒な作業が必要です。ただし、CPU キャッシュの動作、特にキャッシュを無視する B ツリー アルゴリズムにより、B ツリーを使用するとパフォーマンスが向上する場合があります。
Bツリーを調べましたか？効率は と の間log_m(n)で実行されるlog_(m/2)(n)ため、約 8 ～ 10 を選択mした場合、検索の深さを 10 未満に保つことができるはずです。
Bit Vector 。数値が存在する場合はインデックスが設定されます。各数値の出現回数を持つように微調整できます。Bentley の Programming Pearls に、ビット ベクトルに関する素晴らしいコラムがあります。
メモリが問題にならない場合は、おそらくマップが最善の策です。マップは O(1) です。つまり、検索するアイテムの数を増やしても、値を見つけるのにかかる時間は同じです。
キーが int で、値が名前であるマップ。
最初にハッシュテーブルを試してください。大幅な速度低下なしに非常に高密度であることを許容できるバリアントがいくつかあります (ブレントのバリアントのように)。
32 ビット整数のみを格納する必要があり、関連するレコードを格納する必要がない場合は、ほとんどの C++ ライブラリのように、 a ではsetなく a を使用します。100% になるのを避けるために、4 バイトのレコードに一定のオーバーヘッドと少しのスラックのみを使用します。最悪の場合、「数百万」の数値を処理するには、数十メガバイトが必要になります。大きいですが、手に負えないものはありません。maphash_set
より厳密にする必要がある場合は、単純な配列に並べ替えて格納し、バイナリ検索を使用してフェッチします。O(1) ではなく O(log n) になりますが、「数百万」のレコードの場合、それらのいずれかを取得するのにまだ 20 のステップしかありません。C には がありbsearch()、これは可能な限り高速です。
編集：あなたの質問で、「マップされたデータ（名前）」について話しているのを見ました。それらの名前はユニークですか？それらもメモリ内にある必要がありますか？もしそうなら、それらは間違いなくメモリ要件を支配します。それでも、名前が典型的な英語の単語である場合、ほとんどは 10 バイト以下であり、合計サイズは「数十メガバイト」のままです。おそらく最大 100 メガバイトですが、それでも非常に扱いやすいものです。