Введение в хеширование в Java
Поскольку мы знаем, что Java является объектно-ориентированным языком, следовательно, должен существовать механизм для описания состояния объекта, независимо от того, насколько большим может быть объект. Хеш-функция в Java появилась для выполнения этого требования.
Что такое функция хеширования?
Хэш-функция может быть определена как функция, которая возвращает целочисленное значение, соответствующее объекту. Хэш-функция всегда возвращает одно и то же целочисленное значение для одного и того же объекта. Целочисленное значение, возвращаемое хэш-функцией, называется значением хеш-функции. Ниже приведены важные моменты, касающиеся функции хеширования:
- Всегда возвращает целое число (4 байта) для объекта.
- Мы не можем вычислить состояние объекта из хеш-значения, то есть хеш-функции необратимы по своей природе.
- Два равных объекта будут иметь одинаковое хеш-значение.
- Два неравных объекта не всегда имеют разные значения Hash.
Применение хэш-функции
Вот общие применения хеш-функций:
1. Структуры данных
Почти каждый язык программирования содержит структуры данных, основанные на хэше. Например, java содержит хэш-таблицу, хэш-карту, хэш-набор, структуры данных дерева, основанные на хэш-функции. Основой этих структур данных является дизайн Key-Value, в котором каждый ключ уникален, тогда как для нескольких ключей может существовать одно и то же значение.
2. Дайджест сообщения
Этот алгоритм используется при проверке целостности данных. Этот алгоритм принимает сообщение любой длины в качестве входных данных и создает данные фиксированной длины (128-битные) в качестве выходных данных. Примеры алгоритмов дайджеста сообщений включают MD2, MD4, MD5 и MD6.
3. Безопасный алгоритм хеширования
Этот алгоритм используется для защиты данных и используется в приложениях и протоколах, таких как Secure Socket Layer (SSL). SHA-0, SHA-1, SHA-2 и SHA-3 являются общими категориями алгоритма безопасного хеширования.
4. Проверка и хранение пароля
Давайте рассмотрим сценарий входа в систему, в котором при вводе пароля для аутентификации пользователя вычисляется хеш-значение введенного пароля и отправляется по сети на сервер, где хранится хеш-код оригинала. Это сделано для того, чтобы при пересылке пароля с сервера на сервер не было обнаружено никакого сниффинга.
5. Работа компилятора
Поскольку в языке программирования используются разные ключевые слова, чтобы различать эти ключевые слова и идентификаторы, компилятор использует хэш-набор, который реализован с использованием хэш-таблицы для хранения всех этих ключевых слов и идентификаторов.
6. Алгоритм Рабина-Карпа
Это алгоритм поиска, который использует хеширование для поиска одного или нескольких шаблонов в заданной строке. Это один из наиболее часто используемых алгоритмов.
7. Сопоставимые и компараторские интерфейсы
Эти интерфейсы содержат функции, которые используются для сравнения двух объектов одновременно. Возвращаемое значение этих функций может быть отрицательным, нулевым или положительным в зависимости от того, является ли данный объект меньше, равен или больше, чем объект, с которым мы сравниваем. Внутренне компаратор и сопоставимые интерфейсы используют хэш-функцию для сравнения объектов друг с другом.
8. Очередь приоритетов
Очередь с приоритетом отличается от обычной очереди, которая следует порядку FIFO (первый пришел первым вышел). В очереди приоритетных элементов расположены в произвольном порядке на основе их приоритета, который реализован внутри с использованием сопоставимых и компаратор, которые стажеры основаны на хэш-функциях.
Проектирование хеш-функций
Вот некоторые общие принципы проектирования для создания хеш-функций:
- Хэш-функция должна быть эффективно оценена.
- Хеш-значения, вычисленные по хеш-функциям, должны быть равномерно распределены, это помогает избежать коллизий.
- Язык программирования Java предоставляет общую функцию хеширования с помощью метода hashCode () в суперклассе Object.
public int hashCode ()(
//Logic goes here
)
Столкновение хэшей в Java
Столкновение хеш-функции происходит, когда два или более объекта возвращают одно и то же хеш-значение. Давайте возьмем пример карты хэша Java, которая хранит данные в парах ключ-значение. Когда мы помещаем объект в хэш-карту, вычисляется хэш-значение ключа, и на основе этого местоположения хэш-значения определяется место хранения объекта значения. Объекты с разными значениями хеша должны входить в разные сегменты. Когда два или более объекта имеют одинаковое значение хеш-функции, они сохраняются в одном и том же месте группы, используя дополнительную структуру данных, называемую связанным списком. Все объекты, имеющие одно и то же значение хеш-функции, объединяются в один связанный список. Этот механизм называется цепочкой. Ниже приведены способы обработки столкновений с помощью хэш-функции:
- Цепочка: как уже говорилось, идея цепочки заключается в создании связанного списка объектов, имеющих одинаковое значение хеш-функции. Цепочка является простой техникой, но требует дополнительных затрат памяти.
- Открытая адресация. В этом методе все элементы хранятся в хеш-таблице, в которой каждая запись содержит запись или значение NULL. Когда выполняется поиск элемента, в каждой записи в хеш-таблице выполняется поиск нужной записи, пока не будет найдена требуемая запись или пока не будет сделан вывод, что запись не существует в таблице.
Преимущества хеширования
Ниже приведены преимущества хеширования:
- Сравните содержимое двух файлов легко и эффективно, не открывая их.
- Хэш-функции используются при проверке целостности файла.
- С помощью хеширования операция поиска в структурах данных стала быстрее.
- Хеш-функции играют жизненно важную роль в безопасности данных, так как большинство алгоритмов и протоколов безопасности используют хеширование.
- Хеширование преобразует данные в более короткое значение фиксированной длины или ключ, который представляет собой исходную строку, которую можно отправить по сети.
Недостатки хеширования
Помимо преимуществ, существуют также некоторые ограничения хеширования:
- Хеширование не может быть реализовано для сортировки данных.
- Столкновения хешей практически невозможно избежать, что, в свою очередь, приводит к неэффективности.
Рекомендуемые статьи
Это руководство по функции хеширования в Java. Здесь мы обсуждаем применение хэш-функции наряду с преимуществами и недостатками. Вы также можете посмотреть следующие статьи, чтобы узнать больше -
- Декларация и инициализация VB.Net
- Java-программа, отображающая HashMap и TreeMap
- Типы хеширования в СУБД
- Техники стеганографии
- Массивы в программировании на Java
- Hashmap в Java