整數低於5000的散列函數？

Question

這是最好的和最簡單的散列函數，它爲低於5000的整數生成唯一的散列值？

實際的問題是，我有一個大小約爲50的整數數組，其中包含1到5000之間的值。現在我必須做反向映射，即給定一個值，並且我必須找出它存儲的索引。我知道這可以通過使用二進制搜索來完成，因爲我的數組已排序。

請不要建議爲C.

Answer 1

除非5 KB的陣列空間，8位（char）值太大，任何哈希庫，不要用哈希麻煩 - 使用數字作爲指標轉換爲字符數組，存儲1表示使用數字，0表示不使用數字。您可以通過將該陣列用作存儲位圖（因此您需要大約625個字節來存儲5000個位）來進一步減少存儲空間，再加上一些代碼來計算正確的位位置以查看。

或者，假設您需要將索引找到50個整數的數組中，請使用5 KB的空間將索引存儲到50個整數的數組中，可能有-1表示該數字未被使用。

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; 
} 

在aux_array逆查找檢查是否該索引爲-1（不存在）或非負，以指示它被發現。這是一個倒排索引。如果最終需要超過127個值，則可以切換到unsigned char或short而不是signed char（在適當調整標記值時，在我的示例中爲-1）。

散列可能不符合成本效益。