Контракти equals та hashCode або як воно все там

Переважна більшість програмуючих на Java звичайно ж знають, що методи equalsі hashCodeтісно пов'язані один з одним, і що обидва ці методи бажано перевизначати у своїх класах узгоджено. Трохи менше знають, чому це так і які сумні наслідки можуть бути, якщо порушити це правило. Пропоную розглянути концепцію цих методів, повторити їх призначення та розібратися, чому вони так пов'язані. Цю статтю, як і попередню завантаження класів, я писав для себе, щоб остаточно розкрити всі деталі питання і більше не повертатися до сторонніх джерел. Тому буду радий конструктивній критиці, оскільки якщо десь є прогалини, їх слід усунути. Стаття, на жаль, вийшла досить великою.

Правила перевизначення equals

Метод equals()необхідний Java для підтвердження або заперечення того факту, що два об'єкти одного походження є логічно рівними . Тобто, порівнюючи два об'єкти, програмісту необхідно зрозуміти, чи еквівалентні їх значущі поля . Не обов'язково всі поля мають бути ідентичними, оскільки метод equals()має на увазі саме логічну рівність . Але іноді немає особливої ​​потреби у використанні цього методу. Як кажуть, найлегший шлях уникнути проблем, використовуючи той чи інший механізм не використовувати його. Також слід зауважити, що одного разу порушивши контрактequalsви втрачаєте контроль над розумінням того, як інші об'єкти та структури взаємодіятимуть з вашим об'єктом. І згодом знайти причину помилки буде дуже важко.

Коли не варто перевизначати цей метод

• Коли кожен екземпляр класу є унікальним.
Більшою мірою це стосується тих класів, які надають певну поведінку, ніж призначені для роботи з даними. Таких, наприклад, як клас Thread. Їх реалізації методу equals, наданого класом Object, більш ніж достатньо. Інший приклад - класи перерахувань ( Enum).
• Коли насправді від класу не потрібно визначати еквівалентність його екземплярів.
Наприклад, для класу java.util.Randomвзагалі немає необхідності порівнювати між собою екземпляри класу, визначаючи, чи можуть вони повернути однакову послідовність випадкових чисел. Просто тому, що природа цього класу навіть не має на увазі таку поведінку.
• Коли клас, який ви розширюєте, вже має власну реалізацію способу equalsі поведінка цієї реалізації вас влаштовує.
Наприклад, для класів Set, List, Mapреалізація equalsзнаходиться у AbstractSet, AbstractListі AbstractMapвідповідно.
• І, нарешті, немає необхідності перекривати equals, коли область видимості вашого класу є privateабо package-privateви впевнені, що цей метод ніколи не буде викликаний.

Контракт equals

При перевизначенні методу equalsрозробник повинен дотримуватися основних правил, визначених специфікації мови Java.

• Рефлексивність
для будь-якого заданого значення x, вираз x.equals(x)має повертати true.
Заданого - мається на увазі такого, щоx != null
• Симетричність
для будь-яких заданих значень xі y, x.equals(y)має повертати trueтільки в тому випадку, y.equals(x)коли true.
• Транзитивність
для будь-яких заданих значень x, yі z, якщо x.equals(y)повертає trueта y.equals(z)повертає true, x.equals(z)має повернути значення true.
• Узгодженість
для будь-яких заданих значень xта yповторний виклик x.equals(y)повертатиме значення попереднього виклику цього методу за умови, що поля, які використовуються для порівняння цих двох об'єктів, не змінювалися між викликами.
• Порівняння null
для будь-якого заданого значення xвиклик x.equals(null)повинен повертати false.

Порушення контракту equals

Багато класи, наприклад класи з Java Collections Framework, залежить від реалізації методу equals(), тому варто їм нехтувати, т.к. Порушення договору цього може призвести до нераціональної роботі програми й у разі знайти причину буде досить складно. Відповідно до принципу рефлексивності , кожен об'єкт має бути еквівалентним самому собі. Якщо цей принцип буде порушено, при додаванні об'єкта в колекцію та при подальшому пошуку його за допомогою методу contains()ми не зможемо знайти той об'єкт, який щойно поклали до колекції. Умова симетричностісвідчить, що два будь-яких об'єкти повинні бути рівними незалежно від того, в якому порядку вони будуть порівнюватися. Наприклад, маючи клас, що містить одне поле рядкового типу, буде неправильно порівнювати в методі equalsдане поле з рядком. Т.к. у разі зворотного порівняння метод завжди поверне значення false.

// Нарушение симметричности
public class SomeStringify {
    private String s;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o instanceof SomeStringify) {
            return s.equals(((SomeStringify) o).s);
        }
        // нарушение симметричности, классы разного происхождения
        if (o instanceof String) {
            return s.equals(o);
        }
        return false;
    }
}

//Правильное определение метода equals
@Override
public boolean equals(Object o) {
    if (this == o) return true;
    return o instanceof SomeStringify &&
            ((SomeStringify) o).s.equals(s);
}

З умови транзитивності випливає, що якщо будь-які два з трьох об'єктів рівні, то в такому разі мають бути рівні три. Цей принцип легко порушити у разі, коли потрібно розширити якийсь базовий клас, додавши щодо нього значний компонент . Наприклад, до класу Pointз координатами xнеобхідно yдодати колір точки, розширивши його. Для цього потрібно оголосити клас ColorPointіз відповідним полем color. Таким чином, якщо в розширеному класі викликати метод equalsбатька, а в батьківському вважатимемо, що порівнюються лише координати xтаyтоді дві точки різного кольору, але з однаковими координатами будуть вважатися рівними, що неправильно. У такому разі необхідно навчити похідний клас розрізняти кольори. Для цього можна скористатися двома способами. Але один порушуватиме правило симетричності , а другий — транзитивності .

// Первый способ, нарушая симметричность
// Метод переопределен в классе ColorPoint
@Override
public boolean equals(Object o) {
    if (!(o instanceof ColorPoint)) return false;
    return super.equals(o) && ((ColorPoint) o).color == color;
}

І тут виклик point.equals(colorPoint)поверне значення true, а порівняння colorPoint.equals(point)— false, т.к. очікує об'єкт "свого" класу. У такий спосіб і порушується правило симетричності. Другий спосіб має на увазі робити "сліпу" перевірку, у разі, коли немає даних про колір точки, тобто маємо клас Point. Або перевіряти колір, якщо інформація про нього доступна, тобто порівнювати об'єкт класу ColorPoint.

// Метод переопределен в классе ColorPoint
@Override
public boolean equals(Object o) {
    if (!(o instanceof Point)) return false;

    // Слепая проверка
    if (!(o instanceof ColorPoint))
        return super.equals(o);

    // Полная проверка, включая цвет точки
    return super.equals(o) && ((ColorPoint) o).color == color;
}

Принцип транзитивності тут порушується так. Допустимо, є визначення наступних об'єктів:

ColorPoint p1 = new ColorPoint(1, 2, Color.RED);
Point p2 = new Point(1, 2);
ColorPoint p3 = new ColorPoint(1, 2, Color.BLUE);

Таким чином хоч і виконується рівність і p1.equals(p2)поверне значення . У цьому другий спосіб, мій погляд, виглядає менш привабливим, т.к. в деяких випадках алгоритм може засліпнути і не виконати порівняння повною мірою, а ви про це можете і не дізнатися. Трохи лірики Загалом конкретного вирішення цієї проблеми, як я зрозумів, немає. Існує думка одного авторитетного автора на ім'я Кей Хорстманн, що можна замінити використання оператора на виклик методу , який повертає клас об'єкта і, перш ніж почати порівнювати самі об'єкти, переконатися, що вони одного типу, а на факт їхнього загального походження не звертати уваги. Таким чином, правила симетричності та транзитивностіp2.equals(p3)p1.equals(p3)falseinstanceofgetClass()будуть виконані. Але при цьому з іншого боку барикади стоїть ще один не менш шанований у широких колах автор Джошуа Блох, який вважає, що такий підхід порушує принцип підстановки Барбари Лисков. Цей принцип говорить, що “викликаючий код повинен працювати з базовим класом так само, як і з його підкласами, не знаючи про це” . І у рішенні, запропонованому Хорстманном, цей принцип явно порушується, тому що залежить від реалізації. Коротше справа ясна, що справа темна. Слід також зазначити, що Хорстманн уточнює правило застосування свого підходу і англійською по білому пише, що потрібно визначитися зі стратегією при проектуванні класів, і якщо перевірка на рівність проводитиметься лише силами суперкласу, можна це робити, виконуючи операціюinstanceof. Інакше, коли семантика перевірки змінюється залежно від похідного класу і методу потрібно спустити вниз по ієрархії, необхідно використовувати метод getClass(). Джошуа Блох, у свою чергу, пропонує відмовитися від успадкування і скористатися композицією об'єктів, включивши до складу класу клас ColorPointі Pointнадавши метод доступу asPoint()для отримання інформації конкретно про точку. Це дозволить уникнути порушення всіх правил, але, як на мене, ускладнить розуміння коду. Третій варіант – скористатися автоматичною генерацією методу equals за допомогою IDE. Idea, до речі, відтворює генерацію за Хорстманном, причому дозволяючи вибрати стратегію реалізації методу у суперкласі чи його спадкоємцях. І, нарешті, таке правило узгодженостіговорить, що й об'єкти xі yзмінюються, повторний виклик x.equals(y)повинен відновити те саме значення, як і раніше. Останнє правило полягає в тому, що жоден об'єкт не повинен дорівнювати null. Тут усе зрозуміло null— це невизначеність, чи об'єкт невизначеності дорівнює? Незрозуміло, тобто false.

Загальний алгоритм визначення equals

1. Перевірити рівність посилання об'єктів thisі параметра методу o.
   if (this == o) return true;
2. Перевірити, чи визначено посилання o, тобто є вона null.
   Якщо в подальшому при порівнянні типів об'єктів використовуватиметься оператор instanceof, цей пункт можна пропустити, тому що цей параметр повертає falseв даному випадку null instanceof Object.
3. Порівняти типи об'єктів thisі oза допомогою оператора instanceofабо методу getClass(), керуючись описом вище та власним чуттям.
4. Якщо метод equalsперевизначається у підкласі, не забудьте зробити викликsuper.equals(o)
5. Перетворення типу параметра oдо потрібного класу.
6. Здійснити порівняння всіх значних полів об'єктів:
   • для примітивних типів (крім floatі double), використовуючи оператор==
   • для посилальних полів необхідно викликати їх методequals
   • для масивів можна користуватися перебором по циклу, або шляхомArrays.equals()
   • для типів floatі doubleнеобхідно використовувати методи порівняння відповідних обгорткових класів Float.compare()таDouble.compare()
7. І, нарешті, відповісти на три питання: чи є реалізований метод симетричним ? Транзитивним ? Узгодженим ? Два інших принципи ( рефлексивність та визначеність ), як правило, виконуються автоматично.

Правила перевизначення hashCode

Хеш - це деяке число, що генерується на основі об'єкта і описує його стан в якийсь момент часу. Це число використовується Java переважно в хеш-таблицях, таких як HashMap. При цьому хеш-функція отримання числа на основі об'єкта повинна бути реалізована таким чином, щоб забезпечити рівномірний розподіл елементів по хеш-таблиці. А також мінімізувати можливість появи колізій, коли за різними ключами функція поверне однакове значення.

Контракт hashCode

Для реалізації хеш-функції у специфікації мови визначено такі правила:

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

Методи equals та hashCode необхідно перевизначати разом

Виходячи з описаних вище контрактів слід, що перевизначаючи у своєму коді метод equals, необхідно завжди перевизначати і метод hashCode. Так як фактично два екземпляри класу відрізняються, тому що знаходяться в різних сферах пам'яті, порівнювати їх доводиться за деякими логічними ознаками. Відповідно, два логічно еквівалентні об'єкти повинні повертати однакове значення хеш-функції. Що станеться, якщо буде перевизначено лише один із цих методів?

1. equalsє, hashCodeні

   Допустимо ми правильно визначабо метод equalsу нашому класі, а метод hashCodeвирішабо залишити як він є у класі Object. Тоді з погляду методу equalsдва об'єкти будуть логічно рівні, тоді як із погляду методу hashCodeвони нічого очікувати мати нічого спільного. І, таким чином, поміщаючи якийсь об'єкт у хеш-таблицю, ми ризикуємо не отримати його за ключом.
   Наприклад, так:

   Map<Point, String> m = new HashMap<>();
   m.put(new Point(1, 1), “Point A”);
   // pointName == null
   String pointName = m.get(new Point(1, 1));

   Очевидно, що об'єкт, що міститься і шукається, — це два різні об'єкти, хоча вони і є логічно рівними. Проте, т.к. вони мають різне хеш-значення, тому що ми порушабо контракт, можна сказати, що ми втратабо свій об'єкт десь у надрах хеш-таблиці.

2. hashCodeє, equalsні.

   Що буде, якщо ми перевизначимо метод hashCode, а реалізацію методу equalsуспадкуємо з класу Object. Як відомо, метод equalsза замовчуванням просто порівнює покажчики на об'єкти, визначаючи, чи посилаються вони на той самий об'єкт. Припустимо, що метод hashCodeми написали за всіма канонами, а саме згенерували засобами IDE, і він повертатиме однакові хеш-значення для логічно однакових об'єктів. Очевидно, що цим ми вже визначабо деякий механізм порівняння двох об'єктів.
   

   Отже, приклад із попереднього пункту за ідеєю має виконуватися. Але ми, як і раніше, не зможемо знайти наш об'єкт у хеш-таблиці. Хоча будемо вже близькі до цього, бо щонайменше знайдемо кошик хеш-таблиці, в якому об'єкт лежатиме.
   

   Для успішного пошуку об'єкта в хеш-таблиці крім порівняння хеш-значень ключа використовується також визначення логічної рівності ключа з об'єктом, що шукається. Т. е. без перевизначення методу equalsніяк не вийде обійтися.

Загальний алгоритм визначення hashCode

Тут, мені здається, взагалі не варто сильно переживати та виконати генерацію методу у своїй улюбленій IDE. Тому що всі ці усунення бітів праворуч, ліворуч у пошуку золотого перерізу, тобто нормального розподілу — це для зовсім затятих чуваків. Особисто я сумніваюся, що зможу зробити краще та швидше, ніж та сама Idea.

Замість ув'язнення

Таким чином, ми бачимо, що методи equalsі hashCodeвідіграють чітко певну роль у мові Java і призначені для одержання характеристики логічної рівності двох об'єктів. У випадку з методом equalsце має пряме відношення до порівняння об'єктів, у разі hashCodeнепряме, коли необхідно, скажімо так, визначити зразкове розташування об'єкта в хеш-таблицях або подібних структурах даних з метою збільшення швидкості пошуку об'єкта. Крім контрактів equalsє hashCodeще одна вимога, що відноситься до порівняння об'єктів. Це узгодженість методу compareToінтерфейсу Comparableз методом equals. Ця вимога зобов'язує розробника завжди повертати x.equals(y) == true, колиx.compareTo(y) == 0. Т. е. ми бачимо, що логічне порівняння двох об'єктів не повинно суперечити ніде в додатку і завжди бути узгодженим.

Джерела

Effective Java, Second Edition. Joshua Bloch. Вільний переклад дуже непоганої книги. Java, бібліотека професіонала. Том 1. Основи. Кей Хорстманн. Трохи менше теорії та більше практики. Але не так детально розібрано все, як у Блоха. Хоча є свій погляд на той же equals(). Структури даних у картинках. HashMap Вкрай корисна стаття з пристрою HashMap у Java. Замість того, щоб вихідники дивитися.