Как работает хеш-таблица
Что такое хеш-таблица?
Хеш-таблица — это структура данных, в которой данные хранятся в виде пар ключ-значение. Она также называется словарем или ассоциативным массивом и хранит данные таким образом, что позволяет выполнять поиск и вставку за постоянное время O(1). Эти свойства хэша делают его одной из самых полезных структур данных в наборе инструментов программиста.
Главный вопрос — откуда такая скорость и как она работает?
Проблемы, которые решают хеш-таблицы
Представим на секунду, что мы храним все записи в массиве или связанном списке. Когда нам нужно что-то найти, мы должны пройти по всем элементам, чтобы найти один. Это может занять очень много времени, в зависимости от количества элементов.
Используя хеш-таблицу, мы можем перейти непосредственно к ячейке со значением, которое нам нужно найти, просто вычислив хеш-функцию для этого ключа.
Как работает хеш-таблица?
Хэш-таблица хранит все значения в store-группах (бункерах) в структуре данных, подобной массиву.
При добавлении новой пары «ключ-значение» в хеш-таблицу нам нужно вычислить, в какое именно «хранилище» будет вставлена наша пара. Сделать это можно с помощью .hashметода (хеш-функции).
Результирующее значение хеш-функции является псевдослучайным числом, то есть всегда будет выдавать одно и то же число для одного и того же значения.
В Ruby — «hash» метод относится к к модулю «Kernel’ . Таким образом , он существует практически для каждого объекта. «hash», грубо говоря, возвращает эквивалент по ссылке к месту памяти , где текущий объект будет хранятся. Но для строк, расчет является по отношению к по значению.
Получив псевдослучайное число — мы должны вычислить номер нашего «хранилища», где будет лежать наша пара ключ-значение.
‘а’ . hash % 16 => 9
a — ключ,
16 — сумма по хранению,
9 — номер хранилища
Поэтому, когда вы добавляете ключ / значение в хэш, он всегда будет привязан к одному и тому же репозиторию. А из-за того, что hash возвращает псевдослучайное число — наши пары будут равномерно распределены между всеми хранилищами.
Худший результат — когда результат функции дает такое же число. Ведь в таком результате — все данные попадут в одно «хранилище» и в этом случае будет не лучше простого массива.
Итого: как работает прошивка
- Первое, что делает ruby, — это берет хэш ключа, используя внутреннюю хеш-функцию.
: c . hash # => 2782
- После получения случайного числа (хеш-значения) с помощью операции по модулю (2782% 16) мы получим номер хранилища, в котором будет храниться наша пара ключ-значение.
: d.hash % 16
- Добавить пару «ключ-значение» в связанный список соответствующей корзины
Подводя итоги: как работает поиск в хеш-таблицах
Первый и второй шаги такие же:
- Определить «хеш-функцию»;
- Найдите «хранилище»;
- Затем выполните итерацию по небольшому списку и получите хеш-элемент.
В Ruby усредненное количество элементов на одну ячейку равно 5.
Подробнее
ST_DEFAULT_MAX_DENSITY 5
Столкновения и рост (Rehash) в хеш-таблицах
Как следствие, с ростом количества добавляемых записей плотность элементов будет увеличиваться в каждом репозитории (на самом деле размер хеш-таблицы составляет всего 16 хранилищ).
Если плотность элементов большая, например 10_000 элементов в одном «хранилище», то при поиске нам придется пересмотреть все элементы этого связанного списка, чтобы найти соответствующую запись. И мы вернемся к времени O (n), что в данном случае очень плохо.
Чтобы избежать такой ситуации, применяется тактика: перехеширование таблицы (увеличение таблицы и повторная компиляция ячеек).
Что это означает?
Это означает, что размер хеш-таблицы будет увеличен (до следующего числа — 16, 32, 64, 128, …) и для всех текущих элементов будет пересчитана позиция в «хранилищах».
«Повторное хеширование» происходит, когда количество всех элементов превышает максимальную плотность, умноженную на текущий размер таблицы.
81 > 5 * 16 — rehash будет будет будет называться, когда мы добавили 81 элемент в в таблице .
num_entries> ST_DEFAULT_MAX_DENSITY * table-> num_bins
Ruby (до Ruby 2.2.0) использует простые числа для определения размеров сегмента (11, 19, 37) см. Подробнее , где начальный размер сегмента был 11.
Но после 2.2.0 было решено использовать размеры, соответствующие «степени двойки». «(16, 32, 64, 128,…). См. Еще
ST_DEFAULT_INIT_TABLE_SIZE 16
Когда количество записей достигает максимально возможного значения для текущей хеш-таблицы, количество «хранилищ» в этой хеш-таблице увеличивается (это принимает следующий размерный номер из 16, 32, 64, 128), и он пересчитывает и исправляет позиции для всех «записей» в этом хэше.
Вот наглядная демонстрация того, как Ruby 2.3.4 ведет себя, когда вы добавляете новый элемент в хеш-таблицу относительно времени.
На графике вы можете видеть, что некоторые вставки вызывают «скачки» на временной шкале. В это время происходит «Rehash» хеш-таблицы. После перехеширования вы можете увидеть, что время вставки следующего элемента упало на несколько мс.
В Ruby 2.0+ были удалены лишние структуры данных для меньших хешей. Для повышения производительности они используют линейный поиск. Подробнее
Вывод
Структура хеш-данных — обычное дело в программировании. Реализация хэша такая же, как в Ruby , Java, Python. Нам просто нужно понимать плюсы и минусы его использования.
Полезные ссылки:
