/Checking-the-number-of-collisions

🕵🏼 Checking the number of collisions for lines in the file [👨‍🏫 Teacher: Веснин Артем Михайлович] {4️⃣ Semester} (Algorithms and data structures)

Primary LanguageC++

Хеширование. Коллизии.

Проверьте число коллизий для строк в файле endict.txt

Используйте в качестве хеша:

  1. Сумму ASCII кодов символов строки

  2. Более продвинутый алгоритм с использованием полиномиального подхода

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
a​ab -> 011000010110000101100010

Используйте в качестве Хэш 16 бит (для строк с нечетным количеством символов предложите способ дополнения битовой последовательности до числа кратного 16). Сравните методы (на частоту коллизий):

  • Остатка от деления (текущая реализация)
  • Середины квадрата
  • Сверткой