Порядок выполнения работы. Экспериментальное исследование проводится следующим образом:
Экспериментальное исследование проводится следующим образом: 1) формируются случайным образом ключи заданного формата в количестве, превышающем количество сегментов хэш-таблицы в 2…3 раза; 2) для каждого сформированного ключа вычисляется хэш-функция, и подсчитывается, сколько раз вычислялся адрес того или иного сегмента хэш-таблицы. Листинг программы 1. Формирование экспериментальных данных.
#include< iostream> #include< fstream> #include< string> #include< ctime> usingnamespace std; #define b 2000 int h(char*); int main() { char current_key[7]={NULL}; int A[b]; int adress=0; srand((unsigned)time(0)); for(int i=0; i< b; i++) A[i]=0; for(int i=0; i< b*3; i++) { for(int j=0; j< 6; j++) { if((j> 0)& & (j< 4)) current_key[j]=(char)(rand()%10+48); else current_key[j]=(char)(rand()%26+65); } adress=h(current_key); A[adress]++; } ofstream os(" result.txt"); for(int i=0; i< b; i++) os< < A[i]< < endl; os.close(); return 0; }
int h(char current_key[6]) { int h=0, sum=0; for(int i=0; i< 6; i++) sum+=(int)((((int)current_key[i])/(3*(i+1))))*(int)current_key[i]; sum*=sum*2; sum=sum % 1000000; h=(int)(sum/100); do { h=h % b; } while(h> b); returnh; }
Результатом работы этой программы является текстовый файл Result.txt, который содержит столько строк, сколько сегментов в хэш-таблице. Каждая строка содержит число, показывающее, сколько раз вычислялся адрес соответствующего сегмента. На основе данных из этого файла построена диаграмма:
Рисунок 1 –Диаграмма распределения данных
Анализ этой диаграммы показывает, что коллизии распределены достаточно равномерно и хэш-функцию можно считать приемлемой. Ниже приведена программа, реализующая следующие режимы: 1. Рандомное генерирование хэш-таблицы на основе заданной хэш-функции(таблица специально сгенерирована так, чтобы оставались промежутки: это даст возможность добавлять в таблицу данные, таблица сохраняется в файле Table.txt) 2. Добавление элементов 3. Поиск элементов 4. Удаление элементов[1]
Листинг программы 2. Работа с хэш – таблицей. #include< iostream> #include< fstream> #include< string> #include< windows.h> #include< ctime> usingnamespace std; #define b 2000 string Tab[b]; int adress=0; int h(char[7]); void input(char[7]); void add(); void find(); void del(); void create_table(); void output_in_file();
int main() { SetConsoleCP(1251); SetConsoleOutputCP(1251); string smth; for(int i=0; i< b; i++) { Tab[i]=" "; }
for(;;) { system(" cls"); cout< < " МЕНЮ" < < endl< < endl< < " 1. Рандомноегенерированиехэш-таблицы" < < endl< < " 2. Добавление элемента" < < endl< < " 3. Поиск элемента" < < endl< < " 4. Удаление элемента" < < endl< < " 5. Выход из программы" < < endl; cin> > smth; if(smth==" 1") create_table(); else { if(smth==" 2") add(); else { if(smth==" 3") find(); else { if(smth==" 4") del(); else { if(smth==" 5") exit(0); else { cout< < " Вводить нужно цифру от 1 до 5 включительно! " < < endl; system(" pause"); } } } } } } return 0; }
int h(char key[7]) {
int h=0, sum=0; for(int i=0; i< 6; i++) sum+=(int)((((int)key[i])/(3*(i+1))))*(int)key[i]; sum*=sum*2; sum=sum % 1000000; h=(int)(sum/100); do { h=h % b; } while(h> b-1); return h; }
void input(char key[7]) { bool correct=true; char smth[256];
do { cin> > smth; if(smth[6]! =NULL) { correct=false; cout< < " Введенные данные некорректны. Введите еще раз: " < < endl; continue; } else { for(int i=0; i< 7; i++) key[i]=smth[i]; } for(int i=0; i< 6; i++) { if((i> 0)& & (i< 4)) { if(((int)key[i]< 48)||((int)key[i]> 57)) { correct = false; cout< < " Введенные данные некорректны. Введите еще раз: " < < endl; break; } } else { if(((int)key[i]< 65)||((int)key[i]> 90)) { correct = false; cout< < " Введенные данные некорректны. Введите еще раз: " < < endl; break; } } if(i==5) correct=true; } } while(correct==false); }
void add() { char key[7]={NULL}; bool correct = true;
system(" cls"); do { if(correct==true) cout< < " Введитеключформата «AцццAA», где" < < endl< < " «ц» – этоцифра 0…9; " < < endl< < " «A» – этобольшаябуквалатиницы A…Z." < < endl; input(key); adress=h(key); correct=true; while((Tab[adress]! =" ")& & (correct==true)) { if(Tab[adress]==key) correct=false; else adress+=2; } if(correct==false) cout< < " Такое значение уже есть в таблице, введите другое! " < < endl; } while(correct==false); adress=h(key); do { if((Tab[adress]==" ")||(Tab[adress]==" deleted")) { Tab[adress]=key; break; } else adress+=2;
} while(adress< b-1); if(adress> =b) cout< < " данные в таблицу добавить нельзя по одной из причин: " < < endl< < " Таблица переполнена" < < endl; else { cout< < " Данные добавлены в таблицу" < < endl< < endl< < "..." < < endl; for(int i=0; i< 11; i++) { if(adress-(5-i)< 0) continue; if(i==5) cout< < endl< < adress< < " " < < Tab[adress]< < endl< < endl; else cout< < adress-(5-i)< < " " < < Tab[adress-(5-i)]< < endl; } cout< < "..." < < endl< < endl; } output_in_file(); system(" pause"); }
void find() { char key[7]={NULL}; bool correct = true; int try_count=0;
system(" cls"); cout< < " Введитеключформата «AцццAA», где" < < endl< < " «ц» – этоцифра 0…9; " < < endl< < " «A» – этобольшаябуквалатиницыA…Z." < < endl; input(key); adress=h(key); bool flag=false; do { if(Tab[adress]==key) { flag=true; break; } else { if(Tab[adress]==" ") break; else adress+=2; } } while(adress< b-1); if(flag==false) cout< < " Элементненайден" < < endl; else { cout< < " Элементнайден! " < < endl< < endl< < "..." < < endl; for(int i=0; i< 11; i++) { if(adress-(5-i)< 0) continue; if(i==5) cout< < endl< < adress< < " " < < Tab[adress]< < endl< < endl; else cout< < adress-(5-i)< < " " < < Tab[adress-(5-i)]< < endl; } cout< < "..." < < endl< < endl; } system(" pause"); }
void del() { char key[7]={NULL}; bool correct = true; int try_count=0;
system(" cls"); cout< < " Введитеключформата «AцццAA», где" < < endl< < " «ц» – этоцифра 0…9; " < < endl< < " «A» – этобольшаябуквалатиницыA…Z." < < endl; input(key); adress=h(key); bool flag=true; do { if(Tab[adress]==key) { Tab[adress]=" deleted"; break; } else { if(Tab[adress]==" ") { flag=false; break; } else adress+=2; } } while(adress< b-1); if(adress> =b) flag=false; if(flag==false) cout< < " Элементненайден" < < endl; else { cout< < " Элементудален! " < < endl< < endl< < "..." < < endl; for(int i=0; i< 11; i++) { if(adress-(5-i)< 0) continue; if(i==5) cout< < endl< < adress< < " " < < Tab[adress]< < endl< < endl; else cout< < adress-(5-i)< < " " < < Tab[adress-(5-i)]< < endl; } cout< < "..." < < endl< < endl; } output_in_file(); system(" pause"); }
void create_table() { char key[7]={NULL}; int adress=0; bool correct=true;
srand((unsigned)time(0)); for(int i=0; i< b-100; i++) { for(int j=0; j< 6; j++) { if((j> 0)& & (j< 4)) key[j]=(char)(rand()%10+48); else key[j]=(char)(rand()%26+65); } adress=h(key); if((Tab[adress]==" ")||(Tab[adress]==" deleted")) Tab[adress]=key; else continue; } output_in_file(); } void output_in_file() { ofstream ofs(" Table.txt"); for(int i=0; i< b; i++) { ofs< < i< < " " < < Tab[i]< < endl; } ofs.close(); } Контрольные вопросы 1. Каков принцип построения хэш-таблиц? 2. Существуют ли универсальные методы построения хэш-таблиц? Ответ обоснуйте. 3. Почему возможно возникновение коллизий? 4. Каковы методы устранения коллизий? Охарактеризуйте их эффективность в различных ситуациях. 5. Назовите преимущества открытого и закрытого хэширования. 6. В каком случае поиск в хэш-таблицах становится неэффективен? 7. Как выбирается метод изменения адреса при повторном хэшировании?
|
