Введение в хеширование в 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. Когда выполняется поиск элемента, в каждой записи в хеш-таблице выполняется поиск нужной записи, пока не будет найдена требуемая запись или пока не будет сделан вывод, что запись не существует в таблице.

Преимущества хеширования

Ниже приведены преимущества хеширования:

  1. Сравните содержимое двух файлов легко и эффективно, не открывая их.
  2. Хэш-функции используются при проверке целостности файла.
  3. С помощью хеширования операция поиска в структурах данных стала быстрее.
  4. Хеш-функции играют жизненно важную роль в безопасности данных, так как большинство алгоритмов и протоколов безопасности используют хеширование.
  5. Хеширование преобразует данные в более короткое значение фиксированной длины или ключ, который представляет собой исходную строку, которую можно отправить по сети.

Недостатки хеширования

Помимо преимуществ, существуют также некоторые ограничения хеширования:

  1. Хеширование не может быть реализовано для сортировки данных.
  2. Столкновения хешей практически невозможно избежать, что, в свою очередь, приводит к неэффективности.

Рекомендуемые статьи

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

  1. Декларация и инициализация VB.Net
  2. Java-программа, отображающая HashMap и TreeMap
  3. Типы хеширования в СУБД
  4. Техники стеганографии
  5. Массивы в программировании на Java
  6. Hashmap в Java