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

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

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

Если в этом справочнике 100 позиций и на каждую просмотренную строчку Егор тратит по 0.2с, то вы в худшем случае будете ждать 20 секунд. А если бы справочник был сортирован по алфавиту, то Егор пользовался бы бинарным поиском, что займет всего 1.4с. Это уже гораздо быстрее, но всё ещё не так мгновенно.

Как сделать мгновенно? Подойдите на кассу к опытному продавцу Галине, и алгоритм будет уже совсем другим, ведь она уже знает все коды выпечки наизусть. И вместо того, чтобы искать во всем справочнике, Галина просто посмотрит на слойку и достанет из памяти запись «Слойка с сыром — код 322» — не прибегая к справочнику, почти мгновенно, за O(1). Примерно по такому же принципу работают и хеш-таблицы: вместо неясной адресации по числам они дают нам возможность связать ключ-строчку «Слойка с сыром» с её кодом — 322.

Хеш-таблица булочек

Мы ассоциируем определённый ключ с его значением, поэтому такие структуры данных ещё называют ассоциативными массивами.

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