Логотип Хекслета

Основы алгоритмов и структур данных

Теория: Хэш

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

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

1804Вена
1614Тирана
1067Минск
752Ватикан
1872Будапешт
1237Берлин
1167Копенгаген
1191Дублин
1786Рейкьявик
856Мадрид
1323Вильнюс
963Люксембург
1275Амстердам
1200Варшава
1147Москва

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

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

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

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

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

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

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

Javascript

let capitals = []

capitals[881] = 'Вена'
capitals[1237] = 'Берлин'
capitals[1323] = 'Вильнюс'
capitals[1614] = 'Тирана'
capitals[1167] = 'Копенгаген'
capitals[963] = 'Люксембург'
capitals[1067] = 'Минск'
capitals[1191] = 'Дублин'
capitals[1275] = 'Амстердам'
capitals[752] = 'Ватикан'
capitals[1786] = 'Рейкьявик'
capitals[1200] = 'Варшава'
capitals[1872] = 'Будапешт'
capitals[856] = 'Мадрид'
capitals[1147] = 'Москва'

Python

capitals = [None for _ in range(1873)]

capitals[1804] = "Вена"
capitals[1237] = "Берлин"
capitals[1323] = "Вильнюс"
capitals[1614] = "Тирана"
capitals[1167] = "Копенгаген"
capitals[963] = "Люксембург"
capitals[1067] = "Минск"
capitals[1191] = "Дублин"
capitals[1275] = "Амстердам"
capitals[752] = "Ватикан"
capitals[1786] = "Рейкьявик"
capitals[1200] = "Варшава"
capitals[1872] = "Будапешт"
capitals[856] = "Мадрид"
capitals[1147] = "Москва"

Java

String[] capitals = new String[1873];

capitals[881] = "Вена";
capitals[1237] = "Берлин";
capitals[1323] = "Вильнюс";
capitals[1614] = "Тирана";
capitals[1167] = "Копенгаген";
capitals[963] = "Люксембург";
capitals[1067] = "Минск";
capitals[1191] = "Дублин";
capitals[1275] = "Амстердам";
capitals[752] = "Ватикан";
capitals[1786] = "Рейкьявик";
capitals[1200] = "Варшава";
capitals[1872] = "Будапешт";
capitals[856] = "Мадрид";
capitals[1147] = "Москва";

PHP

<?php

$capitals = new SplFixedArray(1873);

$capitals[881] = 'Вена';
$capitals[1237] = 'Берлин';
$capitals[1323] = 'Вильнюс';
$capitals[1614] = 'Тирана';
$capitals[1167] = 'Копенгаген';
$capitals[963] = 'Люксембург';
$capitals[1067] = 'Минск';
$capitals[1191] = 'Дублин';
$capitals[1275] = 'Амстердам';
$capitals[752] = 'Ватикан';
$capitals[1786] = 'Рейкьявик';
$capitals[1200] = 'Варшава';
$capitals[1872] = 'Будапешт';
$capitals[856] = 'Мадрид';
$capitals[1147] = 'Москва';

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

Javascript

console.log(capitals.length) // => 1873

Python

print(len(capitals))  # => 1873

Java

System.out.println(capitals.length); // => 1873

PHP

<?php

print_r(count($capitals)); // => 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:

Javascript

let capitals = []

capitals[Math.floor(881 / 20)] = 'Вена'
capitals[Math.floor(1237 / 20)] = 'Берлин'
capitals[Math.floor(1323 / 20)] = 'Вильнюс'
capitals[Math.floor(1614 / 20)] = 'Тирана'
capitals[Math.floor(1167 / 20)] = 'Копенгаген'
capitals[Math.floor(963 / 20)] = 'Люксембург'
capitals[Math.floor(1067 / 20)] = 'Минск'
capitals[Math.floor(1191 / 20)] = 'Дублин'
capitals[Math.floor(1275 / 20)] = 'Амстердам'
capitals[Math.floor(752 / 20)] = 'Ватикан'
capitals[Math.floor(1786 / 20)] = 'Рейкьявик'
capitals[Math.floor(1200 / 20)] = 'Варшава'
capitals[Math.floor(1872 / 20)] = 'Будапешт'
capitals[Math.floor(856 / 20)] = 'Мадрид'
capitals[Math.floor(1147 / 20)] = 'Москва'

Python

# В Python для целых чисел используется целочисленное деление
capitals = [None for _ in range(100)];

capitals[1804 // 20] = "Вена"
capitals[1237 // 20] = "Берлин"
capitals[1323 // 20] = "Вильнюс"
capitals[1614 // 20] = "Тирана"
capitals[1167 // 20] = "Копенгаген"
capitals[963 // 20] = "Люксембург"
capitals[1067 // 20] = "Минск"
capitals[1191 // 20] = "Дублин"
capitals[1275 // 20] = "Амстердам"
capitals[752 // 20] = "Ватикан"
capitals[1786 // 20] = "Рейкьявик"
capitals[1200 // 20] = "Варшава"
capitals[1872 // 20] = "Будапешт"
capitals[856 // 20] = "Мадрид"
capitals[1147 // 20] = "Москва"

Java

// В java для целых чисел используется целочисленное деление
String[] capitals = new String[100];

capitals[881 / 20] = "Вена";
capitals[1237 / 20] = "Берлин";
capitals[1323 / 20] = "Вильнюс";
capitals[1614 / 20] = "Тирана";
capitals[1167 / 20] = "Копенгаген";
capitals[963 / 20] = "Люксембург";
capitals[1067 / 20] = "Минск";
capitals[1191 / 20] = "Дублин";
capitals[1275 / 20] = "Амстердам";
capitals[752 / 20] = "Ватикан";
capitals[1786 / 20] = "Рейкьявик";
capitals[1200 / 20] = "Варшава";
capitals[1872 / 20] = "Будапешт";
capitals[856 / 20] = "Мадрид";
capitals[1147 / 20] = "Москва";

PHP

<?php

$capitals = new SplFixedArray(100);

$capitals[round(881 / 20)] = 'Вена';
$capitals[round(1237 / 20)] = 'Берлин';
$capitals[round(1323 / 20)] = 'Вильнюс';
$capitals[round(1614 / 20)] = 'Тирана';
$capitals[round(1167 / 20)] = 'Копенгаген';
$capitals[round(963 / 20)] = 'Люксембург';
$capitals[round(1067 / 20)] = 'Минск';
$capitals[round(1191 / 20)] = 'Дублин';
$capitals[round(1275 / 20)] = 'Амстердам';
$capitals[round(752 / 20)] = 'Ватикан';
$capitals[round(1786 / 20)] = 'Рейкьявик';
$capitals[round(1200 / 20)] = 'Варшава';
$capitals[round(1872 / 20)] = 'Будапешт';
$capitals[round(856 / 20)] = 'Мадрид';
$capitals[round(1147 / 20)] = 'Москва';

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

Javascript

const getCity = year => capitals[Math.floor(year / 20)]

let city = getCity(1191) // Дублин

Python

def get_city(year):
    return capitals[year // 20]

city = get_city(1191)  # Дублин

Java

class App {
    public static String getCity(String[] capitals, int year) {
        return capitals[year / 20];
    }
}

PHP

<?php

function getCity($year, $capitals)
{
    return $capitals[round($year / 20)];
}

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

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

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

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

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

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

Javascript

let capitals = new Array(100)

Python

capitals = [None for _ in range(100)]

Java

String[] capitals = new String[100];

PHP

<?php

$capitals = array_fill(0, 100, null);

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

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

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

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

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

Javascript

console.log(1999 % 20) // => 19

Python

print(1999 % 20)  # => 19

Java

System.out.println(1999 % 20); // => 19

PHP

<?php

print_r(1999 % 20); // => 19

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

Javascript

let capitals = new Array(100)

capitals[881 % 100] = 'Вена'
capitals[1237 % 100] = 'Берлин'
capitals[1323 % 100] = 'Вильнюс'
capitals[1614 % 100] = 'Тирана'
capitals[1167 % 100] = 'Копенгаген'
capitals[963 % 100] = 'Люксембург'
capitals[1067 % 100] = 'Минск'
capitals[1191 % 100] = 'Дублин'
capitals[1275 % 100] = 'Амстердам'
capitals[752 % 100] = 'Ватикан'
capitals[1786 % 100] = 'Рейкьявик'
capitals[1200 % 100] = 'Варшава'
capitals[1872 % 100] = 'Будапешт'
capitals[856 % 100] = 'Мадрид'
capitals[1147 % 100] = 'Москва'

const getCity = year => capitals[year % 100]

let city = getCity(1167) // Копенгаген

Python

capitals = [None for _ in range(100)]

capitals[1804 % 100] = 'Вена'
capitals[1237 % 100] = 'Берлин'
capitals[1323 % 100] = 'Вильнюс'
capitals[1614 % 100] = 'Тирана'
capitals[1167 % 100] = 'Копенгаген'
capitals[963 % 100] = 'Люксембург'
capitals[1067 % 100] = 'Минск'
capitals[1191 % 100] = 'Дублин'
capitals[1275 % 100] = 'Амстердам'
capitals[752 % 100] = 'Ватикан'
capitals[1786 % 100] = 'Рейкьявик'
capitals[1200 % 100] = 'Варшава'
capitals[1872 % 100] = 'Будапешт'
capitals[856 % 100] = 'Мадрид'
capitals[1147 % 100] = 'Москва'

def get_city(year):
    return capitals[year % 100]

city = get_city(1167)  # Копенгаген

Java

String[] capitals = new String[100];

capitals[881 % 100] = "Вена";
capitals[1237 % 100] = "Берлин";
capitals[1323 % 100] = "Вильнюс";
capitals[1614 % 100] = "Тирана";
capitals[1167 % 100] = "Копенгаген";
capitals[963 % 100] = "Люксембург";
capitals[1067 % 100] = "Минск";
capitals[1191 % 100] = "Дублин";
capitals[1275 % 100] = "Амстердам";
capitals[752 % 100] = "Ватикан";
capitals[1786 % 100] = "Рейкьявик";
capitals[1200 % 100] = "Варшава";
capitals[1872 % 100] = "Будапешт";
capitals[856 % 100] = "Мадрид";
capitals[1147 % 100] = "Москва";

class App {
    public static String getCity(String[] capitals, int year) {
        return capitals[year % 100];
    }
}

PHP

<?php

$capitals = array_fill(0, 100, null);

$capitals[881 % 100] = 'Вена';
$capitals[1237 % 100] = 'Берлин';
$capitals[1323 % 100] = 'Вильнюс';
$capitals[1614 % 100] = 'Тирана';
$capitals[1167 % 100] = 'Копенгаген';
$capitals[963 % 100] = 'Люксембург';
$capitals[1067 % 100] = 'Минск';
$capitals[1191 % 100] = 'Дублин';
$capitals[1275 % 100] = 'Амстердам';
$capitals[752 % 100] = 'Ватикан';
$capitals[1786 % 100] = 'Рейкьявик';
$capitals[1200 % 100] = 'Варшава';
$capitals[1872 % 100] = 'Будапешт';
$capitals[856 % 100] = 'Мадрид';
$capitals[1147 % 100] = 'Москва';

const getCity = (year) => $capitals[year % 100];

function getCity($capitals, $year)
{
    return $capitals[$year % 100];
}

$city = getCity(1167); // 'Копенгаген'

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

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

Javascript

console.log(getCity(1167)) // => Минск

Python

print(get_city(1167))  # => Минск

Java

System.out.println(App.getCity(1167)); // => Минск

PHP

<?php

print_r(getCity(1167)); // => Минск

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

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

Коллизии

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

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

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

Javascript

import LinkedList from './LinkedList.js'

let capitals = new Array(100)

const setCapital = (year, city) => {
  let index = year % capitals.length
  if (typeof (capitals[index]) === 'undefined') {
    capitals[index] = new LinkedList()
  }

  capitals[index].add({ key: year, value: city })
}

Python

from LinkedList import LinkedList

capitals = [None for _ in range(100)]

def set_capital(year, city):
    index = year % len(capitals)

    if capitals[index] is None:
        capitals[index] = LinkedList()

    capitals[index].add({'key': year, 'value': city})

Java

class App {
    private LinkedList[] capitals = new LinkedList[100];

    public void setCapital(int year, String city) {
        var index = year % capitals.length;
        if (capitals[index] == null) {
            capitals[index] = new LinkedList<Object[]>();
        }

        capitals[index].add(new Object[] {year, city});
    }
}

PHP

<?php

use LinkedList;

$capitals = array_fill(0, 100, null);

function setCapital($year, $city, &$capitals)
{
    $index = $year % count(capitals);
    if (!isset($capitals[$index])) {
        $capitals[$index] = new LinkedList();
    }

    $capitals[$index]->add(['key' => $year, 'value' => $city]);
}

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

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

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

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

Javascript

const getCapital = (year) => {
  let index = year % capitals.length
  if (typeof (capitals[index]) === 'undefined') {
    return undefined
  }

  for (let pair of capitals[index]) {
    if (pair.key === year) {
      return pair.value
    }
  }

  return undefined
}

Python

def get_capital(year):
    index = year % len(capitals)

    if capitals[index] is None:
        return None

    for pair in capitals[index]:
        if pair['key'] == year:
            return pair['value']

    return None

Java

lass App {
    private LinkedList[] capitals = new LinkedList[100];

    public void setCapital(int year, String city) {
        // ...
    }

    public String getCapital(int year) {
        var index = year % capitals.length;

        if (capitals[index] == null) {
            return null;
        }

        for (var pair : capitals[index]) {
            var casted = (Object[]) pair;
            if ((int) casted[0] == year) {
                return (String) casted[1];
            }
        }

        return null;
    }
}

PHP

<?php

function getCapital($capitals, $year)
{
  $index = $year % count($capitals);
  if (!isset($capitals[$year])) {
      return null;
  }

  foreach($capitals[$index] as $pair) {
      if ($pair['key'] === $year) {
          return $pair['value'];
      }
  }

  return null;
}

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

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

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

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

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

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

Хэш-функция

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

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

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

Javascript

const capital = 'Мадрид'
for (let i = 0; i < capital.length; i++) {
  console.log(capital.charCodeAt(i))
}
// => 1052
// => 1072
// => 1076
// => 1088
// => 1080
// => 1076

Python

capital = 'Мадрид'

for i in range(len(capital)):
    print(ord(capital[i]))
# => 1052
# => 1072
# => 1076
# => 1088
# => 1080
# => 1076

Java

var capital = "Мадрид";
for (var i = 0; i < capital.length; i++) {
    System.out.println((int) capital.charAt(i));
}
// => 1052
// => 1072
// => 1076
// => 1088
// => 1080
// => 1076

PHP

<?php

$capital = 'Мадрид';
for ($i = 0; $i < count($capital); i += 1) {
  print_r(mb_ord($capital[$i]));
}
// => 1052
// => 1072
// => 1076
// => 1088
// => 1080
// => 1076

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

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

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

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

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

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

c0 + c1 * k + c2 * k^2 + c3 * k^3 + ... + cn-1 * k^(n-1)

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

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

(c0 + c1 * k + c2 * k^2 + c3 * k^3 + ... + cn-1 * k^(n-1)) mod m

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

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

Javascript

const hash = (s) => {
  const k = 65537
  const m = 2 ** 20

  let result = 0
  let k_i = 1
  for (let i = 0; i < s.length; i++) {
    result = (result + k_i * s.charCodeAt(i)) % m
    k_i = (k_i * k) % m
  }

  return result
}

Python

def hash(s):
    k = 65537
    m = 2**20

    result = 0
    k_i = 1

    for i in range(len(s)):
        result = (result + k_i * ord(s[i])) % m
        k_i = (k_i * k) % m

    return result

Java

class App {
    private int hash(String s) {
        var k = 65537;
        var m = (int) Math.pow(2, 20);

        var result = 0;
        var k_i = 1;

        for (var i = 0; i < s.length(); i++) {
            result = (result + k_i * s.charAt(i)) % m;
            k_i = (k_i * k) % m;
        }

        return result;
    }
}

PHP

<?php

function hash($s)
{
    $k = 65537;
    $m = 2 ** 20;

    $result = 0;
    $k_i = 1;
    for ($i = 0; $i < mb_strlen($s); $i += 1) {
        $result = ($result + $k_i * mb_ord($s[$i])) % $m;
        $k_i = ($k_i * $k) % $m;
    }

    return $result;
}

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

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

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

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

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

Javascript

hash('Мадрид') // 792876
hash('Москва') // 399671
hash('Минск') // 857356

Python

hash('Мадрид') # 792876
hash('Москва') # 399671
hash('Минск')  # 857356

Java

App.hash("Мадрид") // 792876
App.hash("Москва") // 399671
App.hash("Минск")  // 857356

PHP

<?php

hash('Мадрид') // 792876
hash('Москва') // 399671
hash('Минск')  // 857356

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

В 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 элементов, чтобы не перестраивать его слишком часто, пока он маленький.

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

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

Javascript

import LinkedList from './LinkedList.js'

class Hash {
  table = []
  count = 0

  hash(s) {
    const k = 65537
    const m = 2 ** 20

    let result = 0, power = 1
    for (let i = 0; i < s.length; i++) {
      result = (result + power * s.charCodeAt(i)) % m
      power = (power * k) % m
    }

    return result
  }

  calculateIndex(table, key) {
    return this.hash(String(key)) % table.length
  }

  rebuildTableIfNeed() {
    if (this.table.length == 0) {
      this.table.length = 128
    }
    else {
      const loadFactor = this.count / this.table.length
      if (loadFactor >= 0.8) {
        let newTable = new Array(this.table.length * 2)
        for (let list in this.table) {
          for (let pair of list) {
            const newIndex = this.calculateIndex(newTable, pair.key)
            if (typeof (newTable[newIndex]) === 'undefined') {
              newTable[newIndex] = new LinkedList()
            }

            newTable[newIndex].add(pair)
          }
        }

        this.table = newTable
      }
    }
  }

  set(key, value) {
    this.rebuildTableIfNeed()

    const index = this.calculateIndex(this.table, key)
    if (typeof (this.table[index]) === 'undefined') {
      this.table[index] = new LinkedList()
    }

    this.table[index].add({ key: key, value: value })
    this.count += 1
  }

  get(key) {
    const index = this.calculateIndex(this.table, key)
    if (typeof (this.table[index].fore()) === 'undefined') {
      return undefined
    }

    for (let pair of this.table[index]) {
      if (pair.key === key) {
        return pair.value
      }
    }

    return undefined
  }
}

Python

class Hash:
    table = []
    count = 0

    def hash(self, s):
        k = 65537
        m = 2**20

        result = 0
        power = 1

        for i in range(len(s)):
            result = (result + power * ord(s[i])) % m
            power = (power * k) % m

        return result

    def calculate_index(self, table, key):
        try:
            return self.hash(str(key)) % len(table)
        except ZeroDivisionError:
            return self.hash(str(key))

    def rebuild_table_if_need(self):
        if len(self.table) == 0:
            table = [None for _ in range(128)]
        else:
            load_factor = self.count / len(self.table)

            if load_factor >= 0.8:
                new_table = [None for _ in range(len(self.table) * 2)]

                for list_ in self.table:
                    for pair in list_:
                        new_index = self.calculate_index(new_table, pair['key'])
                        if new_table[new_index] is None:
                            new_table[new_index] = LinkedList()

                        new_table[new_index].add(pair)

                self.table = new_table

    def set(self, key, value):
        self.rebuild_table_if_need()
        index = self.calculate_index(self.table, key)

        if self.table[index] is None:
            self.table[index] = LinkedList()

        self.table[index].add(
            {'key': key, 'value': value}
        )
        self.count += 1

    def get(self, key):
        index = self.calculate_index(self.table, key)

        if self.table[index] is None:
            return None

        for pair in self.table[index]:
            if pair['key'] == key:
                return pair['value']

        return None

Java

public class Hash {

    public LinkedList[] table = new LinkedList[128];
    public int count = 0;

    private int hash(String s) {
        var k = 65537;
        var m = (int) Math.pow(2, 20);

        var result = 0;
        var k_i = 1;

        for (var i = 0; i < s.length(); i++) {
            result = (result + k_i * s.charAt(i)) % m;
            k_i = (k_i * k) % m;
        }

        return result;
    }

    public int calculateIndex(LinkedList[] table, String key) {
        return hash(key) % table.length;
    }

    private void rubuildTableIfNeed() {
        var loadFactor = (double) count / table.length;
        if (loadFactor >= 0.8) {
            LinkedList[] newTable = new LinkedList[table.length * 2];
            for (LinkedList list : table) {
                for (var pair : list) {
                    Object[] casted = (Object[]) pair;
                    var newIndex = calculateIndex(newTable, (String) casted[0]);
                    if (newTable[newIndex] == null) {
                        newTable[newIndex] = new LinkedList();
                    }

                    newTable[newIndex].append(pair);
                }
            }

            table = newTable;
        }
    }

    public void set(String key, Object value) {
        this.rubuildTableIfNeed();
        var index = calculateIndex(table, key);

        if (table[index] == null) {
            table[index] = new LinkedList();
        }

        table[index].append(new Object[] {key, value});
        count++;
    }

    public Object get(String key) {
        var index = calculateIndex(table, key);
        if (table[index] == null) {
            return null;
        }

        for (var current : table[index]) {
            LinkedListNode node = (LinkedListNode) current;
            var pair = node.value;
            var casted = (Object[]) pair;
            if (casted[0].equals(key)) {
                return casted[1];
            }
        }

        return null;
    }
}

PHP

<?php

class Hash
{
    public function __construct()
    {
        $this->table = [];
        $this->count = 0;
    }

    public function hash($s)
    {
        $k = 65537;
        $m = 2 ** 20;

        $result = 0;
        $power = 1;
        for ($i = 0; $i < strlen($s); $i += 1) {
            $result = ($result + $power * ord($s[$i])) % $m;
            $power = ($power * $k) % $m;
        }

        return $result;
    }

    public function calculateIndex($table, $key)
    {
        return $this->hash((string) $key) % count($table);
    }

    public function rebuildTableIfNeed()
    {
        if (count($this->table) === 0) {
            $this->table = array_fill(0, 128, null);
        } else {
            $loadFactor = $this->count / count($this->table);
            if ($loadFactor >= 0.8) {
                $newTable = array_fill(0, count($this->table) * 2, null);
                foreach ($this->table as $list) {
                    foreach ($list as $pair) {
                        $newIndex = $this->calculateIndex($newTable, $pair['key']);
                        if (!isset($newTable[$newIndex])) {
                            $newTable[$newIndex] = new LinkedList();
                        }

                        $newTable[$newIndex]->append($pair);
                    }
                }

                $this->table = $newTable;
            }
        }
    }

    public function set($key, $value)
    {
        $this->rebuildTableIfNeed();

        $index = $this->calculateIndex($this->table, $key);
        if (!isset($this->table[$index])) {
            $this->table[$index] = new LinkedList();
        }

        $this->table[$index]->append(['key' => $key, 'value' => $value ]);
        $this->count += 1;
    }

    public function get($key)
    {
        $index = $this->calculateIndex($this->table, $key);
        if (!isset($this->table[$index])) {
            return null;
        }

        foreach ($this->table[$index] as $pair1) {
            $pair = (array) $pair1;
            if ($pair['value']['key'] === $key) {
                return $pair['value']['value'];
            }
        }

        return null;
    }
}

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

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

Javascript

let newTable = new Array(this.table.length * 2)
for (let list in this.table) {
  for (let pair of list) {
    const newIndex = this.calculateIndex(newTable, pair.key)
    if (typeof (newTable[newIndex]) === 'undefined') {
      newTable[newIndex] = new LinkedList()
    }

    newTable[newIndex].add(pair)
  }
}

Python

new_table = [None for _ in range(len(self.table) * 2)]

for list_ in self.table:
    for pair in list_:
        new_index = self.calculate_index(new_table, pair['key'])
        if new_table[new_index] is None:
            new_table[new_index] = LinkedList()

        new_table[new_index].add(pair)

Java

LinkedList[] newTable = new LinkedList[table.length * 2];

for (LinkedList list : table) {
    for (var pair : list) {
        Object[] casted = (Object[]) pair;
        var newIndex = calculateIndex(newTable, (String) casted[0]);
        if (newTable[newIndex] == null) {
            newTable[newIndex] = new LinkedList();
        }

        newTable[newIndex].add(pair);
    }
}

PHP

<?php

$newTable = array_fill(0, count($this->table) * 2, null);
foreach ($this->table as $list) {
    foreach ($list as $pair) {
        $newIndex = $this->calculateIndex($newTable, $pair['key'])
        if (!isset($newTable[$newIndex])) {
            $newTable[$newIndex] = new LinkedList();
        }

      $newTable[$newIndex]->add($pair);
    }
}

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

Выводы

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

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

Рекомендуемые программы

Навигация
Теория
Тесты
Упражнение