Автор оригинала: Andrew Shcherbakov.
1. введение
В этом уроке мы рассмотрим методы хеширования, используемые в различных структурах данных, которые обеспечивают постоянный доступ к их элементам.
Мы более подробно обсудим так называемую технику складывания и дадим краткое введение в технику среднего квадрата и биннинга.
2. Обзор
Когда мы выбираем структуры данных для хранения объектов, одним из соображений является необходимость быстрого доступа к ним.
Пакет утилит Java предлагает нам довольно много структур данных для хранения наших объектов. Для получения дополнительной информации о структурах данных обратитесь к нашей странице компиляции коллекций Java, которая содержит руководства по некоторым из них.
Как мы знаем, некоторые из этих структур данных позволяют нам извлекать их элементы в постоянное время, независимо от количества элементов, которые они содержат.
Вероятно, самый простой из них-это массив. Фактически, мы получаем доступ к элементам массива по их индексу. Время доступа, естественно, не зависит от размера массива. На самом деле, за кулисами многие структуры данных в значительной степени используют массивы.
Проблема в том, что индексы массивов должны быть числовыми, в то время как мы часто предпочитаем манипулировать этими структурами данных с помощью объектов.
Чтобы решить эту проблему, многие структуры данных пытаются присвоить объектам числовое значение, которое может служить индексом массива. Мы называем это значение хэш-значением или просто хэшем .
3. Хеширование
Хеширование – это преобразование объекта в числовое значение . Функции, выполняющие эти преобразования, называются хэш-функциями .
Для простоты рассмотрим хэш-функции, которые преобразуют строки в индексы массива, то есть в целые числа из диапазона [0, N] с конечным N .
Естественно, хэш-функция применяется к широкому спектру строк . Поэтому его “глобальные” свойства становятся важными.
К сожалению, невозможно, чтобы хэш-функция всегда преобразовывала разные строки в разные числа .
Мы можем довольно легко убедить себя, что число строк намного больше, чем число целых чисел в любом диапазоне [0, N] . Поэтому неизбежно, что существует пара неравных строк, для которых хэш-функция выдает равные значения. Это явление называется столкновением .
Мы не собираемся углубляться в технические детали, стоящие за хэш-функциями, но ясно, что хорошая хэш-функция должна пытаться равномерно отображать строки, на которых она определена, в числа.
Еще одним очевидным требованием является то, что хорошая хэш-функция должна быть быстрой. Если вычисление хэш-значения занимает слишком много времени, мы не сможем быстро получить доступ к элементам.
В этом уроке мы рассмотрим один из методов , которые пытаются сделать отображение однородным , сохраняя его быстрым.
4. Техника складывания
Наша цель-найти функцию, которая преобразует строки в индексы массивов. Просто чтобы проиллюстрировать эту идею, предположим, что мы хотим, чтобы этот массив обладал способностью 10 5 элементы и давайте использовать строку язык Java в качестве примера.
4.1. Описание
Давайте начнем с преобразования символов строки в числа. ASCII является хорошим кандидатом для этой операции:
Теперь мы упорядочиваем только что полученные числа в группы определенного размера. Как правило, мы выбираем значение размера группы на основе размера нашего массива, который 10 5 . Поскольку числа, в которые мы преобразовали символы, содержат от двух до трех цифр, без потери общности, мы можем установить размер группы равным двум:
Следующий шаг-объединить числа в каждой группе, как если бы они были строками, и найти их сумму:
Теперь мы должны сделать последний шаг. Давайте проверим, соответствует ли число 348933 может служить индексом нашего массива размера 10 5 . Естественно, он превышает максимально допустимое значение 99999. Мы можем легко преодолеть эту проблему, применив оператор по модулю, чтобы найти конечный результат:
348933 % 10000 = 48933
4.2. Заключительные Замечания
Мы видим, что алгоритм не включает в себя никаких трудоемких операций и, следовательно, он довольно быстр. Каждый символ входной строки вносит свой вклад в конечный результат. Этот факт определенно помогает уменьшить количество столкновений, но не избежать их полностью.
Например, если бы мы хотели пропустить сворачивание и применили оператор по модулю непосредственно к входной строке, преобразованной в ASCII (игнорируя проблему переполнения)
749711897321089711010311797103101 % 100000 = 3101
тогда такая хэш-функция будет выдавать одно и то же значение для всех строк , которые имеют те же последние два символа , что и наша входная строка: a ge , p age , lar ge, и так далее.
Из описания алгоритма мы легко видим, что он не свободен от коллизий. Например, алгоритм производит одно и то же хэш-значение для языка Java и языка vaJa строк .
5. Другие Методы
Техника складывания довольно распространена, но не единственная. Иногда методы binning или mid-square также могут быть полезны.
Мы проиллюстрируем их идею, используя не строки, а числа (предположим, что мы уже каким-то образом преобразовали строки в числа). Мы не будем обсуждать их преимущества и недостатки, но вы можете составить свое мнение после просмотра алгоритмов.
5.1. Техника Биннинга
Предположим, что у нас есть 100 целых чисел, и мы хотим, чтобы наша хэш-функция сопоставила их в массив из 10 элементов. Затем мы можем просто расположить эти 100 целых чисел в десять групп таким образом, чтобы первые десять целых чисел оказались в первой ячейке, вторые десять целых чисел оказались во второй ячейке и т. Д.:
5.2. Техника Среднего квадрата
Этот алгоритм был предложен Джоном фон Нейманом, и он позволяет нам генерировать псевдослучайные числа, начиная с заданного числа.
Давайте проиллюстрируем это на конкретном примере. Предположим, у нас есть четырехзначное число 1111 . Согласно алгоритму, мы квадратируем его, получая таким образом 1234321 . Теперь мы извлекаем четыре цифры из середины, например: 2343 . Алгоритм позволяет нам повторять этот процесс до тех пор, пока мы не будем удовлетворены результатом.
6. Заключение
В этом уроке мы рассмотрели несколько методов хеширования. Мы подробно описали технику складывания и дали краткое описание того, как можно достичь биннинга и среднего квадрата.
Как всегда, мы можем найти соответствующие фрагменты кода в нашем репозитории GitHub .