整数低于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）。

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