Сигурно си спомняте за контракта между hashCode и equals :
1.Ако два обекта са еднакви (equal), то те задължително трябва да имат едни и същи хеш кодове.
2.Ако два обекта имат едни и същи хеш кодове, те могат, а могат и да не бъдат еднакви – това е в зависимост от устойчивостта на хеш функцията на колизии.
Как действат на практика тези правила при структурите, използващи хеш?
Както споменахме, HashMap съхранява обектите си на базата на някакъв ключ, който също е обект. От изключителна важност е да сме предефинирали двойката методи за този ключ. Хеш кодът е необходим при въвеждане на двойката <K,V> – по него после се търси съответната стойност. Ако той не е достатъчно консистентен, то ще се получи колизия, но новата двойка ще бъде съхранена, само при условие, че сравнението на двата ключа с equals дава резултат лъжа. При търсене на стойност, за която ключът вече е участвал в колизия, следва да се сравнят с equals стойностите на тези ключове, в резултат на което ще се разбере точно коя стойност да се върне. Затова, освен хеш на ключа, маповете съхраняват и истинския ключ заедно със стойността.
Нека да разгледаме подробно как е организиран един HashMap. Както казахме той имплементира интерфейса Map. На ниско ниво представлява един масив от обекти. Долната фигура го илюстрира:
По подразбиране всеки HashMap се инициализира с 16 елемента, които първоначално, естествено, са null. Както споменахме, освен ключ и стойност, се пази и хеш кода на ключа, така че това е и причината HashMap вътрешно да съхранява двойките, които му подаваме, като обекти от нов тип – типът Entry. Има и друга причина, но за нея – след малко. Нека разгледаме какво представлява вложения клас Entry:
Както се вижда, ключът се съхранява като final променлива, но е добавен още един обект от същия тип Entry<K,V> next. Тази променлива, при липса на колизия има стойност null, a при колизия – сочи към следващото Entry. Всъщност истинската причина HashMap да съхранява подадените двойки в свой обект от тип Entry е точно тази – че трябва да поддържа свързан списък, в случай на колизии.
Така всъщност се оказва, че HashМаp представлява масив от обекти от тип Entry<K,V>, като при особени случаи всяко Entry се превръща в свързан списък. Можем да приемем, че ако няма колизия, то Entry е просто свързан списък с един елемент. Всеки индекс на основния масив от Entry се нарича bucket.
Нека имаме опитна постановка от предната статия- клас Person и клас Namе с предефинирани методи equals и hashcode.
Test:
public static void main(String[] args) {
Map<Name, Person> mapOfPeople = new HashMap<Name, Person>();
Name name1 = new Name("Ivan", "Ivanov", "Ivanov");
Name name2 = new Name("Georgi", "Georgiev", "Georgiev");
Name name3 = new Name("Petyr", "Petrov", "Petrov");
Name name4 = new Name("Geri", "Georgieva", "Petrova");
Person p1 = new Person(name1, 25);
Person p2 = new Person(name2, 45);
Person p3 = new Person(name3, 18);
Person p4 = new Person(name4, 21);
mapOfPeople.put(name1, p1);
mapOfPeople.put(name2, p2);
mapOfPeople.put(name3, p3);
mapOfPeople.put(name4, p4);
}
Наблюдаваме какво се случва в структурата, като използваме Inspect опция на дебъг режима на Eclipse:
Това, което ще се случи след първото добавяне на двойка <K,V> е следното:
На подадения ключ name1 се изчислява hashCode() и той е -463305792. Това обаче е прекалено голямо число, за да послужи като индекс на масива от Entry<K,V>. Добре ще бъде, ако се може да се постави в границите на масива по подразбиране с големина 16 елемента. За целта, полученият код се дели на дължината на масива(например 16) и се взима остатъкът от целочисленото делене, който винаги е по –малък или равен на дължината на масива. В нашия случай ще получим индекс= 463305792%16 = 0 (за оптимизация JVM изчислява индекса като побитова операция). Което означава, че новосъздаденият обект от тип Entry ще бъде поставен на позиция 0. Член променливата му next ще бъде null, тъй като за сега нямаме колизия. Този индекс се получи съвсем случайно – няма никаква гаранция на коя позиция ще се запази първата двойка:
Съвсем аналогично се добавя и следващата двойка <K,V>:
И така до края:
Както виждате подредбата на елементите в масива става на базата на хеш кода. Ние въведохме двойките с ключове в последователност: “Ivan”, “Georgi”, “Petyr”, “Geri” а на извадката виждате реално как са подредени вътре.
За да демонстрираме колизия и да покажем какво се случва в структурата при колизия, съвсем умишлено ще предефинираме хеш кода да се изчислява, без бащиното име:
public class Name{
......
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result
+ ((firstName == null) ? 0 : firstName.hashCode());
result = prime * result
+ ((lastName == null) ? 0 : lastName.hashCode());
return result;
}
Така, ако създадем два обекта от тип Name с еднакви първи и трети имена, но с различни втори, хеш кодът им ще бъде един и същ. Например:
Иван Петров Иванов и Иван Георгиев Иванов
В този случай ще очакваме колизия.
Тестваме:
public static void main(String[] args) {
Map<Name, Person> mapOfPeople = new HashMap<Name, Person>();
Name name1 = new Name("Ivan", "Ivanov", "Ivanov");
Name name5 = new Name("Ivan", "Georgiev", "Ivanov");
Person p1 = new Person(name1, 25);
Person p5 = new Person(name5, 45);
mapOfPeople.put(name1, p1);
mapOfPeople.put(name5, p5);
}
Какво ще се случи, когато добавим name1 и name5:
Ето как изглежда ситуацията в Debug режим:
Както очаквахме – стойността на член променливата на първото Entry вече не е null, а сочи към второто Entry. При втора колизия на индекс 12, ще продължи да се запълва свързаният списък по същата логика. Как обаче HashMap-а се справя с това да отсява кое е колизия и кое е просто съвпадение на ключовете, тъй като се знае, че при дублиране, той заменя старата двойка с новата? Вече разгледахме класа Entry- той пази освен хеш кода и самия ключ. Когато се опитваме да вмъкнем двойка ключ и стойност в структурата, най-общо се спазва следната последователност:
1. Ключът от двойката Entry<K,V> се хешира.
2. По получения хеш се изчислява индекса.
3. Ако този bucket(на този индекс) има стойност null, се създава ново Entry<K и се записва на тази позиция.
4. Ако първият елемент на bucket-a е различен от null, то най-вероятно е настъпила колизия. В този случай подаденият ключ се сравнява(чрез equals()) с ключа на записаното Entry. Ако резултатът е истина, то някой се опитва да дублира ключ и новото Entry се презаписва върху старото. А ако резултатът е лъжа, то се продължава, в случай че next != null. Ако сравнението с всички ключове на този bucket даде лъжа, то се добавя новото Entry като последен елемент в свързания списък.
Сигурно вече разбирате, защо е необходимо да предефинирате и двата метода. Ако не предефинирате equals, то при при добавяне на нова двойка и установяване на колизия, HashMap няма как да провери дали просто не дублирате ключа (метод equals() ще върне true само при еднакви референции) и ще го добавя в свързания списък.
Нека премахнем предефинирания метод equals() от класа Name и да тестваме:
public static void main(String[] args) {
Map<Name, Person> mapOfPeople = new HashMap<Name, Person>();
Name name1 = new Name("Ivan", "Ivanov", "Ivanov");
Name name5 = new Name("Ivan", "Georgiev", "Ivanov");
Name name6 = new Name("Ivan", "Georgiev", "Ivanov");//new object with new address
Person p1 = new Person(name1, 25);
Person p5 = new Person(name5, 45);
Person p6 = new Person(name6, 90);
mapOfPeople.put(name1, p1);
mapOfPeople.put(name5, p5);
mapOfPeople.put(name6, p6);
Person foundPers = mapOfPeople.get(new Name("Ivan", "Georgiev", "Ivanov"));
if(foundPers == null){
System.out.println("No such person.");
}else{
System.out.println("Years of person are: " + foundPers.getYears());
}
}
Да видим какво се случва:
Вижда се, че без проблем вкарахме двойка с ключ, който реално вече съществува, и така заблудихме мап-а, че е настъпила колизия, но ключовете са различни.
Нека да опитаме да потърсим по ключ new Name(“Ivan”, “Georgiev”, “Ivanov”). Резултатът ще бъде “No such person.” Въпреки че виждаме, че вътре има двойка с такъв ключ. Причината отново в е това, че липсва предефинираният equals.
Нека да тестваме същия пример, но с предефинирания метод equals в класа Name:
Както се вижда, след mapOfPeople.put(name6, p6), той измества от мап-а двойката със същия ключ (name5,p5), както е редно. Резултатът е : Years of person are: 90.
Как се случва търсенето в структурата:
mapOfPeople.get(new Name(“Ivan”, “Georgiev”, “Ivanov”))
1. Ключът се хешира.
2. По получения хеш се изчислява индекса.
3. За всички елементи от свързания списък се проверява дали хеш кодовете им са едни и същи с изчисления хеш код. За тези, за които това е истина, се проверява дали записаният ключ е същият (equals) като този, по който търсим.
4. Ако equals върне true, то като резултат се връща съответната стойност (V).
Нека да обобщим казаното до тук:
• HashMap представлява масив от обекти от тип Entry<K,V>, всеки елемент на който се казва bucket, а самият масив – table.
• Всеки bucket съхранява първият елемент на свързан списък от тип Entry
• Entry е вътрешния клас, в чиито обекти HashMap съхранява двойките <K,V>.
• Важно е да се предефинират и двата метода hashCode и equals, тъй като:
o Ако два ключа имат един и същи хеш код, но са различни( не са equals), то се запазват в един bucket в свързан списък.
o Ако два ключа имат един и същи хеш код и са еднакви (equals), то следва че се получава дублиране на ключове и последния вкаран замества първия такъв.
Какво ново в Java 8?
За оптимизация на HashMap в Java 8 са направени някои промени във вътрешната му структура. В предната статия споменахме, че структурата си има два много важни параметъра, които определят производителността и – initial capacity и load factor. Според документацията на HashMap, стойността на loadFactor по подразбиране 0,75 осигурява много добър баланс между време и памет. Не е много разумно тя да бъде променяна. Ако умножим loadFactor*capacity ще получим един друг параметър на HashMap – threshold – това е размерът, който, когато HashMap-ът достигне, автоматично ще се разшири. Тоест, ако вземем стойността на капацитетът по подразбиране ще получим 0,75*16 = 12. Логично е, когато стигне 12 елемента, hashMap-ът да се разшири.
В Java 8, се въвеждат някои нови полета на класа HashMap. Сред тях е и TREEIFY_THRESHOLD (по подразбиране е 8). Когато извикваме метод put(K,V) той вътрешно извиква метод putVal, който работи по същия начин като в Java 7 – създава свързан списък при възникване на колизия. След това в конкретния bucket проверява дали броят на елементите в свързания списък е по –голям от TREEIFY_THRESHOLD. Ако това е така, то се вика методът treeifyBin()(само в Java 8), който преобразува свързания списък в бинарно дърво. Използва друг статичен вложен член клас- TreeNode (подобно на Entry<K,V>), който реализира бинарното дърво. Какво печелим? Докато свързаният списък ни дава сложност О(n), то балансираното бинарно дърво ни дава сложност О(logn). Ако в така преструктурирания bucket изтрием един елемент, нищо няма да се промени – ще се запази структурата. Ако обаче броят на възлите в това дърво достигне минималния праг UNTREEIFY_THRESHOLD (по подразбиране 6), то се вика метод untreeify(), който трансформира дървото в свързан списък.
Явор Томов, Даниел Джолев