Як згенерувати хеш-код у Java

Хеш-код — це унікальне числове значення, яке використовується для ідентифікації об’єктів. Найчастіше, воно використовується для прискорення пошуку, вставки та видалення елементів у таких структурах, як HashMap, HashSet та інших.

У Java кожен об’єкт має метод hashCode(), який генерує це значення. Проте, коли ви створюєте власні класи, важливо знати, як правильно перевизначити цей метод, щоб забезпечити коректну роботу з об’єктами у хеш-таблицях. За більш поглибленими знаннями звертайтеся до академії FoxmindEd. Там ви знайдете курси по розробці, та зможете стати професійним програмістом, який використовує Java як мову для програмування.

Звісно, hashCode() використовується не лише із колекціями. Він також застосовується у кешуванні, аналізі даних та інше. Проте у цій статті ми розглянемо, як працює метод hashCode() в Java, які алгоритми можна використовувати для його перевизначення саме з точки зору використання у колекціях, адже це основне, де ви будете із ним працювати.

Методи для генерації хеш-коду у Java

У Java кожен об’єкт має вбудований метод hashCode(), який призначений для генерації хеш-коду. Цей метод є частиною базового класу Object, від якого наслідуються всі класи в Java. Давайте розглянемо, як цей метод працює та як його можна перевизначити для кастомних класів.

Метод hashCode() у класі Object повертає цілочислове значення, яке зазвичай базується на адресі пам’яті об’єкта. За замовчуванням, реалізація hashCode() у класі Object не гарантує жодних особливих властивостей, окрім того, що для різних об’єктів результат, як правило, буде різним.

У багатьох випадках стандартна реалізація методу hashCode() не є достатньо ефективною для використання у власних класах, особливо коли вони будуть використовуватися у хеш-таблицях. У такому випадку необхідно перевизначити метод hashCode() таким чином, щоб він враховував унікальні поля вашого класу.

При перевизначенні hashCode(), важливо дотримуватись таких принципів:

• Однакові об’єкти (тобто об’єкти, для яких метод equals() повертає true) повинні  завжди мати однаковий хеш-код.
• Різні об’єкти можуть мати однаковий хеш-код, але це має траплятися якомога рідше.

Проте, як же у двох об’єктів може вирахуватися однаковий хеш код? Таке явище називаєтьс називається хеш-колізією. І це відбувається тому, що хеш-код — це обмежене числове значення (зазвичай ціле число), яке обчислюється на основі внутрішніх властивостей об’єкта.

FoxmindEd – це навчальний центр, що має велику різноманітність напрямків курсів для новачків та програмістів з досвідом!

Тільки починаєте свій шлях в ІТ? Спробуйте курси Start

Вже маєте базові навички програмування? Тоді
курси Junior саме для вас.

Хочете поглибити свої знання в ІТ? Ми маємо курси Middle/Senior

Чому виникає хеш-колізія?

1. Обмежений діапазон значень: У Java метод hashCode() повертає 32-бітове ціле число (тип int). Це означає, що існує 2^32 (близько 4 мільярдів) можливих значень хеш-коду. Однак кількість можливих об’єктів або їх комбінацій властивостей набагато більша (теоретично безкінечна). Тому, коли два різних об’єкти генерують одне і те ж числове значення, виникає колізія.
2. Використання однакового алгоритму: Хеш-коди обчислюються за певним алгоритмом. Навіть якщо два об’єкти мають різні поля, можливе таке їх поєднання, при якому кінцевий результат (хеш-код) буде однаковим.

Для перевизначення hashCode() найчастіше використовуються кілька підходів.

1. Простий алгоритм на основі простих чисел:

Вибирається початкове число (наприклад, 17) і множиться на просте число (наприклад, 31) для кожного значущого поля. Наприклад:

@Override

public int hashCode() {

   int result = 17;

   result = 31 * result + (field1 != null ? field1.hashCode() : 0);

   result = 31 * result + field2;

   return result;

}

Цей підхід забезпечує хорошу рівномірність розподілу хеш-кодів і мінімізує колізії (ситуації, коли у різних об’єктах можуть вирахуватися однакові хеш коди).

2. Складніший алгоритм на основі побітових операцій:

Для підвищення ефективності можна використовувати побітові зсуви та побітові операції AND, OR. Це дозволяє більш рівномірно розподілити хеш-коди для різних значень.

@Override

public int hashCode() {

   int result = field1.hashCode();

   result = 31 * result + (int) (field2 ^ (field2 >>> 32));

   return result;

}

3. Застосування бібліотеки Objects.hash():

Java також пропонує метод Objects.hash(), який дозволяє спростити процес генерації хеш-коду. Цей метод приймає довільну кількість аргументів і автоматично обчислює хеш-код, що базується на цих значеннях.

@Override

public int hashCode() {

   return Objects.hash(field1, field2, field3);

}

Найкращі практики при перевизначенні hashCode()

1. Дотримання контракту між hashCode() та equals()

• Однаковий хеш-код для рівних об’єктів. Якщо два об’єкти вважаються рівними по equals(), вони повинні мати однаковий хеш-код. Це основне правило, яке забезпечує коректну роботу хеш-таблиць.
• Необов’язкова різність хеш-кодів для різних об’єктів. Два об’єкта, що рівні по hashcode можуть бути рівні по equals, а можуть і ні.
• Різні хеш-коди для різних об’єктів. Якщо у 2 об‘єктів різні хешкоди, то об‘єкти мають бути різні по equals.
• Стабільність хеш-коду. Один об‘єкт має повторно повертати один хешкод, якщо його поля не змінювалися. 

Чому важливо перевизначати equals() і hashCode():

• Некоректне зберігання дублікатів: Якщо hashCode() та equals() перевизначені неправильно, у хеш-таблицях, таких як HashSet, можуть зберігатися дублікатні об’єкти, хоча цього не повинно відбуватися. Це порушує основну концепцію таких колекцій, де кожен елемент має бути унікальним.
• Проблеми з пошуком у хеш-таблицях: Неправильне перевизначення методу hashCode() може спричинити проблеми з пошуком у хеш-таблицях, таких як HashMap або HashSet. Якщо об’єкти, що мають рівні значення, отримують різні хеш-коди, пошук може стати менш ефективним, оскільки це порушує рівномірний розподіл об’єктів по бакетам (кошикам) хеш-таблиці.

2. Використання значущих полів

Перевизначаючи метод hashCode(), слід враховувати всі поля, які впливають на рівність об’єктів (equals()). Якщо ви забули включити деяке поле в розрахунок хеш-коду, це може призвести до ситуації, коли два рівні об’єкти матимуть різні хеш-коди, що порушує контракт між hashCode() та equals().

3. Вибір простих чисел

При розрахунку хеш-коду часто використовують множення на прості числа, наприклад, 31. Це дозволяє отримати хороший розподіл значень хеш-кодів і зменшити кількість колізій.

Висновок

Правильне перевизначення методу hashCode() у Java є важливим завданням, яке значно впливає на роботу ваших об’єктів у програмі. Генерація коректного хеш-коду забезпечує правильну ідентифікацію об’єктів і дозволяє уникнути багатьох потенційних помилок. Дотримання контракту між методами hashCode() та equals() є ключовим фактором, що гарантує, що рівні об’єкти завжди матимуть однаковий хеш-код, а різні — різні.

При перевизначенні hashCode() важливо використовувати значущі поля об’єкта, обирати відповідний алгоритм для обчислення хеш-коду і враховувати стабільність його значень. Це забезпечить надійну роботу вашого коду, зменшить ймовірність виникнення колізій та підвищить ефективність ваших програм.