ハッシュ関数は5000以下の整数ですか？

Question

5000より小さい整数に対してユニークなハッシュ値を生成する最も簡単で簡単なハッシュ関数はどれですか？

実際の問題は、1から5000までの値を含む約50のサイズの整数配列があることです。今では、値を指定して逆マッピングを行う必要があり、格納されているインデックスを見つけなければなりません。私はそれが私の配列がソートされているのでバイナリ検索を使って行うことができることを知っています。

8ビット（char）の値の配列スペースの5キロバイトが大きすぎる場合を除き、ハッシュを気にしないC.

Answer 1

のための任意のハッシュライブラリを示唆しないでください - インデックスとして番号を使用数字が使用されていることを示す1を格納し、使用されていないことを示す0を格納します。これをさらに減らすには、ストレージ用にビットマップとして配列を使用する（約625バイトに5000ビットを格納する必要があります）と、見るべき右のビット位置を計算する少しのコードを使用します。

または、インデックスを50個の整数の配列に配置する必要がある場合は、5 KBのスペースを使用して、50個の整数の配列にインデックスを格納します。 。インデックスは、それが発見された場所を示すために（存在しない）-1であるか非負かどうかを確認するaux_arrayで

int main_array[50]; 
signed char aux_array[5000]; 

// initialize aux_array to all -1 
for (int i = 0; i < sizeof(aux_array); i++) 
    aux_array[i] = -1; 
// for each value `v` in main_array, store its index `i` in `aux_array[v]` 
for (int i = 0; i < num_values; i++) 
{ 
    int v = main_array[i]; 
    if (aux_array[v] != -1) 
     ...non-unique data in main_array... 
    aux_array[v] = i; 
} 

逆ルックアップをチェックします。これは逆インデックスです。 127以上の値が必要になった場合は、signed charではなくunsigned charまたはshortに切り替えることができます（マーカー値を適切に調整して、私の例では-1）。

ハッシングはおそらく費用対効果に優れません。