Рубрики
Без рубрики

Руководство по технике складывания на Java

Узнайте о самых популярных методах хеширования, их плюсах и минусах.

Автор оригинала: Andrew Shcherbakov.

1. введение

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

Мы более подробно обсудим так называемую технику складывания и дадим краткое введение в технику среднего квадрата и биннинга.

2. Обзор

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

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

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

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

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

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

3. Хеширование

Хеширование – это преобразование объекта в числовое значение . Функции, выполняющие эти преобразования, называются хэш-функциями .

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

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

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

Отображение строк в индексы массивов

Мы можем довольно легко убедить себя, что число строк намного больше, чем число целых чисел в любом диапазоне [0, N] . Поэтому неизбежно, что существует пара неравных строк, для которых хэш-функция выдает равные значения. Это явление называется столкновением .

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

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

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

4. Техника складывания

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

4.1. Описание

Давайте начнем с преобразования символов строки в числа. ASCII является хорошим кандидатом для этой операции:

Преобразуйте строку в ascii

Теперь мы упорядочиваем только что полученные числа в группы определенного размера. Как правило, мы выбираем значение размера группы на основе размера нашего массива, который 10 5 . Поскольку числа, в которые мы преобразовали символы, содержат от двух до трех цифр, без потери общности, мы можем установить размер группы равным двум:

Упорядочить коды ascii строки

Следующий шаг-объединить числа в каждой группе, как если бы они были строками, и найти их сумму:

Объедините и суммируйте числа

Теперь мы должны сделать последний шаг. Давайте проверим, соответствует ли число 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 .