Другие части: массивы, итераторы, множества, ассоциативные массивы, деревья, списки и связные списки
Хеш-таблицы могут использоваться как самостоятельные коллекции для хранения данных, но в основном они используются как вспомогательные инструменты для быстрого поиска данных в других коллекциях.
Давайте рассмотрим следующую проблему. В массиве хранится набор разных строк:
var a = ['apple', 'banana', 'kiwi', 'pear', 'mango'];
Если мы хотим узнать, что находится в массиве по смещению 2, то сделать это очень просто, обратившись к массиву и указав это смещение: a[2], и это даст результат 'kiwi'.
Но если нужно узнать, есть ли строка 'kiwi' в массиве, то обратная операция невозможна. Придётся перебрать каждый элемент массива и сравнить его с 'kiwi':
И мы получим результат 2. Нужно отметить, что в данном случае мы перебрали не весь массив, а только три элемента, но это лишь потому, что строка 'kiwi' попалась на третьем месте. Она могла бы стоять и на первом месте, тогда мы нашли бы её за одну операцию. Но могла бы стоять и в самом конце массива длиной в миллион элементов, и тогда пришлось бы сделать миллион операций.
То есть в среднем такие операции поиска весьма медленны.
Здесь и приходят на помощь хеш-таблицы.
Хеш-таблицу можно представить как обычный массив, в котором хранятся значения. Но хеш-таблица "волшебным" образом знает, по какому смещению хранится 'kiwi' или любой другой элемент. То есть уже не нужно перебирать все элементы массива.
Как это получается?
Массиву без разницы, какие конкретно элементы записаны в каких конкретно смещениях.
В хеш-таблице дела обстоят не так. Для каждого элемента там вычисляется своё уникальное смещение, которое нельзя выбрать произвольно. Если мы добавим в хеш-таблицу несколько элементов подряд, то их смещения могут получиться не 0, 1, 2, 3... а, например, 0, 54, 16, 11, 2... и никак иначе.
Занимается вычислениям смещений специальная хеш-функция. Она берёт значение элемента и делает из него хеш (hash). Это переводится как "крошить", "рубить", "путать". В общем, я бы назвал это окрошкой.
Как именно функция получает хеш, мы рассмотрим позже. Пока можно считать её "чёрным ящиком", который для каждого уникального значения (числа, строки, объекта) выдаёт другое уникальное значение в виде целого числа. Это целое число и будет смещением в массиве.
- Допустим, мы хотим сохранить строку 'kiwi' в хеш-таблицу. С помощью хеш-функции таблица получает из строки 'kiwi' смещение: допустим, 5. Строка 'kiwi' записывается в массив по смещению 5.
- Теперь нам нужно найти 'kiwi' в хеш-таблице. Таблица снова применяет хеш-функцию к строке 'kiwi' и получает смещение 5. Посмотрим в массив, что там лежит по смещению 5? Если строка 'kiwi', значит мы её нашли. Если там пусто, значит нет такой строки нигде в массиве.
Таким образом, поиск в массиве элемента по его значению теперь занимает всего одну итерацию:
Получить из значения хеш → взять элемент со смещением, равным хешу
Теперь рассмотрим, как устроена
Хеш-функция
Если нам дано дано N разных значений, то нужно получить из них N разных хешей. Для этого желательно использовать какую-то информацию о самих значениях.
Вот самый примитивный пример:
Допустим, у нас есть 10 строк разной длины (от 1 символа до 10). Тогда в качестве хеша можно взять длину строки. Строка с длиной 1 даст хеш 1, строка с длиной 2 даст хеш 2, и т.д.
Другой вариант: каждая строка начинается с разной буквы. Тогда строка, которая начинается с "A", даст хеш 0, строка, которая начинается с "B", даст хеш 1, и т.д.
Но в реальности такая информация вряд ли пригодится – разные строки могут быть одной длины, или начинаться на одну и ту же букву, вследствие чего у них получится один и тот же хеш.
Поэтому более-менее универсальные хеш-функции реализуются следующим образом:
Строка и есть хеш самой себя. Ведь строка состоит из байтов, а любую последовательность байтов можно представить как N-битное целое число. Очевидно, это число будет уникальным для каждой уникальной строки, потому что оно и есть строка.
Значит, если просто взять строку и представить её как целое число, то это число и будет смещением, куда нужно записать строку.
Но возникает проблема
Строка длиной 8 символов – это 64-битное число. Массив для хранения смещений таких строк должен состоять из 2^64 элементов, что просто невозможно. И ведь это всего 8 символов, а строки имеют неограниченную длину.
Поэтому поступают следующим образом:
Для массива хеш-таблицы выбирается какая-то длина. Можно выделить 10 элементов, или 1000, или миллион, это неважно. Сколько есть – столько и есть.
Вычислив хеш строки (N-битное число), мы берём остаток от деления этого числа на длину нашего массива. Что это дает: какое бы ни было число N, остаток от деления на M всегда находится в пределах от 0 до M-1, то есть всегда помещается в диапазон возможных смещений в нашем массиве.
Но возникает другая проблема
Очевидно, что если взять, например, 100 чисел и вычислить от каждого остаток от деления на 10, то мы получим совпадающие остатки. Например, у чисел 0..9 остаток от деления на 10 равен 0..9. У чисел 10..19 остаток от деления на 10 также равен 0..9, и т.д.
То есть, для 100 уникальных чисел 0..99 мы получили только 10 уникальных хешей 0..9. Это значит, что возникла
Коллизия хешей
Коллизия – это столкновение. Она возникает, когда у двух разных чисел вычисляется один и тот же хеш.
Мы должны записать в массив значение с соответствующим ему смещением, но там уже записано какое-то другое значение с таким же смещением.
Что делать?
В каждой позиции массива хранить не один элемент, а список элементов. Если появляется элемент, хеш которого совпадает с уже имеющимся элементом, то он просто добавляется в соответствующий список.
Поиск происходит аналогично: сначала мы по хешу элемента находим его позицию в массиве, а затем проверям список, который там хранится. Если в списке несколько элементов, то мы перебираем весь список, пока не найдём искомый элемент.
Что-то напоминает, да? Ведь мы с этого и начали. Была проблема перебора элементов в массиве, и мы хотели уйти от неё с помощью хеш-таблицы, но снова вернулись к перебору.
Да, это так. Но теперь мы перебираем не весь массив значений, а только лишь отдельный список для конкретного хеша.
Хеш-функции это отдельная наука. Здесь я обрисовал только общую картину. Её должно быть достаточно, если вы захотите углубиться в эту тему и почитать что-то более продвинутое.