Основы алгоритмов и структур данных
2026-02-26 23:26 Diff
https://ru.hexlet.io/courses/basic-algorithms/lessons/hash/theory_unit

Ранее в курсе мы изучили метод перебора и сталкивались с задачей про европейские столицы. Снова попробуем решить эту задачу, но выберем новый, более продуктивный способ.

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

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

Временная сложность такого алгоритма составляет O(n), что довольно медленно. Бинарный поиск позволяет сократить это время до O(logn). На большой таблице из миллиона записей среднее количество сравнений для линейного поиска равно 500000, а для бинарного — всего 10.

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

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

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

Разреженные массивы

Простейший способ определить столицу по году основания — использовать массив:

Такой массив занимает много памяти. В нем хранится всего 15 городов, но при этом размер массива — это целых 1873 элемента:

Так получилось потому, что индексами в массиве могут быть только последовательные целые числа, начиная с 0. Если мы добавляем элемент с индексом 752, в массив добавляются и неопределенные элементы с индексами от 0 до 751. Длина массива получилась равной 1873, потому что:

  • Наибольший год основания — 1872
  • Первым в массиве всегда стоит элемент с индексом 0

Если мы применим массив, доступ к элементам выполнится очень быстро — за константное время O(1). Но при этом мы впустую расходуем память — в нашем примере массив заполнен всего на 0,8%.

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

Возьмем числа 0, 1, 2 и 3, поделим их на 20 и получим такой результат:

  • 0 делить на 20 = 0
  • 1 делить на 20 = 0.05
  • 2 делить на 20 = 0.1
  • 3 делить на 20 = 0.15

Целая часть этих чисел будет равна 0, пока мы не доберемся до такой операции:

19 делить на 20 = 0.95

Начиная с 20, целая часть после деления будет равна 1:

  • 20 делить на 20 = 1
  • 21 делить на 20 = 1.05

Начиная с 40, целая часть будет равна 2.

Получается, что после преобразования числа схлопываются:

  • От 0 до 19 → 0
  • От 20 до 39 → 1
  • От 40 до 59 → 2 и так далее

Чтобы получать целую часть, воспользуемся стандартной функцией Math.floor:

Чтобы узнать, какой город основан в 1191 году, мы проверяем элемент с индексом 1191/20:

У такого подхода есть недостаток — довольно трудно предсказать размер массива. Когда речь идет о годах основания, мы можем проанализировать данные и прикинуть, что каждые двадцать лет можно схлопнуть в один элемент.

Для чисел 0 до 1999 нам достаточно массива из ста элементов. Последний элемент такого уплотненного массива имеет индекс 99, а Math.floor(1999/20) как раз равно 99.

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

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

Модульная арифметика

Предположим, мы фиксируем размер массива. Пусть у нас будет массив из ста элементов:

Мы хотим сохранить в него несколько элементов, но их индексы могут быть произвольными целыми числами. Чтобы преобразовать индекс в число от 0 до 99, мы должны вычислить остаток от деления индекса на 100.

Общее правило такое:

Остатки от деления любого числа на n всегда находятся в диапазоне от 0 до n-1

Это правило поможет нам работать с массивами любого размера.

Иногда вместо «остаток от деления на n» говорят «модуль по основанию n». В JavaScript и многих других языках программирования для вычисления модуля используют оператор %:

Решим нашу задачу со столицами с помощью модуля:

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

Попробуем узнать, какой город основан в 1167 году. Если верить нашей таблице, это Копенгаген. Но программа говорит совсем другое:

Минск основан в 1067 году, а Копенгаген — в 1167. Годы отличаются, но у них один и тот же остаток от деления на 100, а именно 67.

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

Коллизии

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

  • Год — это индекс, по которому мы сохраняем и извлекаем данные. Обычно его называют ключом
  • Название — это значение

Попробуем реализовать в коде:

Мы уже разработали структуру данных LinkedList, поэтому мы можем просто импортировать ее.

Размер массива capitals всегда будет равен ста элементам.

По умолчанию все ячейки массива пусты, и связный список создается только при первой записи в ячейку. В каждом списке может храниться несколько элементов. Чтобы различать их, мы сохраняем не просто значение, а пару из ключа (key) и значения (value).

При поиске точно также вычисляем индекс:

Если в ячейке ничего нет, значит, мы ничего и не записывали.

Но если в ячейке что-то есть, то это список, по которому мы пробегаем и пытаемся найти пару с заданным ключом (key).

Обнаружив пару, возвращаем ее значение (value).

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

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

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

Хэш-функция

Теперь попробуем решить обратную задачу — определять год основания столицы, зная ее название. Заглянем в таблицу в начале урока и вспомним, что год основания Мадрида — 856, а Москвы — 1147.

Наша структура данных может хранить значения с любым целочисленным ключом, не только с годом. Но «Мадрид» и «Москва» — это не числа, а строки.

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

Слово «Мадрид» хранится как последовательность чисел 1052, 1072, 1076, 1088, 1080 и 1076. В простейшем случае мы могли бы использовать для вычисления индекса код первой буквы — в нашем примере 1052. Но это значит все города на М (Мадрид, Москва и Минск) попадут в один и тот же список. В таком случае скорость поиска будет не очень высокой.

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

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

Хороший результат в таком случае даст так называемая полиномиальная функция.

Попробуем применить ее к нашей задаче с городами. Пусть коды символов строки длины n будут равны c0, c1, ..., cn-1. Возьмем число k, которое будет больше кода любого символа — скажем, k = 65537.

У нас получилось такое выражение:

Число k достаточно большое. На каждом шаге нам приходится возводить его в возрастающую степень, поэтому выражение может оказаться просто огромным. Для слова "Мадрид" мы получим 1300923352423037265600321836.

На практике для ускорения вычислений и для удобства используют не все выражение, а только остаток от его деления на другое число — m:

Обычно модуль m делают равным большому простому числу или большому круглому числу — например, миллиону или миллиарду. Часто в качестве модуля выбирают степень числа 2 — к примеру, 2^32 или 2^64.

Чтобы промежуточные числа не становились слишком большими, все сложения и умножения выполняют по модулю m. Другими словами, остаток от деления вычисляется сразу после сложения или умножения.

Здесь в качестве модуля мы выбрали 2**20, то есть 2 в степени 20 (2^20). Это число равно 1048576 и часто используется программистами, потому что очень близко к миллиону. Слово мегабайт традиционно означает именно 1048576 байт, а не миллион, как можно было бы ожидать.

Сейчас комитет по стандартизации мер и весов рекомендует термины «мебибайт» для 1048576 байтов и «мегабайт» для 1000000 байтов, но большинство программистов все еще не используют эту новую рекомендацию.

Переменная k_i на каждом шаге цикла умножается на k. Она принимает значения 1, затем k, затем k умноженное на 2, и так далее. В переменной result накапливается результат вычислений.

Функция называется hash, и это неслучайно. В переводе с английского слово hash означает «мелко крошить, перемешивать».

Функция перемешивает исходные данные так, чтобы получилось число, похожее на случайное:

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

В Python для вычисления хешей можно использовать функцию hash(), в Java — метод hashCode(), в C# — метод GetHashCode(). В JavaScript нет готовой хеш-функции — считается, что все нужное уже есть в языке.

Название функции дало название всей структуре данных. Обычно ее называют хеш-таблицей (hash table или hashmap). Очень часто это название сокращают просто до хеша. Другие распространенные названия — словарь (dictionary) и ассоциативный массив (associative array).

Худший случай

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

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

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

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

Обычно подсчитывают коэффициент заполнения хеш-таблицы (load factor) — это частное от деления количества вставленных элементов на размер внутреннего массива. Если он достигает заранее выбранного порога в 60–80%, внутренний массив увеличивают вдвое, а индексы всех элементов пересчитывают.

Точно также, если коэффициент заполнения становится слишком маленьким, 20–25%, массив уменьшают вдвое. У массива есть нижняя граница в 128 или 256 элементов, чтобы не перестраивать его слишком часто, пока он маленький.

Хэш-таблицы и функция вставки

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

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

Именно за это отвечает вложенный цикл:

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

Выводы

В этом уроке мы изучили хэш-таблицы и научились с ними работать. Повторим основные тезисы:

  • Хэш-таблица обеспечивает временную сложность O(1). Она похожа на массив, потому что в ней тоже есть операция индексации. В качестве индекса можно использовать практически любые структуры данных — строки, дату и время, массивы.
  • Массивы, в которых большая часть элементов не определена, называются разреженными. Чтобы сэкономить память, программисты стараются уплотнить массив, но тогда довольно трудно предсказать размер массива.
  • Остатки от деления любого числа на n всегда находятся в диапазоне от 0 до n-1. Иногда вместо «остаток от деления на n» говорят «модуль по основанию n. В JavaScript и многих других языках программирования для вычисления модуля используют оператор %
  • Ситуация, когда разные элементы после преобразования индекса попадают в одну и ту же ячейку массива, называется коллизией. Справиться с коллизиями нетрудно. Вместо того чтобы хранить в каждой ячейке массива простое значение, мы размещаем там односвязный список. При добавлении элемента мы добавляем в список пару из года и города:
  • Для некоторых задач нужны ключи, которые очень похожи на случайные. Мы можем взять все наши числа и подвергнуть их какой-нибудь обработке — например, вычислить их сумму или произведение. Но сложение и умножение — слишком простые операции. Хороший результат в таком случае даст так называемая полиномиальная функция.
  • Хэш-функция перемешивает исходные данные так, чтобы получилось число, похожее на случайное. В Python для вычисления хешей можно использовать функцию hash(), в Java — метод hashCode(), в C# — метод GetHashCode(). В JavaScript нет готовой хеш-функции — считается, что все нужное уже есть в языке.