|
|
Задание 2 сем 2 в2. Отчет по выполнению практического задания 2 По дисциплине Структуры и алгоритмы обработки данных
|
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
|
Федеральное государственное бюджетное образовательное учреждение высшего образования
"МИРЭА - Российский технологический университет"
РТУ МИРЭА
| 
Отчет по выполнению практического задания №2
По дисциплине «Структуры и алгоритмы обработки данных»
|
Тема:
Хеширование и организация быстрого поиска данных.
|
|
Выполнил студент
|
Бананов Б.Б.
|
группа
|
БАНБ-АН-АН
|
Оглавление
Тема. Хеширование и организация быстрого поиска данных. Задание
Разработайте приложение, которое использует хеш-таблицу для организации прямого доступа к записям файла, структура записи которого приведена в варианте 17.
Коллизия обрабатывается в 5 строке функции push:
Разработайте и реализуйте функции для операций:
1) Хеш-функцию (метод определите сами).
2) Прочитать запись из файла и вставки запись в таблицу (запись
включает: ключ и номер записи с этим ключом в файле).
3) Удалить запись из таблицы и соответственно из файла.
4) Найти запись с заданным ключом в файле, используя хеш-таблицу.
5) Выполнить рехеширование.
2. Разработайте такие тесты, чтобы возникли коллизии.
3. Разработайте такие тесты, чтобы требовалось рехеширование.
4. Заполните файл большим количеством записей. Определите время чтения записи с заданным ключом для первой записи файла, для последней и где-то в середине. Убедитесь (или нет), что время доступа для всех записей одинаково.
5. Выведите список индексов, которые формируются при вставке элементов в таблицу.
Разработка программы
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
std::vector split(const std::string& s, char delim) {
std::stringstream ss(s);
std::string item;
std::vector elems;
if (s.length() < 1) return elems;
while (std::getline(ss, item, delim)) {
elems.push_back(item);
// elems.push_back(std::move(item)); // if C++11 (based on comment from @mchiasson)
}
return elems;
}
int getNextPrime(int n) {
while (1) {
int c = 1;
n++;
for (int i = 2; i <= n; i++)
if (n % i == 0)
c++;
if (c == 2)
return n;
}
}
struct Node {
int id = -1; //номер читательского
string name = ""; //фио
string adress = ""; //адрес
void output() {
if (id < 0) {
printf("(Пусто)");
return;
}
if (isDeleted) {
printf("(УДАЛЕНО)");
return;
}
printf("(Номер читательского: %d, ФИО: ", id);
cout << name;
cout << ", Адрес: ";
cout << adress;
cout << ")";
cout << " Позиция в файле: ";
cout << position;
}
int position = -1;
bool isFree = true;
bool isDeleted = false;
friend bool operator!= (Node n1, Node n2) {
return n1.id != n2.id;
}
friend bool operator== (Node n1, Node n2) {
return n1.id == n2.id;
}
};
class HashTable {
//открытая адресация
int size = 11; //размер таблицы
int amountItemsExisting = 0; //количество элементов в таблице
int amountItemsDeleted = 0; //кол-во удалённых элементов в таблице
int step = 1; //смещение
vector table;
public:
//рехэширование таблицы
void rehash() {
amountItemsDeleted = 0;
if (isOverflow()) size *= 2;
amountItemsExisting = 0;
vector temp(table);
table.clear();
table.resize(size);
while (!(temp.empty())) {
Node node = temp.back();
temp.pop_back();
if (node.isFree) continue;
if (node.isDeleted) continue;
push(node);
}
}
private:
public:
HashTable() {
table.resize(this->size);
}
//добавить в таблицу
void push(Node node) {
if (node.id < 0) return;
int key = getHash(node);
int tableSize = table.size();
while (!table[key].isFree) {
key += step;
key %= tableSize;
}
node.isFree = false;
node.isDeleted = false;
table[key] = node;
amountItemsExisting++;
if (isOverflow()) {
rehash();
}
}
//удалить из таблицы
void pop(Node node) {
int key = getHash(node);
if (key < 0 || key >= size) return;
Node& tableNode = table[key];
tableNode.isDeleted = true;
amountItemsExisting--;
amountItemsDeleted++;
}
//форматированный вывод таблицы в консоль
void output() {
int tableSizeNumbers = log10(table.size());
for (auto i = 0; i < this->table.size(); i++) {
Node node = table[i];
printf(("%3d "), i);
table[i].output();
cout << endl;
}
}
//найти запись по ключу
Node find(int id) {
int key = getHash(id);
for (auto i = key; i < table.size(); i++) {
Node& selNode = table[i];
if (selNode.isDeleted) continue;
if (selNode.isFree) break;
if (selNode.id == id) return selNode;
}
Node badNode = Node();
badNode.id = -1;
return badNode;
}
HashTable() {}
private:
//проверка на переполненность
bool isOverflow() {
return ((double)amountItemsExisting + amountItemsDeleted) / size > 0.75 ? true : false;
}
//хэш-функция(по записи и отдельно по ключу)
int getHash(Node node) {
return node.id % size;
}
//хэш-функция(по записи и отдельно по ключу)
int getHash(int id) {
return id % size;
}
};
class File {
fstream file;
ofstream O2File;
HashTable* hashTable; //хэш-таблица
vector freeFields;
string path;
static const int LINE_LENGTH = 128;
public:
void rehash() {
hashTable->rehash();
}
File(string path) {
this->path = path;
file.open(path, fstream::out | fstream::in);
if (!file.is_open()) throw new exception();
//O2File.open("TEMP." + path, ofstream::out | ofstream::in);
hashTable = new HashTable();
this->fillTable();
}
//поиск записи по ключу
Node find(int key) {
return this->hashTable->find(key);
}
void output() {
this->hashTable->output();
}
void add(Node newNode) {
file.clear();
if (freeFields.size() > 0) {
file.seekp(freeFields.front(), ios_base::beg);
freeFields.erase(freeFields.begin());
} else {
file.seekp(0, ios_base::end);
file << endl;
}
newNode.position = file.tellg();
string msg = (boost::format(string("%-" + to_string(LINE_LENGTH) + "s")) % (boost::format("%d;%s;%s") % newNode.id % newNode.name % newNode.adress)).str();
file << msg;
file.flush();
push(newNode);
}
void pop(int key) {
Node node = hashTable->find(key);
if (node.id < 0) return;
hashTable->pop(node);
clearLine(node.position);
}
File() {
delete hashTable;
file.close();
O2File.close();
}
private:
//всорптавка записи в таблицу
void push(Node newNode) {
hashTable->push(newNode);
}
//заполнение таблицы из файла
void clearLine(int pos) {
file.clear();
if (pos < 0) return;
file.seekg(pos, ios::beg);
string line;
getline(file, line);
file.clear();
file.seekp(pos, ios::beg);
file << string(" ").substr(0, line.length());
file.flush();
if (line.length() < 128) return;
freeFields.push_back(pos);
}
void fillTable() {
string line;
while (!file.eof() && !file.bad() && !file.fail() && file.good()) {
//file.clear();
auto pos = file.tellg();
file.sync();
getline(file, line);
vector elems = split(line, ';');
if (elems.size() < 3) {
auto lastPos = file.tellg();
clearLine(pos);
file.seekg(lastPos);
continue;
}
Node* node = new Node();
int id = stoi(elems[0]);
string name = elems[1];
string adress = elems[2];
node->id = id;
node->name = name;
node->adress = adress;
//node->code = buff;
node->position = pos;
this->hashTable->push(*node);
}
}
};
void main() {
setlocale(LC_ALL, "Russian");
File* file = new File("database.txt");
file->output();
cout << "обновление новой записи" << endl;
int deletingNumber = 179815;
Node node = { deletingNumber, "Шампунь", "Вернский, 4" };
file->add({ 12321+rand()%10, "Вадим", "Горский, 5" });
file->add(node);
file->output();
cout << (boost::format("Удаление записи с номером %d:\n\t") % deletingNumber).str();
file->find(deletingNumber).output();
file->pop(deletingNumber);
cout << endl;
file->output();
cout << "Рехеширование:\n";
file->rehash();
file->output();
system("pause");
}
|
Тесты
Входные данные
database.txt
Выводы
В результате проделанной работы, я получить навыки по разработке хеш-таблиц и их применении. В процессе было разработано приложение, которое использует хеш-таблицу для организации прямого доступа к записям файла.
Ответы на вопросы
Расскажите о назначении хеш-функции.
Алгоритм хеш-функции преобразует уникальный ключ записи в её индекс в таблице.
Что такое коллизия?
Коллизия – это ситуация, когда разным ключам соответствует одно значение хеш-функции.
Что такое «открытый адрес» по отношению к хеш-таблице?
В хеш-таблице элементы могут содержать только пары ключ-значение или ключ - ссылка на значение, где Открытый адрес – это свободная ячейка хеш-таблицы, закрытый адрес – это занятая ячейка.
Как в хеш-таблице с открытым адресом реализуется коллизия?
В случае коллизии происходит смещение на ограниченное кол-во ячеек, определяемое определёнными алгоритмами или просто константа(напр. =1)
Какая проблема, может возникнуть после удаления элемента из хеш-таблицы с открытым адресом и как ее устранить?
Выполнение операции удаления записи из хеш-таблицы с открытым адресом имеет свои трудности и связано это с тем, что при удалении нельзя делать ячейку открытой, так как другие ключи при разрешении коллизий были вставлены после удаляемой и поиск свободной выполнялся при закрытой ячейке.
Решением этой проблемы является добавление метки “удалено”. А очистка от “удалённых” элементов возможно только при рехешировании.
Что определяет коэффициент нагрузки в хеш-таблице?
Кол-во записей в таблице / максимальный размер таблицы.
Обычно это значение не должно превышать 0,75.
Что такое «первичный кластер» в таблице с открытым адресом?
Первичный кластер(или первичная кластеризация) - это явление, которое происходит, когда обработчик коллизий создает условие роста кластера. Обработчик коллизий со смещением 1 из таблицы с открытым адресом способствует первичной кластеризации. Первичная кластеризация порождает длинные пути.
Как реализуется двойное хеширование?
Помимо хеширования ключа, идёт хеширования смещения для устранения первичной кластеризации.
Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличие от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно, будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её рехешированием. |
|
|
Скачать 286.57 Kb.