Хеш функцията в математиката е такава функция, която служи за промяна на гъстотата на дадено множество – разширяване или стестняване на множеството. Казано по-друг начин, ако на входа на хеш функцията подаваме различни по дължина множества, на изхода ще получаваме низове, който ще бъде с фиксирана дължина и ще бъдат различни за различните множества на входа.
Тоест на всеки текст с различна дължина, подаден на входа на хеш функция, съответства изходен код (хеш) с фиксирана дължина. Важна особеност на хеш функцията е, че тя е еднопосочна – тоест по даден хеш не бихме могли да възстановим входните данни, преди хеширането. Като приложение – хеш функциите намират широко приложение в криптографията – за удостоверяване на източници, за легитимност и цялостност (интегритет) на данните. В програмирането често се използват за сравнение на данни , особено за комплексни данни(обекти), които по-трудно биха могли да бъдат сравнявани. Има вероятност при различни входни данни понякога да се получи една и съща стойност на хеша – това се нарича колизия.
Всеки обект в Java си има свой хеш код, връщан от hashCode() и метод equals(). Ако работим с примитивни данни, сравнението е елементарно – така например лесно сравняваме две числа от тип int. С обектите, обаче нещата не стоят точно така. Тук се намесва хеш функцията, която за всеки различен обект връща цяло число- неговата хеш стойност или метод hashCode(). Казва се че два обекта вероятно са еднакви, ако имат един и същ хеш код. Например:
public class Person {
private String firstName;
private String familyName;
private int years;
public Person(String firstName, String familyName, int years) {
this.firstName = firstName;
this.familyName = familyName;
this.years = years;
}
public String getFirstName() {
return firstName;
}
public void setFirstName(String firstName) {
this.firstName = firstName;
}
public String getFamilyName() {
return familyName;
}
public void setFamilyName(String familyName) {
this.familyName = familyName;
}
public int getYears() {
return years;
}
public void setYears(int years) {
this.years = years;
}
}
Ако създадем два обекта от тип Person и им сравним хеш кодовете ще видим следното:
public static void main(String[] args) {
Person p1 = new Person("Ivan", "Ivanov", 25);
Person p2 = new Person("Ivan", "Ivanov", 25);
System.out.println("The p1 hashCode is: " + p1.hashCode());
System.out.println("The p1 hashCode is: " + p2.hashCode());
}
Резултат:
The p1 hashCode is: 5282812
The p1 hashCode is: 3198717
Това е така, тъй като в класа Person не е предефиниран методът hashCode() и той работи с имплементацията си по подразбиране, наследена от клас Object- според документацията на Oracle, hashCode се изчислява като се превърне вътрешния адрес на обекта в цяло число. В момента ние сме създали два обекта, които имат различен адрес (създадени са с new). Така става ясна причината, поради която се чудите, защо въпреки че обектите имат едни и същи стойности за член променливите си, все пак им се изчисли различен хеш код. Сега ще създадем p2 като го инициализираме със стойността на p1, тоест и двата обекта ще имат един и същи вътрешен адрес. Би трябвало да ни изчисли един и същи хеш код и за двата:
public static void main(String[] args) {
Person p1 = new Person("Ivan", "Ivanov", 25);
Person p2 = p1;
System.out.println("The p1 hashCode is: " + p1.hashCode());
System.out.println("The p1 hashCode is: " + p2.hashCode());
}
Резултат:
The p1 hashCode is: 5282812
The p1 hashCode is: 5282812
Както виждате, имплементацията на метода hashCode по подразбиране не върши особена работа, за да я ползваме за User defined класове. Трябва ние сами да предефинираме метода hashCode за нашия клас, за да му зададем конкретна логика как да изчислява хеш кода за създадените по-късно обекти. Важно е да се спомене, че много класове в Java API-то са с предефиниран метод hashCode()- например класът String. Нека видим:
public static void main(String[] args) {
String s1 = new String("ivan");
String s2 = new String("ivan");
System.out.println("The s1 hashCode is: " + s1.hashCode());
System.out.println("The s1 hashCode is: " + s2.hashCode());
}
Резултат:
The s1 hashCode is: 3244570
The s1 hashCode is: 3244570
Виждате, че въпреки че са създадени с new и са два различни обекта с различни адреси, то методът hashCode() връща едни и същи стойности и за двата.
Нека сега да предефинираме метода hashCode() за нашия клас Person. За целта ще използваме абсолютно всички член променливи на класа – за String ще ползваме неговия хеш код, за int променливата – ще участва също в крайния код. Добавяме следния метод в класа Person:
public class Person{
.......
@Override
public int hashCode() {
int result = 240;
result = result + this.firstName.hashCode();
result = result + this.familyName.hashCode();
result = result * this.years;
return result;
}
}
Нека сега да тестваме дали работи нашият предефиниран hashCode():
public static void main(String[] args) {
Person p1 = new Person("Ivan", "Ivanov", 25);
Person p2 = new Person("Ivan", "Ivanov", 25);
System.out.println("The p1 hashCode is: " + p1.hashCode());
System.out.println("The p1 hashCode is: " + p2.hashCode());
}
Резултат:
The p1 hashCode is: -729724973
The p1 hashCode is: -729724973
Така вече може да използваме хеш кода за да сравняваме обектите ни от тип Person.
Когато говорим за обекти е по-трудно да се каже кога един обект е „равен“ на друг. В този случай е добре да има обща логика за всички обекти от даден тип, по която да може да се каже кога един обект е същият като друг – обикновено имплементираме метод equals(). Този метод също се наследява от базовия клас Object, както и методът hashCode(). Често се случва тези методи да се предефинират в зависимост от създадените нови класове, за да може по-конкретно да се каже кога два обекта от тип дадения клас са еднакви. Има два основни контракта между тези два метода :
1.Ако два обекта са еднакви (equal), то те задължително трябва да имат едни и същи хеш кодове.
2.Ако два обекта имат едни и същи хеш кодове, те могат, а могат и да не бъдат еднакви – това е в зависимост от устойчивостта на хеш функцията на колизии.
Затова запомнете, че ако предефинирате единия, ще трябва да предефинирате и другия метод. Нека извикаме метода и да сравним двата обекта, без да сме го предефинирали:
public static void main(String[] args) {
Person p1 = new Person("Ivan", "Ivanov", 25);
Person p2 = new Person("Ivan", "Ivanov", 25);
System.out.println("are they equal? " + p1.equals(p2));
}
Резултат:
are they equal? false
Резултатът е ясен – тъй като не сме предефинирали метода в нашия клас Person, то се изпълнява имплементацията му по подразбиране от класа Object, която е:
public boolean equals(Object obj) {
return (this == obj);
}
Тоест, по подразбиране методът ще връща true, само ако референциите са едни и същи. Нека тестваме, като инициализираме p1 с p2, така че да сочат към едно и също място.
public static void main(String[] args) {
Person p1 = new Person("Ivan", "Ivanov", 25);
Person p2 = p1;
System.out.println("are they equal? " + p1.equals(p2));
}
Резултат:
are they equal? true
Как да се знае кога два наши обекта са еднакви (equals), като това зависи много от специфичните полета на различните класове? Ще трябва да предефинираме метода equals() за всеки клас, според ситуацията. Например кога два обекта от тип Person са еднакви- решаваме, че, ако имената им и годините им са еднакви, то те са еднакви, или пък само ако имената им са еднакви- въпрос на решение.
Добавяме следния метод в класа Person:
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Person other = (Person) obj;
if (familyName == null) {
if (other.familyName != null)
return false;
} else if (!familyName.equals(other.familyName))
return false;
if (firstName == null) {
if (other.firstName != null)
return false;
} else if (!firstName.equals(other.firstName))
return false;
if (years != other.years)
return false;
return true;
}
Тук сме обхванали всички възможни – двата обекта да са едни и същи референции, подадения да е празен, двата да са от различни класове, конкретните полета да им съвпадат.
Тестваме:
public static void main(String[] args) {
Person p1 = new Person("Ivan", "Ivanov", 25);
Person p2 = new Person("Ivan", "Ivanov", 25);
System.out.println("are they equal? " + p1.equals(p2));
}
Резултат:
are they equal? true
Така вече можем да кажем за всеки два обекта от този тип дали са еднакви (equals).
Защо обаче се налага да се знае дали два обекта са еднакви? В програмирането често се среща понятието асоциативен масив- това е такъв масив, който подобно на традиционния пази стойности, но всяка стойност идентифицира не по индекс, а по обект. Защо обект- защото String, например, който често се ползва за критерий за търсене е обект. Нека си представим масива от Person обекти.
Искаме да търсим дали в него има човек с име Marry. Знаем, че достъпът до елементите по индекс е най-бърз. Как бихме могли да „достъпим“ елемента по друг критерий(в случая firstName). Много по-лесно щеше да е, ако можехме да търсим и да достъпим елемента по String, например:
Е, не се разочаровайте, но Java не предлага в чист вид асоциативни масиви, но пък предлага структура, която действа по-подобен начин. HashMap – структура, която ще пази елементите си с какъвто обект ние си изберем като индекс. За да може да търси и достъпва елементите по такъв „сложен“ индекс, ще трябва да има много ясен критерий, когато вкарва елементи, за да знае точно къде да ги постави. Ще трябва после да се търси по този обект. А сега сигурно си спомнихте, че тръгнахме от момента, в който щяхме чрез hashCode() и equals() да дефинираме правила за сравнение и за идентифициране на обекти. За да сме сигурни, че два обекта са еднакви, можем с голяма степен на достоверност да ползваме хеширане (след хеш се връща като резултат число) и после да сравним двете числа, получени след хеширане- числата знаем как да сравняваме. Е, когато вкарваме нашите обекти от тип Person в структурата HashMap, заедно с всеки обект ще подаваме и „индекс“(отново обект, в случая е String), по който да бъде открит той по-късно. Този индекс ще наричаме ключ(key), а основния обект, който искаме да съхраняваме – стойност (value). При търсене в последствие, ще се налага да подаваме този ключ и по него ще ни бъде върнат обекта, който търсим. За целта подадения ключ при търсене ще трябва да се сравнява с ключа, който сме въвеждали при вмъкване на данните. Структурата ще трябва да обхожда елементите си и да сравнява (equals()) ключове. За да бъде възможно това, разяснихме какво трябва да се направи, за да можем да сравняваме всякакъв тип данни.
Както стана ясно по-горе Java разполага с имплементация за посочената цел – HashMap<K,V>. Класът имплементира остарялата идея за речник – структура, в която се пазят двойки ключове(K – key)и стойности(V- value), напълно аналогично на истински речник- дума: превод. Ако искаш да потърсиш превода на думата tree , то ще трябва да потърсим по ключ стринга „tree“ и да ни върне стойността на превода – стринга „дърво“. Такъв HashMap ще бъде създаден със следната декларация:
HashMap<String,String> dictionary;
Ако се върнем на нашия пример, от който тръгнахме по-горе, ще трябва да създадем:
HashMap<String,Person> mapOfPeople = new HashMap<String,Person>();
За да си добавим нов човек в map-а, ще използваме метод put(k,v):
public static void main(String[] args) {
HashMap<String,Person> mapOfPeople = new HashMap<String,Person>();
Person p1 = new Person("Ivan", "Ivanov", 25);
Person p2 = new Person("George", "Ivanov", 25);
mapOfPeople.put("ivan", p1);
mapOfPeople.put("george", p2);
Person foundPerson = mapOfPeople.get("ivan");
}
За да потърсим после човек по критерий име, ще използваме метод get(k), който по подаден ключ име, ще върне човек, ако го намери разбира се.
Нека променим леко опитната постановка на задачата. Ще заменим двете имена на човека вместо стрингове да бъдат един цял обект – Name. Ще предефинираме конструктора на Person да приема като аргумент Name и years.
public class Name {
private String firstName;
private String seconName;
private String lastName;
public Name(String firstName, String seconName, String lastName) {
this.firstName = firstName;
this.seconName = seconName;
this.lastName = lastName;
}
public String getFirstName() {
return firstName;
}
public void setFirstName(String firstName) {
this.firstName = firstName;
}
public String getSeconName() {
return seconName;
}
public void setSeconName(String seconName) {
this.seconName = seconName;
}
public String getLastName() {
return lastName;
}
public void setLastName(String lastName) {
this.lastName = lastName;
}
}
public class Person {
private Name name;
private int years;
public Person(Name name, int years) {
this.setName(name);
this.years = years;
}
public int getYears() {
return years;
}
public void setYears(int years) {
this.years = years;
}
public Name getName() {
return name;
}
public void setName(Name name) {
this.name = name;
}
}
Какво ще целим при теста сега? Ще създадем мап от Person с ключ от тип обекта Name. Ще създадем и ще вмъкнем два обекта от тип Person в мап-а заедно с техните Name-ключове. После ще се опитаме да потърсим Person по ключ обект от тип Namе.
public static void main(String[] args) {
Map<Name, Person> mapOfPeople = new HashMap<Name, Person>();
Name name1 = new Name("Ivan", "Ivanov", "Ivanov");
Person p1 = new Person(name1, 25);
Name name2 = new Name("Georgi", "Georgiev", "Georgiev");
Person p2 = new Person(name2, 25);
mapOfPeople.put(name1, p1);
mapOfPeople.put(name2, p2);
Person somePerson = mapOfPeople
.get(new Name("Ivan", "Ivanov", "Ivanov"));
if (somePerson != null) {
System.out.println(somePerson.getName().getFirstName());
} else {
System.out.println("No such person in this Map!");
}
}
Резултат:
No such person in this Map!
Защо се получи така? Въпреки че търсим по ключ име, с което сме сигурни че сме вкарали такъв човек, резултатът е, че такъв не е намерен. В горния случай потърсихме по ключ String – той обаче си има предефиниран метод hashCode(), както и метод equals(). Сега, обаче, използваме като ключ обект, на който не сме предефинирали нито equals, нито hashCode(). Следователно те работят с имплементациите си по подразбиране от класа Object. Вкарвайки първия човек с ключ Name name1 = new …, това означава, че при записа се използва неговия hashCode(), който в случая беше вътрешния му адрес. При търсене по ключ new Name(“Ivan”, “Ivanov”, “Ivanov”), хешът на този обект е неговият вътрешен адрес, който тъй като е нов обект, е съвесем различен от този, който има name1. От тук следва, че ако не предефинираме методите hashCode и equals, единственият вариант за да открием човек в мап-а, е да търсим със същата референция от тип Name, която сме ползвали, когато сме го вкарвали. Например:
public static void main(String[] args) {
Map<Name, Person> mapOfPeople = new HashMap<Name, Person>();
Name name1 = new Name("Ivan", "Ivanov", "Ivanov");
Person p1 = new Person(name1, 25);
Name name2 = new Name("Georgi", "Georgiev", "Georgiev");
Person p2 = new Person(name2, 25);
mapOfPeople.put(name1, p1);
mapOfPeople.put(name2, p2);
Person somePerson = mapOfPeople
.get(name1);
if (somePerson != null) {
System.out.println(somePerson.getName().getFirstName());
} else {
System.out.println("No such person in this Map!");
}
}
Резултат:
Ivan
Това, естествено не е практично. Да си представим, че някой пълни мап-а с обекти от тип Person и ни го дава да работим с него – тогава как ще търсим по Name, след като не разполагаме със същите референции, с които той е вкарвал Person-и в мап-а.
Решението е да си предефинираме методите hashCode() и equals() в обекта, който ще ползваме като ключ – в случая Name. Ще ги добавим в класа Name:
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());
result = prime * result
+ ((seconName == null) ? 0 : seconName.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Name other = (Name) obj;
if (firstName == null) {
if (other.firstName != null)
return false;
} else if (!firstName.equals(other.firstName))
return false;
if (lastName == null) {
if (other.lastName != null)
return false;
} else if (!lastName.equals(other.lastName))
return false;
if (seconName == null) {
if (other.seconName != null)
return false;
} else if (!seconName.equals(other.seconName))
return false;
return true;
}
}
Сега тестваме като търсим по нов обект new Name(“Ivan”, “Ivanov”, “Ivanov”).
public static void main(String[] args) {
Map<Name, Person> mapOfPeople = new HashMap<Name, Person>();
Name name1 = new Name("Ivan", "Ivanov", "Ivanov");
Person p1 = new Person(name1, 25);
Name name2 = new Name("Georgi", "Georgiev", "Georgiev");
Person p2 = new Person(name2, 25);
mapOfPeople.put(name1, p1);
mapOfPeople.put(name2, p2);
Person somePerson = mapOfPeople
.get(new Name("Ivan", "Ivanov", "Ivanov"));
if (somePerson != null) {
System.out.println(somePerson.getName().getFirstName());
} else {
System.out.println("No such person in this Map!");
}
}
Резултат:
Ivan
Нека да разгледаме по-подробно интерфейса Map и някои от неговите имплементации. Основните методи, с които разполага интерфейса Map са:
• V put(K key, V value) – вкарва обект V по подаден ключ K и връща обекта, ако е успешно записан.
• V get(Object key) – Връща обекта, по подаден ключ за търсене.
• V remove(Object key) – Премахва обекта и го връща като резултат по подаден ключ.
• boolean containsKey(Object key) – Връща Boolean, като проверява дали подадения ключ се съдържа.
• boolean containsValue(Object value) – Връща Boolean, като проверява дали подадеата стойност се съдържа.
Важно нещо, което трябва да запомните, е че когато добавите елемент чрез метода put(K,V), ако подадете един и същи ключ два пъти, то новата стойност ще замени старата и старата ще бъде изгубена. Друга съществена особеност е, че когато добавяте елементи последователно, няма никаква гаранция, че те ще се запазват в същата последователност. Хубавото е, че позволява да се вмъкнат двойки със стойности на (null,null).
Може би най-голямото предимство на структурата е, че гарантира константно време за достъп до елементите, записани в нея. Това и качество я прави изключително подходяща за случаи, при които се налага бърз достъп и често търсене. Важно е да се каже, че структурата си има и два много важни параметъра – load factor и initial capacity. Initial capacity определя размера на структурата при създаването и, а loadFactor e число межу 0 и 1, което показва до каква степен е разрешено да се запълва структурата, преди да си увеличи капацитета автоматично. По подразбиране Initial capacity е 16, а loadFactor е 0.75. Тези два параметъра могат да се променят от програмиста, но трябва да се внимава, защото много силно влияят на производителността.
Тъй като вътрешната организация на HashMap не е толкова проста – колекционира всички двойки като обекти от тип Entry, то обхождането на тази колекция е малко по-особено. Всъщност Entry е вложен клас в класа Map, затова се достъпва с Map.Entry. Ще трябва да си декларираме Iterator, който да итерира множеството(Set) от всички Entry-та (това са всички съществуващи двойки). И така всяко едно Entry си има ключ и стойност, съответно с getKey() и getValue() ще ги достъпваме.
public static void main(String[] args) {
Map<Name, Person> mapOfPeople = new HashMap<Name, Person>();
Name name1 = new Name("Ivan", "Ivanov", "Ivanov");
Person p1 = new Person(name1, 25);
Name name2 = new Name("Georgi", "Georgiev", "Georgiev");
Person p2 = new Person(name2, 25);
mapOfPeople.put(name1, p1);
mapOfPeople.put(name2, p2);
Iterator it = mapOfPeople.entrySet().iterator();//Ще итерира около множеството от Entry-та.
while (it.hasNext()) { //докато все още има Entry
Map.Entry<Name, Person> pair = (Map.Entry) it.next(); //от итератора чрез next() взимаме текущата двойка.
System.out.println("The key is: " + pair.getKey().getFirstName() //на текущата двойка може да и вземем ключа или стойността.
+ " " + pair.getKey().getLastName() + " The value is: "
+ pair.getValue().getName().getFirstName()
+" "
+ pair.getValue().getYears());
}
}
Резултат:
The key is: Ivan Ivanov The value is: Ivan 25
The key is: Georgi Georgiev The value is: Georgi 25
Друг вариант за обхождане на Map е чрез for each. За нашия пример:
for (Map.Entry<Name, Person> me : mapOfPeople.entrySet()) {
System.out.println("Key: "+me.getKey().getFirstName() + " & Value: " + me.getValue().getName().getFirstName() + " " + me.getValue().getYears());
}
Друга известна имплементация на интерфейса Map е HashTable. Всъщност няма чак толкова разлики между двете, с изключението, че HashTable представлява синхронизирана имплементация – предотвратява опастността от конкурентен достъп. Какво означава това? Означава, че HashTable може да бъде достъпвана само от една нишка в един момент – тоест никоя друга не може да работи с нея, докато при HashMap не е така. Когато няколко нишки се опитват да променят HashTable, то първата достъпила я, я заключва и другите остават да чакат да бъде освободена.
Също така е добре да знаете, че LinkedHashMap като имплементация на Map, поддържа двойките си по реда на постъпването им в нея. TreeMap пък поддържа двойките си сортирани по т.нар. “natural order” на ключовете им.
Явор Томов, Даниел Джолев