Лабораторная работа №5
Хеширование данных. Поиск данных в хеш-таблице.
Разработать программу хеширования данных из файла методом открытого хеширования. Хеш-таблицу закодировать как класс, а операции с ней - как функции-члены класса. В программе предусмотреть следующий действия:
а) создание хеш-таблицы с небольшим количеством классов (B<=30) и небольшим набором исходных данных, вывод всей таблицы на экран, осуществление поиска по таблице, в качестве хеш-функции выбрать h(x)=x%B;
б) создание хеш-таблицы, для которой количество классов B задается пользователем (до 20000 - 50000), осуществление поиска по таблице, подсчет общего числа коллизий в таблице, нахождение самой длинной цепочки коллизий, процента заполняемости таблицы. В качестве хеш-функции выбрать h(x)=(ax+c)%B, проанализировать результаты заполняемости таблицы для различных a и c.
В качестве исходных данных выбрать:
9 вариант. Текстовый файл (варианты 3,6,9,12).
Алгоритм:
Создается массив списков размером B.
Считывается текст из файла и делится на лексемы. (пропускаются ненужные символы)
Лексема добавляется в список с индексом h(x). В качестве x берется hashcode лексемы.
Алгоритм поиска:
Список с индексом h(x) проверяется на наличие слова
При наличии выводится само слово, при отсутствии – соответствующее сообщение.
Алгоритм вывод таблицы:
Создается таблица с количеством строчек = B.
Каждая строка заполняется всеми словами, которые находятся в списке с соответствующим индексом.
Алгоритм подсчета коллизий:
Создается переменная для подсчета коллизий.
Проверяется каждый список и к переменной добавляется количество элементов в данном списке.
Алгоритм поиска самой длинной коллизии:
Создается переменная, которой изначально присваивается количество коллизий в списке с индексом 0.
Проверяется количество коллизий в каждом списке, если коллизий больше, то происходит переприсваивание.
Алгоритм подсчета заполняемости:
Считается количество непустых списков, делится на B и умножается на 100.
Код:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.IO;
namespace WindowsFormsApp1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
class HashTableA
{
public int B;
List[] Key;
public void Tablica()
{
Key = new List[B];
for (int i = 0; i < B; i++)
Key[i] = new List();
String[] data = File.ReadAllText("inputa.txt").Split(',', ' ', '\n').ToArray();
for (int i = 0; i < data.Length; i++)
{
/*string slovo = data[i];
int r = 0;
if (slovo.Length > 2) r = slovo[0] + slovo[1];
else r = slovo[0];
Key[System.Math.Abs(r % B)].Add(data[i]);*/
if (data[i].CompareTo(" ") > 0)
Key[System.Math.Abs(data[i].GetHashCode() % B)].Add(data[i]);
}
}
public void Vivod(DataGridView tablica)
{
tablica.Rows.Clear();
tablica.Columns.Clear();
int length = Key[0].Count;
for (int i = 1; i < B; i++)
if (Key[i].Count > length)
length = Key[i].Count;
for (int i = 0; i <= length; i++)
tablica.Columns.Add(" ", " ");
tablica.Rows.Add(B - 1);
for (int i = 0; i < B; i++)
tablica.Rows[i].Cells[0].Value = i;
for (int i = 0; i < B; i++)
for (int j = 0; j < Key[i].Count; j++)
tablica.Rows[i].Cells[j + 1].Value = Key[i][j];
}
public String Search(String word)
{
if (Key[System.Math.Abs(word.GetHashCode() % B)].Contains(word))
return word;
else
return "Такого слова нет";
}
}
class HashTableB
{
List[] Key;
public int B, a, c;
public void Build()
{
Key = new List[B];
for (int i = 0; i < B; i++)
Key[i] = new List();
String[] data = File.ReadAllText("inputb.txt").Split(',', ' ', '\n',';','\r','\t').ToArray();
for (int i = 0; i < data.Length; i++)
{
// int kk = data[i].GetHashCode();
// int gg = data[i].CompareTo(" ");
if (data[i].CompareTo(" ") > 0) //убираем пустые строки (все, что в Юникоде до пробела)
/*<0 текст в классе раньше по алфавиту чем пробел
=0 текст в классе одинаков с текстом пробел
>0 текст в классе позже по алфавиту чем текст пробел*/
Key[System.Math.Abs((a * data[i].GetHashCode() + c) % B)].Add(data[i]); //Аbs, тк хэши могут быть отрицательные
}
}
public String Search_Word(String word)
{
if (Key[System.Math.Abs((a * word.GetHashCode() + c) % B)].Contains(word)) //contains определяет, есть ли данное слово под индексом
return word;
else
return "Слово не найдено";
}
public void Collizii(Label l)
{
int x = 0;
for (int i = 0; i < Key.Length; i++)
if (Key[i].Count > 1) //число элементов под данным индексом
x += Key[i].Count;
l.Text = "Число коллизий: " + (x - 1);
}
public void MakcimumCollizii(Label l)
{
int x = Key[0].Count; //число элементов в первой ячейке
for (int i = 1; i < Key.Length; i++)
if (Key[i].Count > x)
x = Key[i].Count;
l.Text = "Самая длинная цепочка коллизий составляет: " + (x - 1) + " элементов";
}
public void Zapolnenie(Label l)
{
double x = 0;
for (int i = 0; i < Key.Length; i++)
if (Key[i].Count > 0)
x++;
x = Math.Round(x / Key.Length * 100);
l.Text = "Процент заполняемости таблицы составляет " + x + "%";
}
}
HashTableA hta = new HashTableA();
HashTableB htb = new HashTableB();
private void button1_Click(object sender, EventArgs e)
{
hta.B = Convert.ToInt32(numericUpDown1.Value);
hta.Tablica();
hta.Vivod(dataGridView1);
}
private void button2_Click(object sender, EventArgs e)
{
textBox2.Text = hta.Search(textBox1.Text);
}
private void button3_Click(object sender, EventArgs e)
{
htb.B = Convert.ToInt32(numericUpDown2.Value);
htb.c = Convert.ToInt32(numericUpDown3.Value);
htb.a = Convert.ToInt32(numericUpDown4.Value);
htb.Build();
htb.Collizii(label5);
htb.MakcimumCollizii(label6);
htb.Zapolnenie(label7);
}
private void button4_Click(object sender, EventArgs e)
{
textBox4.Text = htb.Search_Word(textBox3.Text);
}
private void label11_Click(object sender, EventArgs e)
{
}
private void numericUpDown3_ValueChanged(object sender, EventArgs e)
{
}
}
}
|
Тесты:
Выводы:
При увеличении B, количество коллизий увеличивается, но максимальная коллизия уменьшается = > таблица нормализуется;
При нечетном a процент заполняемости больше,количество коллизий меньше;
Большое увеличение a негативно влияет на количество коллизий и заполняемость;
 |
Скачать 159.66 Kb.