Map_HashTable

Словарь на базе хеш-таблицы

Введение

Словари (ассоциативные массивы, map)

Ассоциативный массив — абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу:

• INSERT(ключ, значение)
• FIND(ключ)
• REMOVE(ключ)

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

Хеш-таблица

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

Хэш-таблица – массив ключей с особой логикой:

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

Сложность всех операций O(1).

Хеш-функция

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

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

Основная чаcть

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

Два соседних натуральных числа всегда будут взаимно просты

Разрешение коллизий - метод цепочек

Каждая ячейка массива является указателем на связный список.

Добавление ключа

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

Время работы:

В лучшем случае: O(1)

В худшем случае:

• если не требуется проверять наличие дубля - O(1)
• иначе O(n)

Удаление ключа

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

Время работы:

В лучшем случае: O(1)

В худшем случае: O(n)

Поиск ключа

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

Время работы:

В лучшем случае: O(1)

В худшем случае: O(n)

Среднее время работы операции поиска, вставки (с
проверкой на дубликаты) и удаления в хеш-таблице,
реализованной методом цепочек – O(1+α), где α –
коэффициент заполнения таблицы.
Среднее время работы – математическое ожидание
времени работы в зависимости от исходного ключа
Время работы для обработки одного ключа T(k) зависит от
длины цепочки и равно 1+𝑁ℎ(𝑘), где 𝑁𝑖 - длина i-ой цепочки.
Предполагается, что хеш-функция равномерна, а ключи
равновероятностны.

Динамическая хеш-таблица

Изначально может быть неизвестно количество хранимых ключей. Коэффициент заполнения может приближаться к 1, а в реализации методом цепочек может быть больше 1. Среднее время работы для метода цепочек: O(1 + 𝛼) Среднее время работы для метода открытой адресации: O( 1 / (1 + 𝛼) )

Требуется динамически увеличивать размер таблицы.
Аналогично динамическому массиву. Процесс называется
«перехешированием».

Перехеширование

• Создать новую пустую таблицу. Размер новой таблицы может быть M2 = 1.5M1, где M1 – размер старой таблицы. Если размер таблицы должен быть простым, то следует использовать простое число близкое к 1.5M1

• Проитерировать старую таблицу. Каждый ключ старой таблицы перенести в новую. Для добавления в новую таблицу надо использовать другую хеш-функцию, возвращающую значения от 0 до M2-1

Когда выполнять перехеширование?

Для хеш-таблиц, реализованных методом цепочек

• Когда коэффициент заполнения близок к 1

Для хеш-таблиц, реализованных методом открытой адресации

• Когда коэффициент заполнения приближается к 2/3 или 3/4

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

✅ Перехешировние выполняется при load factor > 0.8 (load factor должен быть близок к 1 ps. для метода цепочек)

Дополнительная информация

exception

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

List

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

*&

указатель на указатель - что бы можно было менять указатель на обькет при рехешинге.

Разрешение коллизий. Метод открытой адресации

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

Плюсы:

• Не тратится память на хранение указателей списка

• Нет элементов хранящихся вне таблицы

Минусы

• Хеш-таблица может оказаться заполненной. Коэффициент заполнения не может быть больше 1.

• При приближении коэффициента заполнения к 1 среднее время работы поиска, добавления и удаления стремится к N

• Сложное удаление