Ошибки, сложный материал, вопросы >
Нашли опечатку или неточность?

Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

Что-то не получается или материал кажется сложным?

Загляните в раздел «Обсуждение»:

  • задайте вопрос нашим менторам. Вы быстрее справитесь с трудностями и прокачаете навык постановки правильных вопросов, что пригодится и в учёбе, и в работе программистом;
  • расскажите о своих впечатлениях. Если курс слишком сложный, подробный отзыв поможет нам сделать его лучше;
  • изучите вопросы других учеников и ответы на них. Это база знаний, которой можно и нужно пользоваться.
Об обучении на Хекслете

Хеш-таблицы

Ассоциативный массив — абстрактный тип данных, с помощью которого хранятся пары ключ-значение. У него есть и другие названия: "словарь", "мап" (от слова map). В разных языках ему соответствуют разные типы данных. В JavaScript — это Object, в других языках:

  • Ruby — Hash
  • Lua — Table
  • Python — Dictionary
  • Elixir/Java — Map

Для чего он нужен? Ассоциативные массивы крайне популярны в прикладном программировании. С их помощью удобно представлять составные данные, содержащие множество различных параметров. Фактически все предыдущие уроки по объектам в JavaScript были посвящены тому, как использовать объекты в качестве ассоциативных массивов.

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

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

Хеширование

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

Хеширование — операция, которая преобразует любые входные данные в строку (реже число) фиксированной длины. Функция, реализующая алгоритм преобразования, называется "хеш-функцией", а результат называют "хешем" или "хеш-суммой". Наиболее известны CRC32, MD5 и SHA (много разновидностей).

// В JavaScript нет встроенной поддержки алгоритма хеширования crc32 (удобен для наглядности)
// Поэтому используется сторонняя библиотека
import crc32 from 'crc-32';

const data = 'Hello, world!'; // Любые данные которые мы хотим хешировать
const hash = crc32.str(data);

// Хеш всегда одинаковый для одних и тех же данных!
console.log(hash); // => -337197338

С хешированием мы встречаемся в разработке часто. Например, идентификатор коммита в git 0481e0692e2501192d67d7da506c6e70ba41e913 не что иное, как хеш, полученный в результате хеширования данных коммита.

После того как хеш получен, его можно преобразовать в индекс массива, например, через получение остатка от деления:

const index = Math.abs(hash) % 1000; // по модулю
console.log(index); // => 338

хеширование

За кулисами

Рассмотрим процесс добавления нового значения в ассоциативный массив (напомню, в JavaScript представлен типом данных Object). Программист пишет:

const data = {};
data['key'] = 'value';

Такая простая, на первый взгляд, строчка, запускает целый процесс. Ниже его грубое описание, без деталей и с упрощениями:

// Для простоты показано на JavaScript, хотя в реальности всё это происходит на более низком уровне

// 1. Создание ассоциативного массива приводит к инициализации индексированного массива внутри интерпретатора.
const internal = [];
// Во время присвоения значения `data['key'] = 'value'`, интерпретатор выполняет несколько действий:

// 2. Хеширует ключ. Результатом хеширования становится число.
const hash = crc32.str('key');
// 3. Число, полученное на предыдущем шаге преобразуется в индекс массива.
const index = Math.abs(hash) % 1000;
// В значение внутреннего индексированного массива, по найденному индексу, записывается ещё один массив,
// первым элементом которого становится ключ `'key'`, а вторым значение `'value'`.
internal[index] = ['key', 'value'];

Почему такая странная структура для хранения? Зачем там нужен ключ? Ответ на этот вопрос будет ниже, там где мы поговорим про коллизии.

Теперь посмотрим на чтение:

const data = {};
data['key'] = 'value';
console.log(data['key']); // => "value"
// Для простоты показано на JavaScript, хотя в реальности всё это происходит на более низком уровне

// 1. Хешируется ключ. Результатом хеширования становится число.
const hash = crc32.str('key');
// 2. Число, полученное на предыдущем шаге преобразуется в индекс массива.
const index = Math.abs(hash % 1000);

// 3. Если индекс существует, то извлекается массив, который находился внутри, и возвращается наружу.
return internal[index]; // ['key', 'value']

Коллизии

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

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

// Пример коллизии

// Две разных строчки возвращают одинаковый хеш!
crc32.str('aaaaa0.462031558722291'); // 1938556049
crc32.str('aaaaa0.0585754039730588'); // 1938556049

Метод цепочек

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

Разрешение коллизий методом цепочек

Метод открытой адресации

Ещё один способ называется метод открытой адресации. В таблице хранятся непосредственно пары ключ-значение. При возникновении коллизии используется специальный алгоритм вставки элемента. Он проверяет ячейки таблицы в некотором порядке и добавляет новый элемент в первую свободную ячейку. Этот же алгоритм используется для поиска значений.

Разрешение коллизий методом открытой адресации

Коллизии не так редки, как может показаться. Убедиться в этом можно, изучив парадокс дней рождений.


<span class="translation_missing" title="translation missing: ru.web.courses.lessons.mentors.mentor_avatars">Mentor Avatars</span>

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят менторы из команды Хекслета или другие студенты.

Для полного доступа к курсу, нужна профессиональная подписка

Профессиональная подписка откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, даст возможность обращаться за помощью к менторам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
115
курсов
892
упражнения
2241
час теории
3196
тестов

Зарегистрироваться

или войти в аккаунт

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 115 курсов, 2000+ часов теории
  • 800 практических заданий в браузере
  • 250 000 студентов

Нажимая кнопку «Зарегистрироваться», вы даёте своё согласие на обработку персональных данных в соответствии с «Политикой конфиденциальности» и соглашаетесь с «Условиями оказания услуг».

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Rambler
Логотип компании Bookmate
Логотип компании Botmother

Есть вопрос или хотите участвовать в обсуждении?

Зарегистрируйтесь или войдите в свой аккаунт

Нажимая кнопку «Зарегистрироваться», вы даёте своё согласие на обработку персональных данных в соответствии с «Политикой конфиденциальности» и соглашаетесь с «Условиями оказания услуг».