Полное условие задачи звучит так: Тип ключа – строка текста произвольной длины. Преобразование строки – конкатенация битовых образов символов. Метод хеширования – мультипликативный. Метод разрешения коллизий – квадратичный.
Имеется следующий код(говорю сразу написан немного неграмотно):
function.hpp
#include <iostream>
#include <map>
#include <conio.h>
#include <string.h>
#include <bitset>
std::map<int , std::string> str; //Контейнер строк
std::map<std::string, int> HashTable; //Хеш таблица
void Print(); //Вывод хеш таблицы
int FindHash(std::string s); //Поиск в хеш таблице
int Hash(std::bitset<8> Binary[1000]); //Функция считающая хеш
void BinaryNumber(int j); //Функция переводящая в двоичный код для общего случая
int BinaryNumber(std::string s); //Для корректной работы функции FindHash
//Перевод строки в двоичную последовательность
void BinaryNumber(int j)
{
std::bitset<8> Binary[1000];
int i = 0;
int k = 0;
std::cin >> str[j];
for (char c : str[j])
{
std::bitset<8> bitset(c);
Binary[i] = bitset;
i++;
}
HashTable[str[j]] = Hash(Binary);
}
//Функция перевода в двоичный код(Для функции поиска)
int BinaryNumber(std::string s)
{
std::bitset<8> Binary[1000];
int i = 0;
int k = 0;
int hash = 0;
for (char c : s)
{
std::bitset<8> bitset(c);
Binary[i] = bitset;
i++;
}
hash = Hash(Binary);
return hash;
}
//Вывод всей информации о хеш таблице
void Print()
{
int i = 0;
for (; HashTable[str[i]] != NULL; i++)
{
std::cout << str[i] << " : " << HashTable[str[i]] << std::endl;
}
}
/*Для мультипликативного хеширования используется следующая формула:
h(K) = [M * ((C * K) mod 1)]
Здесь производится умножение ключа на некую константу С, лежащую в интервале [0..1].
После этого берется дробная часть этого выражения и умножается на некоторую константу M, выбранную таким образом,
чтобы результат не вышел за границы хеш-таблицы. Оператор [ ] возвращает наибольшее целое, которое меньше аргумента.*/
int Hash(std::bitset<8> Binary[1000])
{
int i = 0;
int hash = 0;
for (; Binary[i] != NULL; i++)
{
hash += 10 * (floor((1 * (int)(Binary[i].to_ulong()))));
}
return hash;
}
//Функция поиска по хеш таблице
int FindHash(std::string s)
{
int hash = BinaryNumber(s);
for (int i = 0; HashTable[str[i]] != NULL; i++)
{
if (HashTable[str[i]] == hash)
{
return 1;
}
else
continue;
}
return 0;
}
main.cpp
#include "function.hpp"
int main()
{
setlocale(0, "");
int j = 0; //Счетчик подсчета строк.
int flag = 0; //Для меню
do
{
system("cls");
std::cout << "Введите 1, чтобы добавить строку" << std::endl
<< "Введите 2, чтобы вывести информацию." << std::endl
<< "Введите 3, чтобы сделать поиск заданного слова" << std::endl
<< "Введите 4, чтобы завершить работу" << std::endl;
std::cin >> flag;
switch (flag)
{
case 1:
{
system("cls");
std::cout << "Введите строку: ";
BinaryNumber(j);
j++;
system("pause");
break;
}
case 2:
{
system("cls");
Print();
system("pause");
break;
}
case 3:
{
system("cls");
std::string s;
std::cout << "Введите слово, которое нужно найти: ";
std::cin >> s;
if (FindHash(s))
{
std::cout << "Такое слово есть!" << std::endl;
}
else
{
std::cout << "Такого слова нет!" << std::endl;
}
system("pause");
break;
}
case 4:
{
system(EXIT_SUCCESS);
}
}
} while (flag != 4);
return 0;
}
Кто сможет доходчиво объяснить как реализовывать разрешение коллизий? По хешированию маловато примеров кода в сети Буду очень благодарен за помощь )
