Създаване на ефикасна и ефективна функция на hashCode в Java

В Java някои вградени библиотеки зависят от внедрения метод на хешкод на обекта. Например HashMap и HashSet зависят от стойността, върната от този метод. Осигуряването на правилното внедряване на hashCode е ЗАДЪЛЖИТЕЛНО, не само за да работят ефективно тези структури от данни, но и за да им позволи да обработват тези обекти ефективно. В тази статия ще проучим общия договор за правилно внедряване на hashCode, кога е важно да го внедрим, как да напишем най-съвременния и някои трикове за оптимизиране на неговата производителност.

Връзка между equals и hashCode

Когато методът equals() е отменен в клас, важно е също така да се предостави имплементация за метода hashCode(), за да се гарантира правилното функциониране на класа в колекции, които разчитат на хеш кодове, като HashMap и HashSet. Не забравяйте, че е важно да включите всяко значимо поле в изчисляването на хеш кода за клас, който участва в метода equals(). Мислете за тях като за отражение един на друг. За клас, който итерира масив, за да провери за равенство, изпълнението на метода hashCode() също трябва да итерира същия масив, за да изчисли хеш кода за всеки елемент. Можете да проверите моята публикация относно внедряването на метода equals, за да сте сигурни, че тези два метода работят надеждно.

Общият договор за изпълнение на Object.hashCode().

• Ако методът hashCode() се извика многократно на обект по време на изпълнение на приложение, той винаги трябва да връща една и съща стойност, стига да не е променена информацията, използвана в сравненията с equals().
• Ако два обекта са равни, според техния метод equals(Object), тогава извикването на техните методи hashCode трябва да доведе до същия резултат.
• По-добре е нееднаквите обекти да имат различни хеш кодове. В един не толкова идеален свят е възможно два обекта, които не са равни, да имат един и същ хеш код.

Еднаквите обекти трябва да имат еднакви хеш кодове. Нарушаването на това правило би накарало колекция като HashMap да се държи неочаквано. Нека да видим пример за поведението на HashMap в резултат на нарушение на втората част от договора. Да приемем, че Person.hashCode() има грешна реализация, която дава различни резултати за еднакви обекти.

/* Example of HashMap behaviour as result of 
   violation of the second part of the contract */
Map<Person, Integer> map = new HashMap<>();

Person p1 = new Person("Name", 20);
Person p2 = new Person("Name", 20);

p1.equals(p2); // true

map.put(p1, 800);
map.get(p2); // Is null

Можем да приемем, че p1.hashCode() връща 10, а p2.hashCode() връща 100. Извикването на map.put(p1, 800) вмъква p1 в кофа, съответстваща на неговия хеш код, който е 10. От друга страна извикването на map.get(p2) се опитва да намери p2 в контейнер, който съответства на неговия хеш код, който е 100. Ясно е, че ще върне нула, защото не съществува там. Ето какво ще се случи при нарушаване на втората част от договора. Когато еднакви обекти, базирани на реализацията на метода equals, имат различни хеш кодове, всяка колекция или клиентски код, които разчитат на тази хеш стойност, ще се държат по грешен начин.

Когато пишем функцията hashCode, ние се стремим да изпълним две основни изисквания. Първо, обектите, които се считат за равни, трябва да произвеждат един и същ хеш код. Освен това добрата хеш функция има тенденция да дава различни резултати за различни обекти. Второ, хеш функцията е по-добра за генериране на хеш кодове, които са равномерно разпределени сред краен диапазон от стойности. Това намалява броя на колизиите по време на вмъкването в базирани на хеш структури от данни. Ако всички обекти имат един и същ хеш, това означава, че структура от данни като HashMap ще се държи като LinkedList, защото обработва сблъсъци, използвайки концепция, наречена Разделно верижно свързване. В реалния свят предотвратяването на сблъсък е почти невъзможно, но бихме могли да постигнем по-добри резултати с доброто внедряване на метода hashCode.

Как да достигнем справедливо приблизително решение без сблъсъци

1. Изчислете hashCode за първото значимо поле „A“ и го запазете в променлива (да приемем, че името й е hashResult).

• Ако „A“ е примитивен тип, извикайте метода hashCode на неговия обвиващ клас.
• Извикайте A.hashCode(), ако това е препратка към обект. Ако обектът е нула, можете да го замените с всяка постоянна стойност, но нулата е най-често срещаната.
• Ако това е масив, ние считаме всеки запис за важен обект. И така, итерирайте през масива и натрупайте всеки хеш код до hashResult.

2. За останалите значими полета извикайте техния метод hashCode и го сумирайте до предварително изчисленото hashResult * 31

Изборът на числото 31, защото е просто число и лесно се изчислява с помощта на оператора shift, който е много по-бърз от нормалното умножение

Един пример е по-добре да илюстрира тези стъпки.

class Employee {
	private int age;
	private int salary;
	private String name;

	private int hashResult;

	public Employee(int age, int salary, String name) {
		this.age = age;
		this.salary = salary;
                this.name = name;
	}

	@Override
	public int hashCode() {
		hashResult = Integer.hashCode(age);
		hashResult = 31 * hashResult + Integer.hashCode(salary);
		hashResult = 31 * hashResult + (name == null ? 0 
                    : name.hashCode());

		return hashResult;
	}
}

Тук се елиминира методът "равно" за съкращаване на кода, но той трябва да използва тези полета за своя резултат, в този случай възраст, заплата и име. Ако обектът съдържа производно поле (поле, чиято стойност се извлича от едно или повече полета), например, целочисленото поле дни се изчислява от начало и край дати, той не трябва да участва в изчислението на хеш кода, ако стойностите, използвани за извличането му, вече са били използвани в изчислението. В този случай можем да изключим полето дни, ако началните и крайните дати са включени в изчисляването на хеш кода.

// Immutable class
class Point {
    private final int x;
    private final int y;
    private int hashResult; 

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int hashCode() {
        int result = hashResult;
        
        if(result == 0){
            result = Integer.hashCode(x);
            result = 31 * result + Integer.hashCode(y);
            
            hashResult = result;
        }
        return hashResult;
    }
}