Как реализовать простую хэш-таблицу в JavaScript

kak realizovat prostuyu hesh tabliczu v javascript

Алекс Надолин

Как красиво {}?

Это позволяет сохранять значения за ключом и получать их очень экономически эффективным способом (O(1)подробнее об этом позже).

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

Проблема

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

Вы когда-нибудь задумывались, как они работают? Как они такие чертовски быстры?

Ну, скажем, у JavaScript не было {} или new Map()и давайте реализуем наши собственные DumbMap!

Примечание о сложности

Прежде чем начать, нам нужно понять, как работает сложность функции: в Википедии есть хорошая информация о сложности вычислений, но я добавлю краткое объяснение для ленивых.

Сложность измеряет, сколько шагов требует наша функция — чем меньше шагов, тем быстрее выполнение (также известно как «время работы»).

Давайте посмотрим на следующий фрагмент:

function fn(n, m) {  return n * m}

Вычислительная сложность (отныне просто «сложность») fn есть O(1)что означает, что он постоянен (вы можете прочитать O(1) как «стоимость одна”): независимо от того, какие аргументы вы передаете, платформа, выполняющая этот код, должна выполнить только одну операцию (умножить n в m). Опять же, поскольку это одна операция, стоимость называется такой O(1).

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

function fn(n, m) {  let s = 0
  for (i = 0; i < 3; i++) {    s += n * m  }
  return s}

Можно подумать, что это сложность O(3)да?

Опять же, поскольку сложность измеряется в контексте очень больших аргументов, мы склонны отвергать константы и рассматривать O(3) такой же как и O(1). Итак, даже в этом случае мы бы сказали, что сложность fn есть O(1). Неважно, какое значение n и m вы всегда выполняете три операции, которые, опять же, являются постоянной стоимостью (следовательно O(1)).

Теперь этот пример несколько иной:

function fn(n, m) {  let s = []
  for (i = 0; i < n; i++) {    s.push(m)  }
  return s}

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

Другие примеры?

function fn(n, m) {  let s = []
  for (i = 0; i < 2 * n; i++) {    s.push(m)  }
  return s}

Это примеры циклов 2 * n раз, то есть сложность должна быть O(2n). Поскольку мы упоминали, что константы «игнорируются» при вычислении сложности функции, этот пример также классифицируется как O(n).

Еще один?

function fn(n, m) {  let s = []
  for (i = 0; i < n; i++) {    for (i = 0; i < n; i++) {      s.push(m)    }  }
  return s}

Вот мы зацикливаемся n и повторение цикла внутри основного цикла, то есть сложность «возведенная в квадрат» (n * n): если n 2, мы будем бежать s.push(m) 4 раза, если 3, мы запустим это 9 раз и так далее.

В этом случае сложность функции называется O(n²).

Последний пример?

function fn(n, m) {  let s = []
  for (i = 0; i < n; i++) {    s.push(n)  }
  for (i = 0; i < m; i++) {    s.push(m)  }
  return s}

В этом случае мы не имеем вложенных циклов, но мы дважды выполняем цикл по двум разным аргументам: сложность определяется как O(n+m). Кристально чистый.

Теперь, когда вы только что получили краткое вступление (или повторение) о сложности, очень легко понять, что функция со сложностью O(1) будет работать гораздо лучше, чем с O(n).

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

(Я всегда лежал на хэш-таблицах O(1)сложность, но просто читайте;))

Давайте создадим (тупу) хэш-таблицу

Наша хэш-таблица имеет 2 простых метода. set(x, y) и get(x). Давайте начнем писать код:

И давайте реализуем очень простой, неэффективный способ сохранять эти пары ключ-значения и получать их позже. Сначала мы начинаем с сохранения их во внутреннем массиве (помните, мы не можем использовать {} поскольку мы реализуем {} — кайф!):

Тогда это просто вопрос получения нужного элемента из списка:

Наш полный пример:

Наши DumbMap удивительно! Он работает сразу, но как он будет работать, когда мы добавим большое количество пар ключ-значения?

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

Результаты? Не слишком обнадеживающе:

with very few records in the map: 0.118mswith lots of records in the map: 14.412ms

В нашей реализации нам нужно прокрутить все элементы внутри this.list чтобы найти таковой с соответствующим ключом. Стоимость есть O(n)и это очень ужасно.

Сделайте это быстрее

Нам нужно найти способ избежать циклического просмотра нашего списка: время для размещения хеш обратно в хэш-таблица.

Вы когда-нибудь задумывались, почему эта структура данных называется a хеш стол? Это связано с тем, что функция хеширования используется для ключей, которые вы устанавливаете и получаете. Мы будем использовать эту функцию, чтобы превратить наш ключ в целое число iи сохраним наше значение в индексе i нашего внутреннего списка. Поскольку доступ к элементу по его индексу из списка имеет постоянную стоимость (O(1)), то хэш-таблица также будет иметь стоимость O(1).

Давайте попробуем это:

Здесь мы используем модуль string-hash, просто превращающий строку в числовой хеш. Мы используем его для хранения и получения элементов по индексу hash(key) нашего списка. Результаты?

with lots of records in the map: 0.013ms

Ш – О – Ш. Вот о чем я!

Нам не нужно перебирать все элементы в списке и получать элементы из DumbMap супер быстрый!

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

Стоимость выбора правильной функции хеширования

Конечно, Выбор функции быстрого хеширования очень важен. Если наши hash(key) выполняется через несколько секунд, наша функция будет довольно медленной независимо от ее сложности.

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

Смущенный? Рассмотрим коллизии поближе.

столкновение

Вы можете подуматьАх, хорошая функция хеширования никогда не создает коллизий!”: Ну, вернитесь в реальный мир и подумайте еще раз. Google удалось создать коллизии для алгоритма хеширования SHA-1, и это лишь вопрос времени или вычислительной мощности, когда функция хеширования будет сломать и вернет тот же хеш для 2 различных входных данных. Всегда предполагайте, что ваша функция хеширования создает коллизии и применяйте правильную защиту от таких случаев.

В этом случае давайте попробуем использовать a hash() функция, которая создает много коллизий:

Эта функция использует массив из 10 элементов для хранения значений, то есть элементы, вероятно, будут заменены – неприятная ошибка в нашем DumbMap:

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

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

Давайте сравним это с помощью нашего собственного hash() функция, генерирующая индексы от 1 до 10:

with lots of records in the map: 11.919ms

и с помощью хэш-функции from string-hashгенерирующий случайные индексы:

with lots of records in the map: 0.014ms

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

Обычно O(1)

Помните мои слова?

Хэш-таблицы имеют a O(1) сложность

Ну, я солгал: сложность хэш-таблицы зависит от выбранной вами функции хеширования. Чем больше столкновений вы генерируете, тем больше будет сложность O(n).

Функция хеширования, например:

function hash(key) {  return 0}

будет означать, что наша хэш-таблица имеет сложность O(n).

Вот почему, в общем, вычислительная сложность имеет три степени: лучший, средний и худший сценарии. Хэш-таблицы имеют a O(1) сложность в лучшем и среднем сценариях, но падают до O(n)в самом худшем случае.

Помните: хорошая функция хеширования является ключом к эффективной хэш-таблице — ни больше, ни меньше.

Больше о столкновениях…

Техника, которую мы использовали для фиксации DumbMap в случае столкновений называется отдельной цепочкой: мы сохраняем все пары ключей, генерирующих столкновение, в списке и проходим их в цикле.

Еще одна популярная техника – открытая адресация:

  • в каждом индексе нашего списка, который мы сохраняем одна и только одна пара ключ-значение
  • при попытке сохранить пару по индексу xесли уже есть пара ключ-значения, попробуйте сохранить нашу новую пару по адресу x + 1
  • если x + 1 взято, попробуйте x + 2 и так дальше…
  • при получении элемента хешируйте ключ и проверьте, элемент ли в этой позиции (x) соответствует нашему ключу
  • если нет, попробуйте получить доступ к элементу в позиции x + 1
  • промойте и повторяйте, пока не дойдете до конца списка или когда найдете пустой индекс — это значит, что нашего элемента нет в хэш-таблице

Умный, простой, элегантный и обычно очень эффективен!

Часто задаваемые вопросы (или TL; DR)

Хэширует ли хэш-таблица значения, которые мы сохраняем?

Нет, ключи хешируются, чтобы их можно было превратить в целые числа iа ключи и значения сохраняются в позиции i в списке.

Вызывают ли коллизии функции хеширования, используемые хэш-таблицами?

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

Используют ли хэш-таблицы внутренний список или связанный список?

Это зависит от того, оба могут работать. В наших примерах мы используем массив JavaScript ([]), которые можно динамически изменять:

> a = []
> a[3] = 1
> a[ <3 empty items>, 1 ]

Почему вы выбрали JavaScript для примеров? Массивы JS Являются хэш-таблицами!

Например:

>  a = [][]
> a["some"] = "thing"'thing'
> a[ some: 'thing' ]
> typeof a'object'

Я знаю, проклятый JavaScript.

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

Является ли ваш пример действительно хорошей реализацией хэш-таблицы? Действительно ли это ДА просто?

Нет, совсем нет.

Посмотрите на «Реализацию хэш-таблицы в JavaScript» Мэтта Цойнерта, поскольку это даст вам немного больше контекста. Есть еще многое, чтобы узнать, поэтому я также предлагаю вам посмотреть:

В конце…

Хэш-таблицы — это очень разумная идея, которую мы используем на регулярной основе: независимо от того, создаете ли вы словарь в Python, ассоциативный массив в PHP или карту в JavaScript. Все они разделяют одинаковые концепции и отлично работают, чтобы позволить нам сохранять и получать элемент по идентификатору по (вероятнее всего) постоянной стоимости.

Надеюсь, вам понравилась эта статья и не стесняйтесь поделиться со мной своими отзывами.

Особое спасибо Джо, который помог мне, просмотрев эту статью.

Привет!

Добавить комментарий

Ваш адрес email не будет опубликован.