Создание хеш таблицы c

Обновлено: 06.07.2024

Сравнить хэш-таблицы с различными способами разрешения коллизий: метод цепочек, метод двойного хэширования и метод линейного пробирования.

Хеширование – преобразование ключей к числам.

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

Хеш-функция ― преобразование по детерминированному алгоритму входного массива данных произвольной длины (один ключ) в выходную битовую строку фиксированной длины (значение). Результат вычисления хеш-фукнции называют «хешем».

Хеш-функция должна иметь следующие свойства:

Всегда возвращать один и тот же адрес для одного и того же ключа;
Не обязательно возвращает разные адреса для разных ключей;
Использует все адресное пространство с одинаковой вероятностью;
Быстро вычислять адрес.

Коллизией хеш-функции H называется два различных входных блока данных X и Y таких, что H(x) = H(y) .

Хеш-таблица – структура данных, хранящая ключи в таблице. Индекс ключа вычисляется с помощью хеш-функции. Операции: добавление, удаление, поиск. Пусть хеш-таблица имеет размер M , количество элементов в хеш-таблице – N .

Число хранимых элементов, делённое на размер массива (число возможных значений хеш-функции), называется коэффициентом заполнения хеш-таблицы (load factor). Обозначим его α = N/M .

Этот коэффициент является важным параметром, от которого зависит среднее время выполнения операций.

Парадокс дней рождений. При вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии уже превысит 50 % (если каждый элемент может равновероятно попасть в любую ячейку).

Хеш-таблицы различаются по методу разрешения коллизий. Основные методы разрешения коллизий:

Метод цепочек.
Метод открытой адресации.

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

Вычисляем значение хеш-функции добавляемого ключа – h .
Находим A[h] – указатель на список ключей.
Вставляем в начало списка (в конец списка дольше). Если запрещено дублировать ключи, то придется просмотреть весь список.

Время работы: В лучшем случае – O(1) . В худшем случае – если не требуется проверять наличие дубля, то O(1) – иначе – O(N)

Вычисляем значение хеш-функции удаляемого ключа – h .
Находим A[h] – указатель на список ключей.
Ищем в списке удаляемый ключ и удаляем его.

Время работы: В лучшем случае – O(1) . В худшем случае – O(N) .

Вычисляем значение хеш-функции ключа – h .
Находим A[h] – указатель на список ключей.
Ищем его в списке.

Время работы: В лучшем случае – O(1) . В худшем случае – O(N) .

Среднее время работы операций поиска, вставки (с проверкой на дубликаты) и удаления в хеш-таблице, реализованной методом цепочек – O(1 + α) , где α – коэффициент заполнения таблицы.

Среднее время работы.

Среднее время работы операций поиска, вставки (с проверкой на дубликаты) и удаления в хеш-таблице, реализованной методом цепочек – O(1 + α), где α – коэффициент заполнения таблицы.

Доказательство. Среднее время работы – математическое ожидание времени работы в зависимости от исходного ключа. Время работы для обработки одного ключа T(k) зависит от длины цепочки и равно 1 + Nh(k) , где Ni – длина i-ой цепочки. Предполагаем, что хеш-функция равномерна, а ключи равновероятны.

Среднее время работы

Метод открытой адресации

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

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

Вычисляем значение хеш-функции ключа – h .
Систематически проверяем ячейки, начиная от A[h] , до тех пор, пока не находим пустую ячейку.
Помещаем вставляемый ключ в найденную ячейку. В п.2 поиск пустой ячейки выполняется в некоторой последовательности. Такая последовательность называется «последовательностью проб».

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

Важно, чтобы для каждого ключа k последовательность проб h(k, 0), h(k, 1), . , h(k, M − 1) представляла собой перестановку множества 0,1, . , M − 1 , чтобы могли быть просмотрены все ячейки таблицы.

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

Удаление ключа. Алгоритм удаления достаточен сложен. Нельзя при удалении ключа из ячейки i просто пометить ее значением NIL . Иначе в последовательности проб для некоторого ключа (или некоторых) возникнет пустая ячейка, что приведет к неправильной работе алгоритма поиска. Решение. Помечать удаляемые ячейки спец. значением «Deleted» . Нужно изменить методы поиска и вставки. В методе вставки проверять «Deleted» , вставлять на его место. В методе поиска продолжать поиск при обнаружении «Deleted» .

Вычисление последовательности проб. Желательно, чтобы для различных ключей k последовательность проб h(k, 0), h(k, 1), . , h(k, M − 1) давала большое количество последовательностей- перестановок множества 0,1. , M − 1 .

Обычно используются три метода построения h(k, i) :

Линейное пробирование.
Квадратичное пробирование.
Двойное хеширование.

h(k, i) = (h′(k) + i) mod M

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

h(k, i) = (h1(k) + ih2(k)) mod M.

Требуется, чтобы последовательность проб содержала все индексы 0, .. , M–1 . Для этого все значения h2(k) должны быть взаимно простыми с M .

M может быть степенью двойки, а h2(k) всегда возвращать нечетные числа.
M простое, а h2(k) меньше M .

Общее количество последовательностей проб O(M^2) .

Лучший случай	В среднемю Метод цепочек.	В среднем. Метод открытой адресации.	Худший случай.
Поиск	O(1)	O(1 + a)	O(1 / 1 - a)	O(n)
Вставка	O(1)	O(1 + a)	O(1 / 1 - a)	O(n)
Удаление	O(1)	O(1 + a)	O(1 / 1 - a)	O(n)

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

Для запуска необходиа java версии 1.8 и Apache Maven версии 3.5.0. Для компиляции необходимо в корне проекта выполнить команду

А для запуска программы

Оба параметра являются обязательными.

Во время выполнения в консоль будут выведены выполненные команды.

Формат входных данных

Примеры: add 10 20 search 15 print min

Команда print отражает внутреннее строение структуры данных. Для хэш-таблицы с методом цепочек вывод команды print будет иметь следующий вид:

<> - отдельная ячейка массива, в которой храниться список ключей. А для хеш-таблиц с открытой адресацией вывод будет выглядеть так:

Hash table: [ 755 D __ 855 __ 942 __ 346 __ 588 __ 576 ]

__ - пустая ячейка, D - удаленная ячейка.

Формат выходных данных

В выходной файл выводятся результаты исполнения программы.

Команда print должна отражать внутреннее строение структуры данных

Команда search выводит error, в случае, когда значение не было найдено, или значение найденное по ключу в противном случае.

Команда add добавляет значение в таблицу (Ничего не выводит).

Команда delete удаляетя число, или ничего не делает, если значение не было найдено (Ничего не выводит).

Команда min выводит минимальное число в таблице, или empty, если таблица пустая.

Команда max выводит максимальное число в таблице,или empty, если таблица пустая.

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

1.Юнит тесты, проверящие корректность работы методов каждой хеш-таблицы

Тесты находятся в ./src/test/java/tests/

2.Юнит тесты для провеки времени выполнения большого числа операций добавления, поиска и удаления.

Тесты находятся в ./src/test/java/tests/

3.Файлы с входными данными и правильными ответами.

На вход программе подается два файла.

Заитем выходной файл с результатами исполнения программы сравнивается с файлом в котором находятся правильные ответы

Тесты находятся в ./tests/

Подробное описание тестов

1.Простая проверка всех операций кроме print

2.Проверка корректной работы add, delete(удаление элементов по несушествуюшему ключу) и print

3.Проверка корректной работы add, delete(удаление элементов по сушествуюшему ключу) и print

4.Проверка корректной работы search(поиск элементов по несушествуюшему ключу)

5.Проверка корректной работы search(поиск элементов по сушествуюшему ключу)

Сравнение времени работы

Время работы рачитываем тестом с 1000000 операций каждого типа.

Search time: 354

Delete time: 255

Search time: 281

Delete time: 365

Search time: 273

Delete time: 377

При использовании открытой адресации двойное хеширование обычно превосходит квадратичное пробирование. Единственным исключением является ситуация, в которой доступен большой объем памяти, а данные не расширяются после создания таблицы; в этом случае линейное пробирование несколько проще реализуется, а при использовании коэффициентов нагрузки менее 0,5 не приводит к заметным потерям производительности.

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

Если не уверены — используйте метод цепочек. У него есть свои недостатки — прежде всего необходимость в дополнительном классе связанного списка, но зато если в список будет внесено больше данных, чем ожидалось изначально, реализация по крайней мере не замедлится до полного паралича.

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

Представляет коллекцию пар «ключ-значение», которые упорядочены по хэш-коду ключа.

Примеры

В следующем примере показано, как создавать, инициализировать и выполнять различные функции Hashtable и выводить их ключи и значения.

Мы не рекомендуем использовать Hashtable класс для новой разработки. Вместо этого рекомендуется использовать универсальный Dictionary<TKey,TValue> класс. Дополнительные сведения см. в разделе неуниверсальные коллекции не следует использовать для GitHub.

Объекты, используемые в качестве ключей, должны Hashtable переопределять Object.GetHashCode метод (или IHashCodeProvider интерфейс) и Object.Equals метод (или IComparer интерфейс). Реализация методов и интерфейсов должна учитывать регистр одинаково. в противном случае Hashtable может вести себя неправильно. Например, при создании Hashtable необходимо использовать CaseInsensitiveHashCodeProvider класс (или любую реализацию без учета регистра IHashCodeProvider ) с CaseInsensitiveComparer классом (или любой реализацией без учета регистра IComparer ).

Более того, эти методы должны получить те же результаты при вызове с теми же параметрами, в то время как ключ существует в Hashtable . Альтернативой является использование Hashtable конструктора с IEqualityComparer параметром. Если равенство ключей было просто ссылочным равенством, то будет достаточно наследуемая реализация Object.GetHashCode и Object.Equals .

Ключевые объекты должны быть неизменными, если они используются в качестве ключей в Hashtable .

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

Коэффициент загрузки Hashtable определяет максимальное отношение элементов к сегментам. Меньшие коэффициенты нагрузки приводят к более быстрому среднему времени поиска за счет увеличения потребления памяти. По умолчанию коэффициент загрузки 1,0 обычно обеспечивает оптимальный баланс между скоростью и размером. При создании можно также указать другой коэффициент загрузки Hashtable .

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

Каждый ключевой объект в Hashtable должен предоставлять собственную хэш-функцию, доступ к которой можно получить, вызвав GetHash . Однако любой объект, реализующий IHashCodeProvider функцию, можно передать в Hashtable конструктор, и эта хэш-функция используется для всех объектов в таблице.

Емкость Hashtable — это количество элементов, которые Hashtable может содержать. Когда элементы добавляются в Hashtable , емкость автоматически увеличивается по мере необходимости путем перераспределения.

foreach Оператор является оболочкой для перечислителя, который разрешает только чтение из коллекции, а не запись в коллекцию.

Поскольку сериализация и десериализация перечислителя для Hashtable может привести к переупорядочению элементов, невозможно продолжить перечисление, не вызывая Reset метод.

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

Конструкторы

Инициализирует новый пустой экземпляр класса Hashtable с заданными по умолчанию начальной емкостью, показателем загрузки, поставщиком хэш-кода и объектом сравнения.

Инициализирует новый пустой экземпляр класса Hashtable посредством копирования элементов из указанного словаря в новый объект Hashtable. У нового объекта Hashtable исходная емкость равна числу копируемых элементов, и он обладает заданными по умолчанию показателем загрузки, поставщиком хэш-кода и объектом сравнения.

Инициализирует новый пустой экземпляр класса Hashtable посредством копирования элементов из указанного словаря в новый объект Hashtable. У нового объекта Hashtable исходная емкость равна числу копируемых элементов, и он обладает заданным по умолчанию показателем загрузки и указанным объектом сравнения IEqualityComparer.

Инициализирует новый пустой экземпляр класса Hashtable посредством копирования элементов из указанного словаря в новый объект Hashtable. У нового объекта Hashtable исходная емкость равна числу копируемых элементов, и он обладает заданным по умолчанию показателем загрузки и указанными поставщиком хэш-кода и объектом сравнения. Этот API устарел. См. Hashtable(IDictionary, IEqualityComparer) для альтернативных шагов.

Инициализирует новый пустой экземпляр класса Hashtable посредством копирования элементов из указанного словаря в новый объект Hashtable. У нового объекта Hashtable исходная емкость равна числу копируемых элементов, и он обладает указанным показателем загрузки и заданными по умолчанию поставщиком хэш-кода и объектом сравнения.

Инициализирует новый пустой экземпляр класса Hashtable посредством копирования элементов из указанного словаря в новый объект Hashtable. У нового объекта Hashtable исходная емкость равна числу копируемых элементов, и он обладает указанными показателем загрузки и объектом сравнения IEqualityComparer.

Инициализирует новый пустой экземпляр класса Hashtable посредством копирования элементов из указанного словаря в новый объект Hashtable. У нового объекта Hashtable исходная емкость равна числу копируемых элементов, и он обладает указанными показателем загрузки, поставщиком хэш-кода и объектом сравнения.

Инициализирует новый пустой экземпляр класса Hashtable с заданными по умолчанию исходной емкостью и показателем загрузки и указанным объектом сравнения IEqualityComparer.

Инициализирует новый пустой экземпляр класса Hashtable с заданными по умолчанию исходной емкостью и показателем загрузки и указанными поставщиком хэш-кода и объектом сравнения.

Инициализирует новый пустой экземпляр класса Hashtable с указанной исходной емкостью и заданными по умолчанию показателем загрузки, поставщиком хэш-кода и объектом сравнения.

Инициализирует новый пустой экземпляр класса Hashtable с указанными исходной емкостью и объектом сравнения IEqualityComparer и заданным по умолчанию показателем загрузки.

Инициализирует новый пустой экземпляр класса Hashtable с указанными исходной емкостью, поставщиком хэш-кода и объектом сравнения и заданным по умолчанию показателем загрузки.

Инициализирует новый пустой экземпляр класса Hashtable с указанными исходной емкостью и показателем загрузки и заданными по умолчанию поставщиком хэш-кода и объектом сравнения.

Инициализирует новый пустой экземпляр класса Hashtable с указанными исходной емкостью, показателем загрузки и объектом сравнения IEqualityComparer.

Инициализирует новый пустой экземпляр класса Hashtable с указанными начальной емкостью, показателем загрузки, поставщиком хэш-кода и объектом сравнения.

Инициализирует новый пустой экземпляр класса Hashtable, который может быть сериализован с помощью объектов SerializationInfo и StreamingContext.

Свойства

Получает или задает интерфейс IComparer для использования применительно к коллекции Hashtable.

Возвращает число пар "ключ-значение", содержащихся в словаре Hashtable.

Получает объект IEqualityComparer, предназначенный для использования применительно к коллекции Hashtable.

Получает или задает объект, который может распределять хэш-коды.

Получает значение, указывающее, имеет ли список Hashtable фиксированный размер.

Получает значение, указывающее, является ли объект Hashtable доступным только для чтения.

Возвращает значение, показывающее, является ли доступ к коллекции Hashtable синхронизированным (потокобезопасным).

Возвращает или задает значение, связанное с указанным ключом.

Получает коллекцию ICollection, содержащую ключи из коллекции Hashtable.

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

Возвращает интерфейс ICollection, содержащий значения из Hashtable.

Методы

Добавляет элемент с указанными ключом и значением в словарь Hashtable.

Удаляет из коллекции Hashtable все элементы.

Создает неполную копию Hashtable.

Определяет, содержит ли объект Hashtable указанный ключ.

Определяет, содержит ли коллекция Hashtable указанное значение.

Копирует элементы коллекции Hashtable в экземпляр класса одномерного массива Array по указанному индексу.

Определяет, равен ли указанный объект текущему объекту.

Возвращает объект IDictionaryEnumerator, осуществляющий перебор Hashtable.

Возвращает хэш-код указанного ключа.

Служит хэш-функцией по умолчанию.

Реализует интерфейс ISerializable и возвращает данные, необходимые для сериализации коллекции Hashtable.

Возвращает объект Type для текущего экземпляра.

Сравнивает указанный объект класса Object с указанным ключом, который содержится в коллекции Hashtable.

Создает неполную копию текущего объекта Object.

Реализует интерфейс ISerializable и вызывает событие десериализации при завершении десериализации.

Удаляет элемент с указанным ключом из Hashtable.

Возвращает синхронизированную (потокобезопасную) оболочку коллекции Hashtable.

Возвращает строку, представляющую текущий объект.

Явные реализации интерфейса

Возвращает перечислитель, который осуществляет итерацию по коллекции.

Методы расширения

Приводит элементы объекта IEnumerable к заданному типу.

Выполняет фильтрацию элементов объекта IEnumerable по заданному типу.

Позволяет осуществлять параллельный запрос.

Преобразовывает коллекцию IEnumerable в объект IQueryable.

Применяется к

Потокобезопасность

Hashtable является потокобезопасным для использования несколькими потоками чтения и одним потоком записи. Он является потокобезопасным для использования с несколькими потоками, когда только один из потоков выполняет операции записи (обновления), что позволяет выполнять чтение без блокировки, при этом модули записи сериализуются в Hashtable . Для поддержки нескольких модулей записи все операции в Hashtable должны выполняться через оболочку, возвращенную Synchronized(Hashtable) методом, при условии, что нет потоков, считывающих Hashtable объект.

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

Чтобы понять, что такое хеш-таблица, вспомним массив. Мы можем получить доступ к элементу с помощью его ключа, причем может быть такой случай, что есть ячейки содержащие элементы и есть не содержащие.
Представим ситуацию, что нам нужно найти элемент, например, массив состоит из строк большой длины. Нам придется нашу подстроку поиска сравнивать со всеми элементами массива, что неудобно, так как поиск займет O(n). НО мы хотим O(1). Решение есть! Использовать специальную хеш функцию, для того, чтобы мы имели доступ по индексу.

Каждой строке соответствует индекс равный (n=длина строки-1). Например: строка "Alex" индекс 3. Вот так можно записать строки.
Хеш функция у нас будет: Hash_Func(string)=Strlen(string) (то есть вычисление длины).
Доступ к массиву мы получаем вот так: Mas[Hash_Func(string)].

Разрешение случаев с коллизией является важной задачей Computer Science. Решениями проблемы являются:

Метод цепочек (открытое хеширование).
Метод открытой адресации (закрытое хеширование).

Идея метода цепочек состоит в том, что все элементы множества, которые относятся к одному и тому же ключу входят в связный список.

Итак! В этом примере, в i позициях содержится указатель на голову списка. Т.е. в массиве с ячейками (1,3,4); в остальных других хранится null (0,2,5);

Возвращаясь к нашему примеру с именами, переделаем его в соответствии с новым методом:
length value
------------------------
2 *head1 ["Joe"->"Rex"->Null]
3 *head2 ["Alex"->"Petr"->"Oleg"->Null]
4 *head3 ["Pavel"->Null]
В этом примере 0,1,5 элементы указатели равны Null
Процедура вставки происходит так: Вычисляется хеш-функция от строки и вставляется в голову списка (push_front) на определенный индекс равный значению функции.
Вставка происходит за O(1).
Поиск или удаление элемента зависит от длины списка, худший случай: O(n) - когда, все элементы хешируются в одну и ту же ячейку. Если функция распределяем n ключей по m ячейкам таблицы равномерно, то в каждом списке будет содержаться порядка k=n/m ключей. Это число называется коэффициентом заполнения хеш-таблицы. В этом случае время поиска: O(1+k), это показано в книжке Кормана, могу скинуть ссылку на нее, если интересно.
Добавлю, что в случае, когда коэффициент заполнения будет слишком велик, надо будет увеличить размер массива и, возможно, перестроить таблицу.

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

Общий прием состоит в следующем: если хеш-функция вырабатывает позицию для первого кандидата i = Hash_Func(key) Mod (capacity) , то последующие позиции определяются как i + increment , i +2 * increment , i +3 * increment и так далее, все по модулю capacity . Величина increment вычисляется как:
Hash_Func(key) Mod (capacity -1)

i,i1,i2 ячейки заняты, i=2, i1=4, i2=6, i3=8, capacity=11
Последующие index=i+increment (increment = 2 Mod 10 = 2 )

В хэш-таблице обработка новых индексов производится при помощи ключей. А элементы, связанные с этим ключом, сохраняются в индексе. Этот процесс называется хэшированием.

Пусть k — ключ, а h(x) — хэш-функция.

Тогда h(k) в результате даст индекс, в котором мы будем хранить элемент, связанный с k .

Коллизии

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

Есть несколько методов борьбы с коллизиями:

Метод цепочек.
Метод открытой адресации: линейное и квадратичное зондирование.

1. Метод цепочек

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

Если j — ячейка для нескольких элементов, то она содержит указатель на первый элемент списка. Если же j пуста, то она содержит NIL .

Псевдокод операций

2. Открытая адресация

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

Существует несколько видов открытой адресации:

a) Линейное зондирование

Линейное зондирование решает проблему коллизий с помощью проверки следующей ячейки.

h(k, i) = (h′(k) + i) mod m ,

Если коллизия происходит в h(k, 0) , тогда проверяется h(k, 1) . То есть, значение i увеличивается линейно.

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

b) Квадратичное зондирование

Работает оно так же, как и линейное — но есть отличие. Оно заключается в том, что расстояние между соседними ячейками больше (больше одного). Это возможно благодаря следующему отношению:

c₁ и c₂ — положительные вспомогательные константы,
i =

c) Двойное хэширование

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

h(k, i) = (h1(k) + ih2(k)) mod m

«Хорошие» хэш-функции

«Хорошие» хэш-функции не уберегут вас от коллизий, но, по крайней мере, сократят их количество.

Ниже мы рассмотрим различные методы определения «качества» хэш-функций.

1. Метод деления

Если k — ключ, а m — размер хэш-таблицы, то хэш-функция h() вычисляется следующим образом:

Например, если m = 10 и k = 112 , то h(k) = 112 mod 10 = 2 . То есть, значение m не должно быть степенью 2. Это связано с тем, что степени двойки в двоичном формате — 10, 100, 1000… При вычислении k mod m мы всегда будем получать p-биты низшего порядка.

2. Метод умножения

kA mod 1 отделяет дробную часть kA ,
⌊ ⌋ округляет значение
A — произвольная константа, значение которой должно находиться между 0 и 1. Оптимальный вариант ≈ (√5-1) / 2, его предложил Дональд Кнут.

3. Универсальное хеширование

В универсальном хешировании хеш-функция выбирается случайным образом и не зависит от ключей.

Читайте также: