我知道我的代码/最小值没有工作,但我不是要求在代码中获得更多的帮助。测试运行了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
----------------------------------
month
和year
分别是100和10000的倍数,而它们中任何一个的模100都是0!这意味着只有day
对您的哈希位置有贡献,这意味着您的有效表大小仅为30!要解决此问题,您应该将month
和year
乘以质数。 - dominicm00