哈希表及碰撞计算结果

Question

哈希表及碰撞计算结果

3

我知道我的代码/最小值没有工作，但我不是要求在代码中获得更多的帮助。测试运行了1000次，尝试将50个人插入表格。试验基于getRandomPersonalNumber随机生成键。

线性探测函数返回任何冲突，如果需要更新索引，并搜索如果键匹配索引。现在在结果中，唯一看起来奇怪的事情是表1。我问了一些朋友关于结果，他们说可能模数100正在做某些事情，这就是为什么我在表1中得到高冲突结果的原因。

我担心它可能与我的计算有关，但再次，它只发生在100模数中，所以我不知道能否精确计算碰撞量而不依赖于代码一些数学？最后，有没有一种方式可以计算出存储量与冲突量（载荷系数）之间的良好平衡点？

typedef struct
{
    struct Bucket *table; 

} HashTable;

static int hash(Key key, int tablesize)
{
    return (key % tablesize);
}

static int addPersonsToTable(HashTable *htable, const Person *personArray, int amount)
{
    int collissions = 0, i;
    for (i = 0; i < amount; i++)
    {
        int key = personArray[i].personalNumber;
        collissions += insertElement(htable, key, personArray[i]);
    }
    return collissions;
}

static int getRandomPersonalNumber(void)
{
    int day = rand() % 30 + 1; 
    int month = rand() % 12 + 1;
    int year = rand() % 60 + 40;
    return day + 100 * month + 10000 * year;
}

int insertElement(HashTable *htable, const Key key, const Value value)
{
    int coll;
    int index = hash(key, htable->size);
    coll = linearProbe(htable, key, &index);
    if (coll ==0 || index > -1)
    {
        htable->table[index].key = key;
        htable->table[index].value = value;
    }
    else
    {

    }

    return coll;
}

表格测试。

-- Summary ----------------------
Average collisions on 1000 runs. Inserted 50 persons.
Table 1 (size 100) - average number of collisions: 516 - load factor: 0.50
Table 2 (size 150) - average number of collisions: 26 - load factor: 0.33
Table 3 (size 200) - average number of collisions: 68 - load factor: 0.25
Table 4 (size 250) - average number of collisions: 12 - load factor: 0.20
Table 5 (size 300) - average number of collisions: 26 - load factor: 0.17
Table 6 (size 350) - average number of collisions: 7 - load factor: 0.14
Table 7 (size 400) - average number of collisions: 16 - load factor: 0.13
Table 8 (size 450) - average number of collisions: 5 - load factor: 0.11
----------------------------------

- jacob

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dominicm00 · Accepted Answer

这是哈希表工作的自然结果；即使您的哈希非常独特，当映射到可能值范围很小的区间时，会有大量的冲突。假设您的哈希函数完全随机，期望的负载因子为usedSpace/availableSpace。

话虽如此，您似乎错误地认为负载因子.5是低效的。这个负载因子是完全可接受的；例如Java的默认负载因子为.75！在非常少量元素上进行线性搜索非常高效，因此只要每个哈希位置中的元素数量较低，就没有真正的性能惩罚。

比总哈希冲突次数更令人担忧的是，如果同一位置存在大量哈希冲突，即您的哈希不够随机。将更多元素塞入单个哈希位置中，线性搜索时间就越长；这就是为什么对哈希函数的保证比对哈希冲突的保证更重要。

编辑：虽然以上内容是正确的，但表大小为100时异常高的冲突（我读错了：哎呀）是由于取模是month和year的倍数：请参见下面的评论。