Разработка программного продукта, исключающего коллизию
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ
.1 Актуальность
.2 Общие основы
ГЛАВА 2. ПРОЕКТНЫЙ РАЗДЕЛ
.1 Принцип построения хеш - функций
.2 Применение хеширования
ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
.1 Организация структуры данных
.2 Реализация функций структуры
ГЛАВА 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 - число записей в таблице), либо найти адрес записи (так как память компьютера имеет адресную архитектуру). Для ускорения поиска прилагаются большие усилия: приме?/p>