Блог

Как работает хеш-таблица

Что такое хеш-таблица?

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

Главный вопрос — откуда такая скорость и как она работает?

Проблемы, которые решают хеш-таблицы

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

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

Как работает хеш-таблица?

Хэш-таблица хранит все значения в store-группах (бункерах) в структуре данных, подобной массиву.

При добавлении новой пары «ключ-значение» в хеш-таблицу нам нужно вычислить, в какое именно «хранилище» будет вставлена ​​наша пара. Сделать это можно с помощью .hashметода (хеш-функции).

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

В Ruby «hash» метод относится к к модулю «Kernel’ . Таким образом , он существует практически для каждого объекта. «hash», грубо говоря, возвращает эквивалент по ссылке к месту памяти , где текущий объект будет хранятся. Но для строк, расчет является по отношению к по значению.

Получив псевдослучайное число — мы должны вычислить номер нашего «хранилища», где будет лежать наша пара ключ-значение.

‘а’ . hash % 16 => 9

a ключ,

16 сумма по хранению,

9 номер хранилища

Поэтому, когда вы добавляете ключ / значение в хэш, он всегда будет привязан к одному и тому же репозиторию. А из-за того, что hash возвращает псевдослучайное число — наши пары будут равномерно распределены между всеми хранилищами.

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

Итого: как работает прошивка

  1. Первое, что делает ruby, — это берет хэш ключа, используя внутреннюю хеш-функцию.

: c . hash # => 2782

  1. После получения случайного числа (хеш-значения) с помощью операции по модулю (2782% 16) мы получим номер хранилища, в котором будет храниться наша пара ключ-значение.

: d.hash % 16

  1. Добавить пару «ключ-значение» в связанный список соответствующей корзины

Подводя итоги: как работает поиск в хеш-таблицах

Первый и второй шаги такие же:

  1. Определить «хеш-функцию»;
  2. Найдите «хранилище»;
  3. Затем выполните итерацию по небольшому списку и получите хеш-элемент.

В 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. Нам просто нужно понимать плюсы и минусы его использования.

Полезные ссылки:

Теги
Кнопка «Наверх»
Закрыть
Закрыть