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

Звучит знакомо? Объекты JavaScript! По сути, объекты создаются с помощью хеш-таблиц.

Из общего обзора, хеш-таблица состоит из:

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

В этом простом примере ниже хранятся телефонные номера людей для быстрого поиска.

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

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

Столкновения

Что, если эта волшебная хеш-функция отображает два разных ключа на один и тот же индекс? Это называется столкновением. В приведенном ниже примере Джон Смит и Сандра Ди хэшировали по одному и тому же адресу корзины # 152.

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

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

Изменение размера

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

По статистике, лучшая производительность для хеш-таблицы - это работа при коэффициенте загрузки от 25% до 75%.

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

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

  • Если количество пар ключ-значение / количество сегментов
  • Если количество пар "ключ-значение" / количество сегментов составляет ›75%, удвойте размер хранилища.
  • Все пары "ключ-значение" в хранилище должны быть повторно хешированы с использованием хэш-функции нового размера в качестве параметра.
  • Переместить пары "ключ-значение" на новый сопоставленный индексный адрес, предоставленный хеш-функцией.
  • Необходимо удалить старое расположение пары "ключ-значение".

Сложность времени

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

Сложность по времени для вставки, извлечения и удаления составляет постоянное время или O (1). Если набор данных был небольшим или имел миллионы записей, время доступа к данным не зависело от количества записей.

Это основано на предположении, что используемая хеш-функция хороша.

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

Вот пример простой структуры данных хеш-таблицы в JavaScript.

Это конец 3 недели Hack Reactor. По-прежнему впечатлены тем, как студенты дневной формы обучения усваивают всю эту информацию к 4-му дню!