Проверьте число коллизий для строк в файле endict.txt
Используйте в качестве хеша:
-
Сумму ASCII кодов символов строки
-
Более продвинутый алгоритм с использованием полиномиального подхода
unsigned int h;
for(int i = 0; i < key.length(); i++) {
h = h + (unsigned int)pow(key.at(i), (i+1));
}
Задача на +3 балла - Используйте строку из endict_small.txt
в качестве битовой последовательности
ab -> 0110000101100010
aab -> 011000010110000101100010
Используйте в качестве Хэш 16 бит (для строк с нечетным количеством символов предложите способ дополнения битовой последовательности до числа кратного 16). Сравните методы (на частоту коллизий):
- Остатка от деления (текущая реализация)
- Середины квадрата
- Сверткой