Размещено на http://www.allbest.ru/

• СОДЕРЖАНИЕ
• ВВЕДЕНИЕ
• ГЛАВА 1. ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ
• 1.1 Актуальность
• 1.2 Общие основы
• ГЛАВА 2. ПРОЕКТНЫЙ РАЗДЕЛ
• 2.1 Принцип построения хеш - функций
• 2.2 Применение хеширования
• ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
• 3.1 Организация структуры данных
• 3.2 Реализация функций структуры
• ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНЫЙ РАЗДЕЛ
• 4.1 Руководство пользователя
• ЗАКЛЮЧЕНИЕ
• СПИСОК ЛИТЕРАТУРЫ



ВВЕДЕНИЕ

С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и др.), компилятором (таблица символов). По словам Брайана Кернигана, это «одно из величайших изобретений информатики». Заглядывая в адресную книгу, энциклопедию, алфавитный указатель, мы даже не задумываемся, что упорядочение по алфавиту является не чем иным, как хешированием.

Хеширование есть разбиение множества ключей (однозначно характеризующих элементы хранения и представленных, как правило, в виде текстовых строк или чисел) на непересекающиеся подмножества (наборы элементов), обладающие определенным свойством. Это свойство описывается функцией хеширования, или хеш-функцией, и называется хеш-адресом. Решение обратной задачи возложено на хеш-структуры (хеш-таблицы): по хеш-адресу они обеспечивают быстрый доступ к нужному элементу. В идеале для задач поиска хеш-адрес должен быть уникальным, чтобы за одно обращение получить доступ к элементу, характеризуемому заданным ключом (идеальная хеш-функция). Однако, на практике идеал приходится заменять компромиссом и исходить из того, что получающиеся наборы с одинаковым хеш-адресом содержат более одного элемента.

Целью данной работы, является реализация метода и разработка программного продукта, исключающего коллизию.



ГЛАВА 1. ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ

1.1 Актуальность

Мир захлестнула волна информации. Главное при работе с ней - быстрый поиск с последующей выборкой. Информация хранится в базах данных, и базы данных стоят сейчас почти на каждом компьютере. Обычно базы состоят из таблиц. Рассмотрим типичную структуру таблицы в реляционной базе данных. Все поля, входящие в таблицу, можно разбить на три группы: системные поля, поля наименования, и поля данных.

Системные поля - это ключи. В них входят первичный ключ (счетчик) для связи с подчиненными таблицами и вторичные ключи для связи с главными таблицами (если данная таблица является подчиненной).

Поля наименования - это те поля, по которым пользователь может идентифицировать описанный в таблице объект в ряду себе подобных. Для предотвращения дублирования записей (т.е. появления «двойников») необходимо обеспечивать уникальность записей. Типы полей - строковые, реже - числовые или дата/время.

Поля данных - в них хранятся данные об объекте. Это поля типа числовые, денежные, дата/время, и т.д.

При работе с таблицей одна из главных задач - выборка, причем в большинстве случаев выборка осуществляется по параметру (то есть из таблицы выбираются только те записи, которые соответствуют некоторому условию). Существуют два подхода к выборке: сверху, со стороны пользователей, и снизу, со стороны аппаратного обеспечения («железа»).

При подходе сверху главный определяющий фактор - удобство пользователя. Существует много способов доступа к данным в таблицах, но наибольшее распространение получил язык SQL. Фактически SQL фактически стал индустриальным стандартом для реляционных баз данных. Американский Институт Национальных Стандартов (ANSI) в 1986 году объявил язык SQL стандартом для реляционных баз данных. То же самое сделала и Международная Организация по стандартам (ISO). Все основные реляционные системы управления баз данных поддерживают в том или ином виде язык SQL, и большинство разработчиков реляционных систем управления базами данных стремятся следовать стандарту ANSI. Конструкторы SQL встроены в настольные СУБД (ACCESS, Delphi), серверные приложения работают в основном с SQL (ORACLE, SQL server).

В команде SQL указывается сама команда (действие, которое надо совершить), область выборки (таблицы, из которых необходимо произвести выборку), данные, которые должны быть выданы (список полей), условия связи между таблицами и условия отбора, то есть по команде SQL фактически осуществляется ассоциативная выборка из базы данных.

При подходе снизу главный определяющий фактор - архитектура компьютера. В настоящее время компьютеры имеют адресную структуру памяти и приспособлены для операций «мало данных - много команд», а при работе с данными (при выборке) чаще всего происходят операции типа «много данных - мало команд» Произошедшее за последнее время бурное развитие компьютерной техники не только не решило, а скорее усугубило эту проблему. Производительность процессоров увеличилось во много раз, увеличилась емкость винчестеров и размер оперативной памяти. Но при этом производительность канала память - процессор увеличилась сравнительно медленно, и является в данный момент камнем преткновения. Применение аппаратных средств ускорения (кэширования) тоже не очень эффективно из-за больших объемов данных.

Для того чтобы получить доступ к нужной записи в таблице необходимо либо перебирать все записи (для этого потребуется N циклов, N - число записей в таблице), либо найти адрес записи (так как память компьютера имеет адресную архитектуру). Для ускорения поиска прилагаются большие усилия: применяют сортировки (то есть записи упорядочивают в определенном порядке), индексирование, и хеширование (адрес записи - некоторая функция от значения аргумента записи). Рассмотрим подробнее все эти способы.

Сортировки. При дихотомическом поиске в упорядоченном массиве количество циклов поиска - log₂N, где N - число записей в таблице. Но сортировки производят только по одному полю. После совершения любого действия над записями (добавления, изменения, удаления) приходится производить упорядочивание (пересортировку) таблицы, а число перестановок возрастает в геометрической прогрессии при увеличении количества записей.

Индексирование. Индексы - это специальные конструкции, которые позволяют быстро найти адрес нужной записи и в настоящее время они широко применяются на практике. На одну таблицу можно создавать несколько индексов. В качестве примера можно рассмотреть рекомендации по применению индексов в ORACLE. Они сводятся к следующему: рекомендуется использовать индексы для обеспечения уникальности записей; для ускорения выборки данных; задавать индексы для тех полей, выборку по которым производится чаще всего, и при этом рекомендуется задавать на таблицу не более трех индексов, что очень мало. На практике применяют индексы следующим образом: в системных полях таблиц используют один или два индекса, и еще один индекс - на поля наименования. Область данных почти никогда не индексируют, хотя отбор чаще всего происходит именно по этим полям. Кроме того, на обновление индексов также требует времени, а сами индексы занимают место на диске (а иногда размер индексов превышает размер основной таблицы).

Поэтому индексация таблиц не очень помогает: индексы занимают место (а иногда могут превышать размеры таблиц), а в случае отбора по неиндексированному полю они не помогают.

Хеширование. При хешировании записей под таблицу сразу выделяют с запасом некоторый объем памяти, и адрес записи в этом объеме - некоторая функция от содержимого одного из полей записи (хеш-функция). Хеширование также проводят по одному полю. Недостатки этого способа: необходимость в избыточном резервировании памяти. Кроме этого, даже при достаточно большом выделенном объеме памяти возможна ситуация, при котором на некоторое место претендуют сразу две или более записей, то есть возникает коллизия.

1.2 Общие основы

Хеширование -- преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения.

Хеширование применяется для сравнения данных: если у двух массивов хеш-коды разные, массивы гарантированно различаются; если одинаковые -- массивы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов входного массива; существует множество массивов, дающих одинаковые хеш-коды -- так называемые коллизии. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

Существует множество алгоритмов хеширования с различными характеристиками (разрядность, вычислительная сложность, криптостойкость и т. п.). Выбор той или иной хеш-функции определяется спецификой решаемой задачи.

Хеш-функция - это некоторая функция h(K), которая берет некий ключ K и возвращает адрес, по которому производится поиск в хеш-таблице, чтобы получить информацию, связанную с K. Например, K - это номер телефона абонента, а искомая информация - его имя. Функция в данном случае нам точно скажет, по какому адресу найти искомое.

Коллизия - это ситуация, когда h(K1) = h(K2), в то время как K1 ? K2. В этом случае, очевидно, необходимо найти новое место для хранения данных. Очевидно, что количество коллизий необходимо минимизировать.

Хорошая хеш-функция должна удовлетворять двум требованиям:

· ее вычисление должно выполняться очень быстро;

· она должна минимизировать число коллизий.

Итак, первое свойство хорошей хеш-функции зависит от компьютера, а второе - от данных. Если бы все данные были случайными, то хеш-функции были бы очень простые (несколько битов ключа, например). Однако на практике случайные данные встречаются крайне редко, и приходится создавать функцию, которая зависела бы от всего ключа.

Теоретически невозможно определить хеш-функцию так, чтобы она создавала случайные данные из реальных неслучайных файлов. Однако на практике реально создать достаточно хорошую имитацию с помощью простых арифметических действий. Более того, зачастую можно использовать особенности данных для создания хеш-функций с минимальным числом коллизий (меньшим, чем при истинно случайных данных).

Возможно, одним из самых очевидных и простых способов хеширования является метод середины квадрата, когда ключ возводится в квадрат и берется несколько цифр в середине. Здесь и далее предполагается, что ключ сначала приводится к целому числу, для совершения с ним арифметических операций. Однако такой способ хорошо работает до момента, когда нет большого количества нолей слева или справа.

хеширование свертка программный коллизия

ГЛАВА 2. ПРОЕКТНЫЙ РАЗДЕЛ

2.1 Принцип построения хеш-функций

Многочисленные тесты показали хорошую работу двух основных типов хеширования, один из которых основан на делении, а другой на умножении. Впрочем, это не единственные методы, которые существуют, более того, они не всегда являются оптимальными.

По мере роста базы данных можно

· пользоваться изначальной хеш-функцией, теряя производительность из-за роста коллизий;

· выбрать хеш-функцию «с запасом», что повлечет неоправданные потери дискового пространства;

· периодически менять функцию, пересчитывать все адреса. Это отнимает очень много ресурсов и выводит из строя базу на некоторое время.

Существует техника, позволяющая динамически менять размер хеш-структуры. Это - динамическое хеширование. Хеш-функция генерирует так называемый псевдоключ (“pseudokey”), который используется лишь частично для доступа к элементу. Другими словами, генерируется достаточно длинная битовая последовательность, которая должна быть достаточна для адресации всех потенциально возможных элементов. В то время, как при статическом хешировании потребовалась бы очень большая таблица (которая обычно хранится в оперативной памяти для ускорения доступа), здесь размер занятой памяти прямо пропорционален количеству элементов в базе данных. Каждая запись в таблице хранится не отдельно, а в каком-то блоке (“bucket”). Эти блоки совпадают с физическими блоками на устройстве хранения данных. Если в блоке нет больше места, чтобы вместить запись, то блок делится на два, а на его место ставится указатель на два новых блока.

Задача состоит в том, чтобы построить бинарное дерево, на концах ветвей которого были бы указатели на блоки, а навигация осуществлялась бы на основе псевдоключа. Узлы дерева могут быть двух видов: узлы, которые показывают на другие узлы или узлы, которые показывают на блоки. Например, пусть узел имеет такой вид, если он показывает на блок:

Zero	Null
Bucket	Указатель
One	Null

Если же он будет показывать на два других узла, то он будет иметь такой вид:

Zero	Адрес a
Bucket	Null
One	Адрес b

Вначале имеется только указатель на динамически выделенный пустой блок. При добавлении элемента вычисляется псевдоключ, и его биты поочередно используются для определения местоположения блока. Например, элементы с псевдоключами 00… будут помещены в блок A, а 01… - в блок B. Когда А будет переполнен, он будет разбит таким образом, что элементы 000… и 001… будут размещены в разных блоках.

2.2 Применение хеширования

До сих пор рассматривались способы поиска в таблице по ключам, позволяющим однозначно идентифицировать запись. Такие ключи называются первичными ключами. Возможен вариант организации таблицы, при котором отдельный ключ не позволяет однозначно идентифицировать запись. Такая ситуация часто встречается в базах данных. Идентификация записи осуществляется по некоторой совокупности ключей. Ключи, не позволяющие однозначно идентифицировать запись в таблице, называются вторичными ключами.

Даже при наличии первичного ключа, для поиска записи могут быть использованы вторичные. Например, поисковые системы internet часто организованы как наборы записей, соответствующих Web-страницам. В качестве вторичных ключей для поиска выступают ключевые слова, а сама задача поиска сводится к выборке из таблицы некоторого множества записей, содержащих требуемые вторичные ключи.



ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

3.1 Организация структуры данных

Все данные организованы в структуре представляющей собой дерево:

class BH_Tree

{

private :

BH *Head;

public :

BH_Tree();

~BH_Tree();

char *Key_Gen(String *data, int coll);

void insert(String *data,int coll);

int Past(BH *root, String *data,int coll,int pos);

void paintTree( TImage *img, int x, int y,int _x=0, int _y=0);

void paintRoot( TImage *img,BH *root,int x, int y,int

n=1,int m=1,int _x=0, int _y=0);

char * binkey (int num);

};

Каждый элемент - узел дерева является структурой:

struct BH

{

String *BH_data;

int collData;

BH *Left;

BH *Right;

BH();

};

3.2 Реализация функций структуры

При внесении данных в структуру, первоначально генерируется «pseudokey», после чего алгоритм проверяет, существует ли первый элемент дерева. Если данные до этого не вводились, то выделяется память под один узел дерева и текущее значение помещается в данный узел. Если же в структуре уже имеются элементы, то данные добавляются в ближайший свободный элемент, путь к которому соответствует «pseudokey».

Функция, реализующая добавление элемента:

int Past(BH *root, String *data,int coll,int pos)

{

char *p=Key_Gen(data,coll);

if(root==NULL)

{root=new (BH);

Past(root,data,coll,pos);

return 1;

}

else

{

if(root->BH_data==NULL

&& root->Left==NULL

&& root->Right==NULL)

{root->BH_data=data;

root->collData=coll;

return 1;

}

else

{if(root->BH_data==NULL)

{

if(p[pos]=='0')

{

if(root->Right==NULL)

{

BH *tmp = new BH;

root->Right=tmp;

root->Right->BH_data=data;

root->Right->collData=coll;

return 1;

}

else

{

Past(root->Right,data,coll,++pos);

return 1;

}

}

if(p[pos]=='1')

{

if(root->Left==NULL)

{

BH *tmp =new BH;

root->Left=tmp;

root->Left->BH_data=data;

root->Left->collData=coll;

return 1;

}

else

{

Past(root->Left,data,coll,++pos);

return 1;

}

}

}

if(root->BH_data!=NULL)

{

if(*root->BH_data==*data)return 1;

if(p[pos]=='0')

{

BH * tmp =new BH;

root->Right=tmp;

root->Right->BH_data=data;

root->Right->collData=coll;

}

if(p[pos]=='1')

{

BH * tmp =new BH;

root->Left=tmp;

root->Left->BH_data=data;

root->Left->collData=coll;

}

int dd = root->collData;

String *ddd = new String;

*ddd=*root->BH_data;

delete(root->BH_data);

root->BH_data=NULL;

root->collData=0;

Past(root,ddd,dd,pos);

return 1;

}

}

}

}

При внесении данных автоматически выполняется функция прорисовки дерева:

void paintTree( TImage *img, int x, int y,int _x=0, int _y=0)

{

img->Canvas->Rectangle(0,0,img->Width,img->Height);

img->Canvas->Brush->Color=clWhite;

img->Canvas->FloodFill(0,0,clWhite,fsBorder);

img->Canvas->CleanupInstance(); paintRoot(img,Head, x, y,100,20,_x,_y)

;}

Данная функция вызывает функцию рисования узла дерева и затем посредством рекурсивных вызовов прорисовывают всё дерево:

void paintRoot( TImage *img,BH *root,int x, int y,int n=1,int m=1,int _x=0,

int _y=0)

{

n-=25;

m+=10;

if(_x>=x & _x<=x+20 & _y>=y & _y<=y+20 )

{

img->Canvas->Brush->Color=clWhite;

img->Canvas->Font->Size=24;

if(root!=NULL) if(root->BH_data!=NULL)img->Canvas-

>TextOutA(10,10,(*root->BH_data));

}

if(root==NULL)

{

img->Canvas->Brush->Color=clRed;

img->Canvas->Ellipse(x,y,(x+10),(y+10));

}

else

{

if(root!=NULL && root->BH_data==NULL)

{

img->Canvas->Brush->Color=clBlue;

img->Canvas->Ellipse(x,y,(x+10),(y+10));

img->Canvas->MoveTo(x+5,y+5);

img->Canvas->LineTo(x-5-n,y+15+m);

paintRoot(img,root->Left,x-10-n,y+10+m,n,m,_x,_y);

img->Canvas->MoveTo(x+5,y+5);

img->Canvas->LineTo(x+15+n,y+15+m);

paintRoot(img,root->Right,x+10+n,y+10+m,n,m,_x,_y);}

else{

img->Canvas->Brush->Color=clGreen;

img->Canvas->Ellipse(x,y,x+10,y+10);

img->Canvas->MoveTo(x+5,y+5);

img->Canvas->LineTo(x-5-n,y+15+m);

paintRoot(img,root->Left,x-10-n,y+10+m,n,m,_x,_y);

img->Canvas->MoveTo(x+5,y+5);

img->Canvas->LineTo(x+15+n,y+15+m);

paintRoot(img,root->Right,x+10+n,y+10+m,n,m,_x,_y);

}

}

}

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНЫЙ РАЗДЕЛ

4.1 Руководство пользователя

Программа представляет собой оконное приложение. В нижнем левом углу располагается поле ввода и кнопка добавления введенных данных в дерево. Основная область рабочего окна служит для прорисовки дерева.

При добавлении данных, на рабочей области отрисовывается построенное дерево. Дерево может содержать до трех различных типов узлов, синие - не содержащие данных, кроме указателей на потомков, зеленые - содержащие пользовательские данные, и красные - NULL элементы.

При непосредственном выборе узла с помощью мышки, происходит поиск и вывод содержимого данного узла.



ЗАКЛЮЧЕНИЕ

Хеширование, которое родилось еще в середине прошлого века, активно используется в наши дни везде, где требуется произвести быструю выборку данных. Появились новые методы хеширования, новые модификации алгоритмов, написанных ранее, что позволяет значительно ускорить и расширить возможности поиска информации.

В своей работе я проанализировал современные подходы к организации хранения и обработки данных, выявил преимущества использования hash - функций для достижения наилучшей производительности поиска информации. Цель работы - создание программного продукта, достигнута.



СПИСОК ЛИТЕРАТУРЫ

1. Hellerman H., Digital Computer System Principles. McGraw-Hill, 1967.

2. Ершов А.П., Избранные труды., Новосибирск: «Наука», 1994.

3. Кнут Д., Искусство программирования, т.3. М.: Вильямс, 2000.

4. Peterson W.W., Addressing for Random-Access Storage // IBM Journal of Research and Development, 1957. V.1, N2. Р.130--146.

5. Morris R., Scatter Storage Techniques // Communications of the ACM, 1968. V.11, N1. Р.38--44.

6. Buchholz W., IBM Systems J., 2 (1963), 86-111

7. Fundamenta Math. 46 (1958), 187-189

8. http://www.ecst.csuchico.edu/~melody/courses/csci151_live/Dynamic_hash_notes.htm

9. http://planetmath.org/encyclopedia/Hashing.html

10. http://www.eptacom.net/pubblicazioni/pub_eng/mphash.html

11. R. Cichelli, Minimal Perfect Hashing Made Simple, Comm. ACM Vol. 23 No. 1, Jan. 1980.

12. T. Gunji, E. Goto, J. Information Proc., 3 (1980), 1-12

13. Чмора А., Современная прикладная криптография., М.: Гелиос АРВ, 2001.

14. Litwin W., Proc. 6^th International Conf. on Very Large Databases (1980), 212-223

15. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ, М.: МЦНМО, 2001

16. Вирт Н., Алгоритмы + структуры данных = программы, М.: Мир, 1985.

17. Керниган Б., Пайк Р., Практика программирования, СПб.: Невский диалект, 2001.

18. Шень А, Программирование: теоремы и задачи. М.: МЦНМО, 1995.

Размещено на Allbest.ru