Разработка программного продукта, исключающего коллизию
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
»а бы от всего ключа.
Теоретически невозможно определить хеш-функцию так, чтобы она создавала случайные данные из реальных неслучайных файлов. Однако на практике реально создать достаточно хорошую имитацию с помощью простых арифметических действий. Более того, зачастую можно использовать особенности данных для создания хеш-функций с минимальным числом коллизий (меньшим, чем при истинно случайных данных).
Возможно, одним из самых очевидных и простых способов хеширования является метод середины квадрата, когда ключ возводится в квадрат и берется несколько цифр в середине. Здесь и далее предполагается, что ключ сначала приводится к целому числу, для совершения с ним арифметических операций. Однако такой способ хорошо работает до момента, когда нет большого количества нолей слева или справа.
хеширование свертка программный коллизия
ГЛАВА 2. ПРОЕКТНЫЙ РАЗДЕЛ
2.1 Принцип построения хеш-функций
Многочисленные тесты показали хорошую работу двух основных типов хеширования, один из которых основан на делении, а другой на умножении. Впрочем, это не единственные методы, которые существуют, более того, они не всегда являются оптимальными.
По мере роста базы данных можно
пользоваться изначальной хеш-функцией, теряя производительность из-за роста коллизий;
выбрать хеш-функцию с запасом, что повлечет неоправданные потери дискового пространства;
периодически менять функцию, пересчитывать все адреса. Это отнимает очень много ресурсов и выводит из строя базу на некоторое время.
Существует техника, позволяющая динамически менять размер хеш-структуры. Это - динамическое хеширование. Хеш-функция генерирует так называемый псевдоключ (pseudokey), который используется лишь частично для доступа к элементу. Другими словами, генерируется достаточно длинная битовая последовательность, которая должна быть достаточна для адресации всех потенциально возможных элементов. В то время, как при статическом хешировании потребовалась бы очень большая таблица (которая обычно хранится в оперативной памяти для ускорения доступа), здесь размер занятой памяти прямо пропорционален количеству элементов в базе данных. Каждая запись в таблице хранится не отдельно, а в каком-то блоке (bucket). Эти блоки совпадают с физическими блоками на устройстве хранения данных. Если в блоке нет больше места, чтобы вместить запись, то блок делится на два, а на его место ставится указатель на два новых блока.
Задача состоит в том, чтобы построить бинарное дерево, на концах ветвей которого были бы указатели на блоки, а навигация осуществлялась бы на основе псевдоключа. Узлы дерева могут быть двух видов: узлы, которые показывают на другие узлы или узлы, которые показывают на блоки. Например, пусть узел имеет такой вид, если он показывает на блок:
ZeroNullBucketУказательOneNull
Если же он будет показывать на два других узла, то он будет иметь такой вид:
ZeroАдрес aBucketNullOneАдрес b
Вначале имеется только указатель на динамически выделенный пустой блок. При добавлении элемента вычисляется псевдоключ, и его биты поочередно используются для определения местоположения блока. Например, элементы с псевдоключами 00… будут помещены в блок A, а 01… - в блок B. Когда А будет переполнен, он будет разбит таким образом, что элементы 000… и 001… будут размещены в разных блоках.
2.2 Применение хеширования
До сих пор рассматривались способы поиска в таблице по ключам, позволяющим однозначно идентифицировать запись. Такие ключи называются первичными ключами. Возможен вариант организации таблицы, при котором отдельный ключ не позволяет однозначно идентифицировать запись. Такая ситуация часто встречается в базах данных. Идентификация записи осуществляется по некоторой совокупности ключей. Ключи, не позволяющие однозначно идентифицировать запись в таблице, называются вторичными ключами.
Даже при наличии первичного ключа, для поиска записи могут быть использованы вторичные. Например, поисковые системы internet часто организованы как наборы записей, соответствующих Web-страницам. В качестве вторичных ключей для поиска выступают ключевые слова, а сама задача поиска сводится к выборке из таблицы некоторого множества записей, содержащих требуемые вторичные ключи.
ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
3.1 Организация структуры данных
Все данные организованы в структуре представляющей собой дерево:
class BH_Tree
{
private :
BH *Head;:_Tree();
~BH_Tree();*Key_Gen(String *data, int coll);insert(String *data,int coll);Past(BH *root, String *data,int coll,int pos);paintTree( TImage *img, int x, int y,int _x=0, int _y=0);paintRoot( TImage *img,BH *root,int x, int y,int=1,int m=1,int _x=0, int _y=0); * binkey (int num);
};
Каждый элемент - узел дерева является структурой:
struct BH
{*BH_data;collData;*Left;*Right;();
};
3.2 Реализация функций структуры
При внесении данных в структуру, первоначально генерируется pseudokey, после чего алгоритм проверяет, существует ли первый элемент дерева. Если данные до этого не вводились, то выделяется память под один узел дерева и текущее значение помещается в данный узел. Если же в структуре уже имеются элементы, то данные добавляются в ближайший свободный элемент, путь к которому соответствует pseudokey.
Функция, реализующая добавление элемента:
int Past(BH *root, String *data,int coll,int pos)
{*p=Key_Gen(data,coll);(root==NULL)
{root=new (BH);(root,data,coll,pos);1;
}
{(root->BH_data==NULL
&& root->Left==NULL
&& root->Right==NULL)
{root->BH_data=data;>collData=coll;1;