3

我知道我没有工作代码/最低限度，但我不是在代码中寻求更多帮助。我将尽可能地总结一下。该测试运行了1000多次尝试将50人员插入表中。试验随机生成基于 的密钥getRandomPersonalNumber。

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

我担心这可能与我的计算有关，但话又说回来，它只发生在100 modulo，所以我不知道我能否在不依赖代码的情况下精确计算碰撞量？最后，有没有办法计算存储量与共谋量（负载因子）的良好中间立场？

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
----------------------------------
4

1 回答 1

3

这是哈希表工作方式的自然结果。即使您的哈希是高度唯一的，当映射到一个小范围的可能值时，也会有大量的冲突。假设您的哈希函数是完全随机的，那么预期的负载因子是usedSpace/availableSpace.

也就是说，您似乎错误地认为您的.5负载因子效率低下。这个负载系数非常好；例如，Java 的默认加载因子为.75! 对极少数元素的线性搜索非常有效，因此只要每个散列位置中的元素数量较少，就不会造成真正的性能损失。

比哈希冲突的总数更令人担忧的是，如果在同一个地方有大量的哈希冲突，即您的哈希不够随机。填充到单个哈希位置的元素越多，搜索时间就越线性；这就是为什么对哈希函数的保证比对哈希冲突的保证更重要的原因。

编辑：虽然上述内容是正确的，但表大小为 100 的异常高冲突（我误读：哎呀）是由于模数是month和year倍数的一个因素：请参阅下面的评论。

于 2021-05-29T21:59:08.593 回答