I know I don't have a working code/minimal, but I am not asking for more help in the code. I am going to try to summarize as much as possible. The test runs for 1000 times trying to insert 50 persons into the table. The trial randomly generates keys based on getRandomPersonalNumber.
The linear probing function returns if there are any collisions, updates the index if needed, and searches if the keys match the index. Now in the result, the only thing that seems weird is Table 1 I have asked some friends about the result, and they said that perhaps modulo 100 is doing something and that why I am getting the high collusion result in Table 1.
I am concerned that it is something perhaps with my calculations, but then again, it is only happening with 100 modulo, so I don't know can I calculate precisely the amount of collision without relying on the code some math perhaps? Lastly, is there a way to calculate a good middle ground for the amount of storage vs the amount of collusion(load factor)?
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;
}
Table test.
-- 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
----------------------------------
