Hash函数的整数低于5000？

Question

哪个是最好和最简单的哈希函数,它为5000以下的整数生成唯一的哈希值？

实际问题是我有一个大小约为50的整数数组,包含1到5000之间的值.现在我必须进行反向映射,即给定一个值,我必须找出它存储的索引.我知道可以通过使用二进制搜索来完成,因为我的数组已经排序.

请不要为C建议任何哈希库.

Answer 1

除非8位(char)值的5 KB数组空间太大,否则不要打扰哈希 - 使用数字作为字符数组的索引,存储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在我的示例中对标记值进行适当调整).

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