ネットワークプロトコル（イーサタイプなど）を解析するためのルックアップを実行する配列を作成するとします。このような識別子は2バイトの長さであるため、直接インデックスを使用すると、2 ^ 16セルの配列になります。配列がまばらである可能性が非常に高いため、これは実際の無駄です。配列。
メモリ使用量を最大限に減らすために、CMPHのような完全なハッシュ関数ジェネレーターを使用して、「n」個の識別子を衝突することなくnサイズの配列にマップできるようにします。このアプローチの欠点は、外部の「外部」ライブラリに依存する必要があることです。
私の場合、メモリ使用量を抑えながら一定時間のルックアップを行うためのよりスマートな方法があるかどうか疑問に思っています。私は16ビットの符号なし数値のインデックス付けに興味があり、セットサイズはかなり制限されていることを覚えておいてください。
ありがとう
16ビット値を扱っているという事実を知っているので、O（1）の異なる可能な値しかないため、ルックアップアルゴリズムは定数時間アルゴリズムになります。その結果、表面上は低速になる可能性のあるアルゴリズム（たとえば、n個の要素に対してO（n）で実行される線形探索）が実際にここで役立つ場合があります。
完璧なハッシュ関数を除いて、高速ルックアップを保証したい場合は、最悪の場合のO（1）ルックアップ時間を保証し、O（1）時間の挿入を期待しているカッコウハッシュを調べることをお勧めします（ただし、ハッシュ関数を少し賢くしてください）。16ビット値のハッシュ関数を生成するのは本当に簡単です。2つの16ビット乗数を計算し、16ビット値の上位ビットと下位ビットにこれらの値を乗算し、それらを合計すると、任意の素数で優れたハッシュ関数が得られると思います。
または、絶対にO（1）ルックアップを行う必要がなく、予想されるルックアップ時間に問題がない場合は、線形プロービングハッシュテーブルやダブルハッシュハッシュテーブルなど、オープンアドレス法の標準ハッシュテーブルを使用することもできます。この種のハッシュスキームでより小さな配列を使用すると、非常に高速になる可能性があり、実装は非常に簡単です。
まったく異なるアプローチの場合、スパースデータを格納していてルックアップ時間を短縮したい場合は、単純な平衡二分探索木を使用するのが適切なオプションです。たとえば、treapデータ構造は実装が簡単で、値に対して期待されるO（log n）ルックアップを提供します。16ビット値を扱っているので、ここではlog nは約16です（対数の底は実際には少し異なると思います）。したがって、ルックアップは非常に高速である必要があります。これにより、要素ごとに少しオーバーヘッドが発生しますが、要素が少ない場合は、簡単に実装できます。さらにオーバーヘッドを減らすために、要素ごとに2つのポインターしか必要としないスプレーツリーを調べることをお勧めします。
お役に立てれば！