Как работает хэширование

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

Хэш-функции фундаментальны и используются повсюду.

Но что же такое хэш-функции и как они работают?

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

В оригинале статьи многие иллюстрации интерактивны

Что такое хэш-функция?

Хэш-функции — это функции, получающие на входе данные, обычно строку, и возвращающие число. При многократном вызове хэш-функции с одинаковыми входными данными она всегда будет возвращать одно и то же число, и возвращаемое число всегда будет находиться в гарантированном интервале. Этот интервал зависит от хэш-функции: в некоторых используются 32-битные целочисленные значения (то есть от 0 до 4 миллиардов), в других интервалы гораздо больше.

Если бы мы захотели написать на JavaScript имитацию хэш-функции, то она могла бы выглядеть так:

function hash(input) {
  return 0;
}

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

Какая хэш-функция может считаться хорошей?

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

Однако полностью избавиться от коллизий невозможно. Если бы мы написали хэш-функцию, возвращающую число в интервале от 0 до 7, и передали бы ей 9 уникальных входных значений, то гарантированно получили бы как минимум 1 коллизию.

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

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

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

Вы сказали, что когда хэш-функция возвращает одинаковое значение для двух входных данных, это называется коллизией. Но если у нас будет хэш-функция, которая возвращает значения в большом интервале, а мы накладываем их на маленькую сетку, то не создадим ли мы множество коллизий, которые на самом деле не будут коллизиями? В нашей сетке 8x2 и 1, и 17 соответствуют второму квадрату.

Отличное замечание. Ты совершенно права, в нашей сетке будут возникать «псевдоколлизии». Но это приемлемо, потому что если хэш-функция хороша, то мы всё равно увидим равномерное распределение. Инкремент каждого квадрата на 100 — это столь же хорошее распределение, как и инкремент каждого квадрата на 1. Если мы получим хэш-функцию с большой степенью коллизий, то это всё равно будет бросаться в глаза. Вскоре мы сами в этом убедимся.

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

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

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

function hash(input) {
  let hash = 0;
  for (let c of input) {
    hash += c.charCodeAt(0);
  }
  return hash % 1000000;
}

Эта хэш-функция циклически обходит всю переданную ей строку и суммирует числовые значения каждого символа. Затем она делает так, чтобы значение находилось в интервале от 0 до 1000000 при помощи оператора деления с остатком (%). Назовём эту хэш-функцию stringSum.

Вот как она выглядит в сетке. Напомню, что это 1000 случайно сгенерированных строк, которые мы хэшируем.

Не сильно отличается от murmur3. В чём же дело?

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

Теперь проблема стала очевиднее. Когда входные данные не случайны, выходные данные stringSum образуют паттерн. А сетка murmur3 выглядит так же, как и при случайных значениях.

А вот что получится, если мы хэшируем 1000 самых распространённых слов на английском:

Разница менее заметна, но мы всё равно видим паттерн в сетке stringSum. Функция murmur3 снова выглядит, как обычно.

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

▍ Лавинный эффект

Ещё один способ проверки хэш-функций — это так называемый «лавинный эффект». Это показатель того, какое количество битов меняется в выходном значении при изменении всего одного бита во входном значении. Чтобы можно было сказать, что хэш-функция имеет хороший лавинный эффект, смена одного бита во входном значении должна приводить в среднем к смене 50% битов в выходном значении.

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

Ниже мы показали лавинный эффект на примере двух 8-битных двоичных чисел. Верхнее число — это входное значение, а нижнее — выходное значение murmur3. Каждый раз во входном значении меняется один бит. Изменившиеся в выходном значении биты будут выделены зелёным, а неизменившиеся биты — оранжевым.

murmur3 проявляет себя хорошо, несмотря на то, что иногда меняется меньше 50% битов, а иногда больше. И это нормально, если в среднем получается 50%.

Давайте посмотрим, как ведёт себя stringSum.

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

Почему всё это важно

Мы поговорили о нескольких способах определения качественности хэш-функций, но не обсудили, почему это важно. Давайте исправим это, рассмотрев хэш-таблицы (hash map).

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

let map = new Map();
map.set("hello", "world");
console.log(map.get("hello"));

Здесь мы берём пару «ключ-значение» ("hello" → "world") и сохраняем её в map. Затем мы выводим значение, связанное с ключом "hello", то есть "world".

Более интересным примером реального использования стал бы поиск анаграмм. Анаграмма — это когда два разных слова состоят из одинаковых букв, например, «апельсин» и «спаниель» или «кабан» и «банка». Если у вас есть список слов, и вы хотите найти все анаграммы, то можно отсортировать буквы в каждом слове по алфавиту и использовать эту строку как ключ структуры map.

let words = [
  "antlers",
  "rentals",
  "sternal",
  "article",
  "recital",
  "flamboyant",
]

let map = new Map();

for (let word of words) {
  let key = word
    .split('')
    .sort()
    .join('');

  if (!map.has(key)) {
    map.set(key, []);
  }
  map.get(key).push(word);
}

В результате выполнения этого кода мы получаем map со следующей структурой:

{
  "aelnrst": [
    "antlers",
    "rentals",
    "sternal"
  ],
  "aceilrt": [
    "article",
    "recital"
  ],
  "aabflmnoty": [
    "flamboyant"
  ]
}

▍ Реализация собственной простой хэш-таблицы

Хэш-таблицы — одна из множества реализаций map; также существует множество способов реализации хэш-таблиц. Простейший способ, который мы и покажем — это список списков. Внутренние списки в реальном мире часто называют «bucket», поэтому так мы их и будем называть. Хэш-функция применяется к ключу для определения того, в каком bucket должна храниться пара «ключ-значение», после чего эта пара «ключ-значение» добавляется в bucket.

Давайте рассмотрим простую реализацию хэш-таблицы на JavaScript. Мы изучим её снизу вверх, то есть сначала рассмотрим вспомогательные методы, а затем перейдём к реализациям set и get.

class HashMap {
  constructor() {
    this.bs = [[], [], []];
  }
}

Мы начнём с создания класса HashMap с конструктором, настраивающим три bucket. Мы используем три bucket и короткое имя переменной bs, чтобы этот код удобно было просматривать на устройствах с маленькими экранами. В реальном коде можно создавать любое количество bucket (и придумать более осмысленные имена переменных).

class HashMap {
  // ...
  bucket(key) {
    let h = murmur3(key);
    return this.bs[
      h % this.bs.length
    ];
  }
}

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

class HashMap {
  // ...
  entry(bucket, key) {
    for (let e of bucket) {
      if (e.key === key) {
        return e;
      }
    }
    return null;
  }
}

Метод entry получает bucket и key и сканирует bucket, пока не найдёт элемент с указанным ключом. Если элемент не найден, возвращается null.

class HashMap {
  // ...
  set(key, value) {
    let b = this.bucket(key);
    let e = this.entry(b, key);
    if (e) {
      e.value = value;
      return;
    }
    b.push({ key, value });
  }
}

Метод set мы первым узнаём из предыдущих примеров Map на JavaScript. Он получает пару «ключ-значение» и сохраняет её в хэш-таблицу. Он делает это при помощи созданных ранее методов bucket и entry. Если элемент найден, то значение перезаписывается. Если элемент не найден, то пара «ключ-значение» добавляется в map. В JavaScript { key, value } — это более компактная запись { key: key, value: value }.

class HashMap {
  // ...
  get(key) {
    let b = this.bucket(key);
    let e = this.entry(b, key);
    if (e) {
      return e.value;
    }
    return null;
  }
}

Метод get очень похож на set. Он использует bucket и entry для поиска элемента, связанного с переданным key, точно так же, как это делает set. Если элемент найден, возвращается его value. Если он не найден, то возвращается null.

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

Вот визуальное представление этой хэш-таблицы. При помощи set добавляется новая пара «ключ-значение». Чтобы не усложнять визуализацию, если bucket должен «переполниться», то все bucket очищаются.

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

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

Именно этот этап поиска мы минимизируем при помощи хэширования, и именно благодаря ему murmur3 оптимизирована по скорости. Чем быстрее хэш-функция, тем быстрее мы отыскиваем нужный bucket для поиска, и тем быстрее наша хэш-таблица в целом.

Кроме того, из-за этого так важно снижение количества коллизий. Если бы мы решили использовать имитацию хэш-функции из начала статьи, постоянно возвращающую 0, то поместили бы все пары «ключ-значение» в первый bucket. Для поиска любого элемента нам пришлось бы проверить все значения в хэш-таблице. При хорошей хэш-функции с хорошим распределением мы снижаем количество необходимых операций поиска до 1/N, где N — это количество bucket.

Давайте посмотрим, как проявляет себя здесь stringSum.

Любопытно: кажется, stringSum распределяет достаточно неплохо. Мы замечаем паттерн, но в целом распределение выглядит хорошим.

Наконец-то! Победа stringSum! Я знала, что она когда-нибудь пригодится.

Не торопись, Хаски. Нам нужно обсудить серьёзную проблему. Распределение выглядит приемлемым при этих последовательных числах, однако мы видели, что у stringSum плохой лавинный эффект. Всё это не кончится ничем хорошим.

Коллизии в реальном мире

Давайте рассмотрим два массива данных из реального мира: IP-адреса и английские слова. Я возьму 100 000 000 случайных IP-адресов и 466 550 английских слов, хэширую их murmur3 и stringSum, а потом посмотрю, сколько коллизий мы получим.

IP-адреса

Английские слова

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

Синтетические коллизии

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

Что здесь происходит? Почему все эти бессмысленные строки хэшируются в одинаковое число?

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

Простите, 141 триллион? Это… 141 и 12 нулей?

Да, и это заняло у меня всего 25 минут. Компьютеры очень быстры.

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

GET / HTTP/1.1
Accept: */*
Accept-Encoding: gzip, deflate
Connection: keep-alive
Host: google.com

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

И это не теоретические рассуждения. Если вы поищите «HashDoS», то сможете найти ещё множество примеров этого. В середине 2000-х это была очень серьёзная проблема.

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

Выше в этом посте мы показали несколько примеров реализаций хэш-функций. Эти реализации получают единственный аргумент: input. Многие из современных хэш-функций получают второй параметр: порождающее значение (seed) (иногда называемое «солью» (salt)). В случае murmur3 этим seed является число.

Пока мы использовали в качестве seed значение 0. Давайте посмотрим, что произойдёт с собранными мной коллизиями при использовании seed, равного 1.

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

Хэш-функция по-прежнему возвращает одинаковые выходные данные для одинаковых входных данных, только теперь входные данные — это сочетание input и seed. Те значения, у которых возникают коллизии при одном seed, не приводят к коллизиям при использовании другого. Языки программирования в начале процесса часто генерируют случайное число для использования в качестве seed, чтобы каждый раз при запуске программы seed различался. Если я злоумышленник, не знающий seed, то больше не могу стабильно наносить ущерб.

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

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

Песочница

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

Заключение

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

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

Если вам интересна эта тема, то рекомендую изучить следующие материалы:

• https://github.com/rurban/smhasher: этот репозиторий — золотой стандарт тестирования качества хэш-функций. Он проводит кучу тестов, выполняя сравнение с большим количеством хэш-функций, и представляет результаты в виде большой таблицы. Может быть сложно понять, для чего нужны все эти тесты, но это самая современная система для тестирования хэш-функций.
• https://djhworld.github.io/hyperloglog/ — это интерактивная статья о структуре данных под названием HyperLogLog. Она используется для эффективного подсчёта уникальных элементов в огромных массивах данных. Для этого она очень хитро применяет хэширование.
• https://www.gnu.org/software/gperf/ — это ПО, которому можно передать ожидаемое множество элементов, которые нужно хэшировать, и оно автоматически сгенерирует «идеальную» хэш-функцию.

Благодарности

Благодарю всех, кто читал ранние черновики статьи и давал бесценные отзывы.

• delroth, Манон, Аарон, Чарли

И всех, кто помог мне найти хэш-коллизии murmur3:

• Инди, Аарон, Макс