0

一意の番号 (105、342、432、34 など) のリストがあり、それらをインデックス (0、1、2、3 など) にマップしたいとします。これを行う一般的な方法はありますか？そうでない場合は、リスト内のすべての数値を事前に知っていて、それらの値をハードコーディングできると想定してください。それが役に立たない場合、別の制限要因は、数字が「ほぼ連続」している可能性があります. これは、それらの大部分が連続していることを意味しますが、ギャップが存在する可能性があります (事前にわかっていることです)。

4

1 に答える 1

1

あなたがしたいことは、本質的にハッシュマップ（または辞書）を実装することです。この種の構造を実装する多くの言語用の多くのライブラリがあります。
非常に単純化された方法で内部で行われるのは、たとえば、配列と、配列のインデックスの 1 つに数値をマップするハッシュ関数であり、O(1) ベースの要素への償却アクセスを実現します。彼らの鍵に。
2 つ目の重要な側面は、衝突をどのように処理するかです。たとえば、数値のハッシュ関数がf(x) = x mod 10. 13と33の両方が3にハッシュされます。. これは衝突であり、対処する必要があります。たとえば、要素の順序付きリストを作成し、これらを配列のスロットに割り当てることができます。要素を検索するときは、そのキーをハッシュし、指定された配列の位置でリストを検索して、完全に一致するキーを探します。
これはすべての始まりに過ぎず、 ウィキペディアのハッシュ関数とハッシュ マップで詳細を確認できます。
あなたの場合、キー自体のみを保存したいことに注意してください。通常、より複雑なオブジェクトを格納し、キーで検索する必要があります。キーは通常、数値または文字列ですが、より複雑なオブジェクトの場合もあります。

編集
あなたの質問は、あなたのような問題に対するより一般的な解決策よりも、特定のシナリオに最適なハッシュ関数を見つけることに関するものであることに気付きました。
私の理解が正しければ、あなたは事前に数字を知っているということですか？これが実際に当てはまる場合は、次のように、非常にハードコードされた形式で (自分で提案したように)、配列内のインデックスの 1 つをそれぞれに割り当てる番号を使用できます。

if (num == 105)
    idx = 0;
else if (num == 342)
    idx = 1;
...

数字がわからないが、たとえば、それらの最小値と最大値を知っている場合は、次のようにそれらをインデックスにハッシュできます。

f(x) = (x - smallest_num) mod (greatest_num - smallest_num + 1)

この場合、f(x)は完全なハッシュ関数です。つまり、衝突は発生しません。数字が常に連続しているわけではないため、アレイのスロットの一部はまだ空のままです。

注：これで何をするつもりなのかまだわからないので、あなたの質問に正しく答えたかどうかはわかりません. 特に、あなたが自分の番号を事前に知っているかもしれないという事実、またはそれらについて多くのことを知っているかもしれないという事実は、私を混乱させます. 目的が明確になれば、目的を達成するための別の方法を提供できるかもしれません。

于 2012-07-01T20:23:45.997 に答える