Внимание! Совсем скоро домен in-72.org.ua станет недоступным! Сайт переносится на новый архивный домен: in72.at.ua. Таким образом, если вы попали сюда через кеш поисковика, например, вы будете знать, куда идти дальше.
В программировании хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
Существует два варианта хэш-таблиц: с прямой и открытой адресацией. Хэш-таблица содержит некоторый массив H, элементы которого есть пары (хэш-таблица с открытой адресацией) или списки пар (хэш-таблица с прямой адресацией). Выполнение операции в хэш-таблице начинается с вычисления хэш-функции от ключа. Получающееся хэш-значение i = hash(key) играет роль индекса в массиве H. Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту, который хранится в соответствующей ячейке массива H[i]. Ситуация, когда для различных ключей получается одно и то же хэш-значение, называется коллизией (collision). Число хранимых элементов делённое на размер массива H (число возможных значений хэш-функции) называется коэффициентом заполнения хэш-таблицы (load factor) и является важным параметром, от которого зависит среднее время выполнения операций. Свойства хеш-таблицы
Важное свойство хэш-таблицы состоит в том, что все три операции в среднем выполняются за время O(1). Но при этом не гарантируется, что время выполнения отдельной операции мало. Это связано с тем, что при достижении некоторого значения коэффициента заполнения необходимо осуществлять перестройку индекса хэш-таблицы: увеличить значение размера массива H и заново добавить в пустую хэш-таблицу все пары.
Разрешение коллизий
Существует несколько способов разрешения колизий.
Открытая адресация В массиве H хранятся сами пары. В случае возникновения коллизии, алгоритм поиска (удаления, добавления) объекта просто перемещается на ячейку вправо до момента разрешения коллизии. Разрешение коллизии происходит при достижении пустой ячейки или ячейки, в котором хранится пара с заданным ключом. Размер шага смещения вправо может зависеть от значения ключа и вычисляться с помощью второй хэш-функции. Данная техника называется двойным хэшированием с открытой адресацией. Прямая адресация В МАССИВЕ H ХРАНЯТСЯ СПИСКИ ПАР. КОЛЛИЗИИ ПРОСТО ПРИВОДЯТ К ТОМУ, ЧТО ПОЯВЛЯЮТСЯ СПИСКИ ДЛИНОЙ БОЛЕЕ ОДНОГО ЭЛЕМЕНТА. Среднее время выполнения операций в хэш-таблице с прямой адресацией равно коэффициенту заполнения.
Задание
Реализовать хеш-таблицу, в которой могут хранится до 1000 чисел в диапазоне от 1 до 30000. Реализовать функции добавления числа в хеш-таблицу. Подсчитать какое количество операций необходимо в среднем для вставки нового числа при коэффициенте заполнения таблицы 25%, 50%, 75% и 90%. Для этого заполнить хеш-таблицу до указанного коэфициента заполнения и усреднить количество операций необходимых для вставки следующих 25 чисел.
Литература 1. Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ = Introduction to Algorithms / Пер. с англ. под ред. А. Шеня. — М.: МЦНМО, 2002. — 960 с. — ISBN 5-900916-37-5 2. КОРМЕН, Т., ЛЕЙЗЕРСОН, Ч., РИВЕСТ, Р., ШТАЙН, К. АЛГОРИТМЫ: ПОСТРОЕНИЕ И АНАЛИЗ = INTRODUCTION TO ALGORITHMS / ПОД РЕД. И. В. КРАСИКОВА. — 2-Е ИЗД.. — М.: ВИЛЬЯМС, 2005. — 1296 С. — ISBN 5-8459-0857-4 3. http://ru.wikipedia.org/wiki/Хеш-таблица 4. Методичні вказівки «Хеш-таблиці. Використання в алгоритмах пошуку»
