Тема: [C++] Хеш-таблиця з розподіленими ланцюжками переповненнь
Доброго дня!
В мене є хеш-таблиця, в яку дані читаються з файлу, та мій код працює вірно.
Але поставлено наступне завдання, що ця таблиця повинна бути з розподіленими ланцюжками переповненнь.
Я не дуже розумію як це в цілому має виглядати та як це реалізувати, було б непогано якщо в когось є приклади або поянення.
Тому що мені пояснили так: це робиться заради того, щоб були варіанти як боротися з тим, коли в одну комірку записують наприклад 101 та 1, але цього просто не може відбутись, бо в комірці зберігається лише одне значення.
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
#define N 5 //число записів у таблиці
#define EMPTY -1
struct HashT
{
string name;
int amount;
string key;
int adr;
};
HashT hashTabl[N]; //хеш - таблиця
string keys[N];
string name[N];
int Hash(string key)
{
int addr = 0;
for (string::iterator it = key.begin(); it != key.end(); ++it)
addr += (int)*it;
return (addr % N);
}
int Hash(int addr)
{
return (addr % N);
}
void Init(void)
{
for (int i = 0; i < N; i++)
hashTabl[i].adr = EMPTY;
}
int Insert(string key, int adr)
{
int addr, a1;
addr = Hash(key);
if (hashTabl[addr].adr != EMPTY)
{
a1 = addr;
do
{
addr = Hash(addr + 1);
} while (!((addr == a1) || (hashTabl[addr].adr == EMPTY)));
if (hashTabl[addr].adr != EMPTY)
return 0;
}
hashTabl[addr].key = key;
hashTabl[addr].adr = adr;
return 1;
}
int Search(string key)
{
int addr, a1;
addr = Hash(key);
if (hashTabl[addr].adr == EMPTY)
return EMPTY; //місце вільне – ĸлюча немає в таблиці
else
if (hashTabl[addr].key == key)
return hashTabl[addr].adr; //ĸлюч знайдений на своєму місці
else //місце зайняте іншим ĸлючем
{
a1 = Hash(addr + 1);
//Пошуĸ, поĸи не знайдений ĸлюч чи не зроблений повний оборот
while ((hashTabl[a1].key != key) && (a1 != addr))
a1 = Hash(a1 + 1);
if (hashTabl[a1].key != key)
return EMPTY;
else
return hashTabl[a1].adr;
}
}
int main(void)
{
ifstream in("D:\\hello.txt");
if (in.is_open())
{
for (int i = 0; i < N; i++) in >> keys[i];
for (int i = 0; i < N; i++) in >> name[i];
}
int i, res;
string key;
Init();
cout << "\nKeys -> ";
for (i = 0; i < N; i++)
cout << keys[i] << " ";
for (i = 0; i < N; i++)
Insert(keys[i], i);
cout << "\nHashed table (key-adr)" << endl;
for (i = 0; i < N; i++)
cout << " " << hashTabl[i].name << " " << hashTabl[i].key << "--" <<
hashTabl[i].adr << endl;
cout << "\n";
for (i = 0; i < N; i++)
{
cout << " Input searched keys -> ";
cin >> key;
res = Search(key);
if (res == EMPTY) cout << " not search \n";
else cout << " " << res << "\n";
}
}