c - 哈希表中的冲突次数

Question

我正在为存储此范围内的元素创建一个哈希表:2000000-20000000 个值。

示例: 17664658-8,7587458-8,7338375-4,5741259-2.....

在100000个元素的样本中，碰撞次数约为23939次，在1000000个元素的样本中，碰撞次数约为439870次。我对哈希表了解不多，但这个碰撞次数也不少高的？

我读到，在受控的数字范围内，您可以拥有一个相当均匀的良好哈希函数，但不知道如何或从哪里开始，有什么建议吗？

这是我的哈希函数。

int hash(char* clave,int m) { //m is the size of the table (about the double of the elements to be stored)
        int number=0,i=0;
        /// 
        while(isdigit(clave[i])){ //i don't use the last 2 characters. 
            number+=(clave[i++]-'0');
            if(isdigit(clave[i]))
                number*=10;
        }
        /// mutiplication method
        float dis,R;
        R=0.6106154;
        dis = R*(number) - floor(R*(number));
        int result = (int)(dis*m);
        return result;
    }

Answer 1

不，碰撞次数并不太高，事实上这与您所期望的差不多。公式为expected number of collisions in a hash table具有统一的随机哈希函数和 m 个存储桶和 n 个插入:

n - m * (1 - ((m-1)/m)^n)

对于您的情况:

m = 178144
n = 100000

将数字代入给出:

100000 - 178144 * (1 - ((178144-1)/178144) ^ 100000)
= 23476.674

观察到的冲突次数是 23939。所以你的哈希函数没有任何问题。