* Речници: хеш таблици и червено-черни дървета
Публикувано на 15 ноември 2015 в раздел ПИК3 Java.
Map е един от често използваните интерфейси в Java. Чрез него се реализират т.нар. "речници". В речниците имаме записани двойки от стойности (ключ, стойност). Целта е да успяваме много бързо да намираме стойността, търсейки по чрез нейния ключ. Много често по интервюта за работа се задават въпроси свързани с класове, които го имплементират.
1. Интерфейсът Map
Преди да разгледаме конкретните реализации, трябва да се запознаем с основния интерфейс на речниците. Той работи с генерични типове и приема два параметъра: Map<Key,Value>:
- Key - ключ, по който ще се търси;
- Value - стойност, която ще бъде търсена.
Защо такава структура ще превеждаме като "речник"? Много е сходно с речниците по чужди езици, които познаваме от деца - когато търсим превода на някоя дума (самата дума е key) и я намерим в речника (нашата структура от данни Map), ние прочитаме същественото за нея описание (търсеното от нас value). Всъщност в миналото в Java се е използвал за тази цел един абстрактен клас Dictionary (буквално речник), но впоследствие е бил заменен от интерфейс Map.
Поглеждайки по-общо можем да установим, че речниците по чужди езици могат да бъдат разглеждани и използвани по различен начин от класическия (съпоставяне на дума/key - превод/value). Сами по себе си те могат да бъдат разглеждани като просто колекция от думи (тоест пропускайки стойностите, Map може да бъде разгледан като множество от ключове). Аналогично Map може да бъде разглеждан и само като колекция от стойности.
Интерфейс Map има множество методи. В примерите в курса ще използваме само малка част от тях (основно get, put и remove), но тук ще си позволим да ги изброим всички (от документацията на Java 8):
- void clear() - изчиства речника;
- V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) - проверява дали съществува стар запис за подадения ключ, след което:
- независимо дали има или няма съществуващ запис, ако BiFunction върне резултат по подадения ключ (key), резултата от BiFunction ще бъде записан в речника с подадения key;
- ако има съществуващ запис и BiFunction не върне резултат по този ключ, записа по подадения key ще бъде изтрит от речника;
- ако няма съществуващ запис и BiFunction не върне резултат по този ключ, метода ще върне null.Пример (от официалната документация): имаме речник с множество от текстови низове. Имаме да добавим нов низ по следните условия - ако има съществуващ запис за този низ, той да се конкатенира в края на съществуващия, а ако няма съществуващ запис, низа просто да се добави. Чрез ламбда израз това се реализира по следния начин:
map.compute(key, (k, v) -> (v == null) ? msg : v.concat(msg));
- V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction) - добавя в речника резултата от подадената функция само ако няма съществуващ запис за ключа. Ако самата функция върне null, computeIfAbsent не добавя нищо, а връща null;
- V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) - ако има съществуващ запис и преизчисляващата функция върне резултат, този резултат се записва в речника, а ако преизчисляващата функция не върне резултат (т.е. върне null), елемента от речника се изтрива. Ако няма съществуващ запис, computeIfPresent ще върне null;
- boolean containsKey(Object key) - проверява дали речника съдържа подадения ключ;
- boolean containsValue(Object value) - проверява дали речника съдържа подадената стойност;
- Set<Map.Entry<K,V>> entrySet() - връща множество кореспондиращо на стойностите в подадения речник. Ще покажем как се използва по-долу в примери с HashMap и TreeMap;
- boolean equals(Object o) - проверява дали подадения обект е същия речник както текущия
- void forEach(BiConsumer<? super K,? super V> action) - извършва подадената Consumer операция за всеки елемент от речника;
- V get(Object key) - връща стойността по подадения ключ. Ако няма такъв ключ в речника, връща null;
- V getOrDefault(Object key, V defaultValue) - връща стойността по подадения ключ. Ако няма такъв ключ в речника, връща defaultValue;
- int hashCode() - хеш кода за самия обект речник;
- boolean isEmpty() - връща true или false в зависимост от това дали има записи в речника;
- Set keySet() - връща множество кореспондиращо на ключовете в подадения речник. Ще покажем как се използва по-долу в примера с TreeMap;
- V merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction) - ако за подадения ключ няма стойност в речника или има съответстваща null стойност, записва в този ключ резултата от remappingFunction. Ако за съществуващия ключ има стойност в речника, тази стойност се подменя с резултата от remappingFunction (ако този резултат е различен от null) или записа се изтрива (ако резултата от функцията е null). Този метод е опростен вариант на compute. Примера с добавяне или конкатениране на низ от по-горе може да бъде реализиран чрез merge по следния, доста по-елегантен начин:
map.merge(key, msg, String::concat); - V put(K key, V value) - добавя запис (комбинация от key-value) в речника. Ако запис с такъв key вече съществува, стария value се заменя с новия;
- void putAll(Map<? extends K,? extends V> m) - добавя записите от подадения речник в текущия;
- V putIfAbsent(K key, V value) - добавя подадения запис само ако няма дублиращ се такъв или има, но е със съответстваща стойност null. Връщаната стойност от метода е записаната стойност или null, ако вече е имало такъв запис;
- V remove(Object key) - изтрива ключа и съответстващата му стойност от речника. Връща стойността, която е била изтрита или null ако не е имало такъв запис;
- boolean remove(Object key, Object value) - изтрива запис само ако има едновременно подадения ключ и съответстващата му стойност е идентична с подадената;
- V replace(K key, V value) - заменя стойноста на съществуващия запис в подадения key с подаденото value. Няма да запише нищо и ще върне null ако в речника няма такъв запис;
- boolean replace(K key, V oldValue, V newValue) - заменя стара стойност с нова само и единствено ако старата стойност е вече записана на съответния ключ;
- void replaceAll(BiFunction<? super K,? super V,? extends V> function) - заменя стойността на всеки елемент от хеш таблицата с резултата от подадената функция;
- int size() - връща броя записи в речника;
- Collection values() - връща списък със стойностите записани в речника.
В Java има четири класа, които са употребявани най-често като имплементации на Map. Това са HashMap, ConcurrentHashMap, LinkedHashMap и TreeMap. Вероятно най-честно използванитe от тях са HashMap и ConcurrentHashMap.
2. Клас HashMap
HashMap е имплементация на речник като хеш таблица. Целта е да записваме обекти по подаден ключ и да ги достъпваме по възможност с константна сложност o(1) или (в най-лошия случай) с линейна o(n). Вие вече познавате една структура от данни, която има константна сложност за достъп до елементите ѝ - това е масива. Може да си представите обикновения масив като речник, в който ключовете са индексите на елементите, а стойностите са конкретните записи, а самите записи са подредени последователно в паметта. При хеш таблиците нещата не са много по-различни - те могат да бъдат разгледани като "асоциативни масиви", т.е. такива, при които достъпваме елементите вместо по индекс, по някаква дума (в случая още по-абстрактно - по какъвто и да е обект, т.е. ключ).
Конкретно при реализацията на HashMap в Java нещата са по-сложни, защото е позволено в един и същи ключ да записваме множество стойности. Връщайки се обратно на аналогията с масивите, можем да си представим един HashMap като асоциативен масив от списъци с елементи. Когато два различни записа съответстват на един и същи елемент в асоциативния масив, те се подреждат в списък. Даваме аналогията между хеш таблица и масив неслучайно. Всъщност HashMap вътрешно се реализира именно чрез масив! Изключително важен за реализацията на речник с HashMap е метод hashCode() на ключа. Именно резултата от метод hashCode() се използва, за да се изчисли индекса на масива, в който е записана търсената стойност.
Ето основните стъпки, по които се изпълнява метод get(key):
a) Изчислява се резултата от key.hashCode();
б) Този резултат се използва от една вътрешна (private) хешираща функция, която по подадения ѝ хеш код изчислява и връща индекс от масива. Една елементарна такава хеш функция например би била key.hashCode()%array.length. Действително тази функция винаги ще връща число от 0 до array.length-1, т.е. именно индекс в границите на масива, в който ще се записва;
в) След като знаем индекса на масива, get го достъпва. Този елемент е списък. Списъкът се обхожда и за всеки негов елемент el се извиква метод equals с параметър key (т.е. el.equals(key)). Ако някой от тях върне true, това е търсения запис и get го връща. Ако нито едно извикване на equals на елемент от списъка не върне true, метод get връща false.
Е, вече имате понятие за най-основните действия, които се извършват в един HashMap. Например веднага можете да си представите и последователността от действия на метод put:
а) Изчислява се резултата от key.hashCode();
б) Чрез хеширащата функция се изчислява индекса на масива, в който елемента трябва да бъде записан;
в) Обхожда се списъка и се търси дали вече има съществуващ key, чийто метод equals ще върне true с подадения, след което:
- ако има съществуващ ключ, метод put заменя старото value с новото;
- ако няма съществуващ ключ, метод put добавя новия елемент в края на списъка.
Нека след всичко изписано дотук дадем и нашия първи практически пример. Ще си дефинираме едно множество от класове - Person описващ човек с име и години, учебен предмет Subject съдържащ в себе си преподавател (Person):
class Person{
String name;
int age;
Person(String name, int age){
this.name = name;
this.age = age;
}
public int hashCode(){
int result = 17;
result = result*37 + this.name.hashCode();
result = result*37 + this.age;
return result;
}
}
class Subject{
String name;
Person professor;
Subject(String name, Person professor){
this.name = name;
this.professor = professor;
}
public int hashCode(){
int result = 17;
result = result*37 + this.name.hashCode();
result = result*37 + this.professor.hashCode();
return result;
}
}
Сега искаме да направим клас Student, който наследява Person и добавя факултетен номер и оценка по даден учебен предмет. Оценките ще бъдат от стандартните (StandartGrade) по шестобалната система, а комбинацията Предмет-Оценка ще бъде реализиран чрез HashMap. Специално обръщаме внимание на StandartGrade, тъй като е реализиран не като клас, а чрез enum. Ще поставим допълнителни коментари в кода за разяснение.
enum StandartGrade{
// Това са възможните записи на Enum полето
// те ще са SLAB, SREDEN, DOBAR, MNOGO_DOBAR и OTLICHEN
// а стойностите в скобите се предават автоматично към
// конструктора на enum
SLAB(2), SREDEN(3), DOBAR(4), MNOGO_DOBAR(5), OTLICHEN(6);
// в тази променлива ще записваме числовата стойност
// която е подадена в скобите на записите
private int grade;
// записваме числовата стойност чрез private конструктор
private StandartGrade(int grade){
this.grade = grade;
}
// метод, който връща числовата стойност на даден запис
int toInt(){
return this.grade;
}
};
class Student extends Person{
int facultyId;
private HashMap<Subject, StandartGrade> grades;
Student(String name, int age, int facultyId){
super(name, age);
this.facultyId = facultyId;
this.grades = new HashMap<Subject, StandartGrade>(10);
}
int getGrade(Subject subject){
StandartGrade result = this.grades.get(subject);
if(result!=null) return result.toInt();
else return StandartGrade.SLAB.toInt();
}
void setGrade(Subject subject, StandartGrade grade){
this.grades.put(subject, grade);
}
void printGrade(Subject subject){
System.out.println(this.name+
" има "+
this.getGrade(subject)+
" по предмета "+
subject.name);
}
}
В Student не сме предефинирали метод hashCode, но ние няма да използваме този клас в HashMap, затова ще го пропуснем. Добра практика все пак е всеки клас да си има свой hashCode.
Нека сега демонстрираме функционалността на програмата. Ще създадем списък с предмети, студенти и оценки, които тези студенти имат по тези предмети:
import java.util.HashMap;
public class HashMapExample{
public static void main(String[] args){
Person philip = new Person("Филип Петров", 32);
Subject pik3 = new Subject("ПИК3", philip);
Subject bd = new Subject("Бази Данни", philip);
Student ivan = new Student("Иван Иванов", 20, 123456);
ivan.setGrade(pik3, StandartGrade.MNOGO_DOBAR);
// ще отпечата записаната оценка
ivan.printGrade(pik3);
// ivan няма оценка по bd - отпечатва 2
ivan.printGrade(bd);
// ivan си е повишил успеха
ivan.setGrade(pik3, StandartGrade.OTLICHEN);
ivan.printGrade(pik3);
}
}
При реализацията на HashMap е изключително важно да имате добър метод hashCode за ключовете, който гарантира различни кодове при различни ключове. Ако не направите това, ще има много колизии и сложността в общия случай ще започва да става линейна, вместо константна.
Освен това е важно да дефинирате в самото начало адекватна първоначална големина на хеш таблицата. Нещо, което понякога не се знае от разработчиците, е че HashMap е реализирано чрез динамични масиви, тоест подобно на ArrayList. Чрез втори параметър в неговия конструктор вие може да подавате т.нар. "коефициент на запълване" (loadFactor), който по подразбиране е 0.75. Това означава, че ако повече от 75% от елементите на масива са заети (припомняме, че самите тези елементи са списъци в случай на колизия), то речника автоматично ще бъде разширен и ще приеме по-голям капацитет. Това обаче не е толкова проста операция, както е в обикновения ArrayList - разширяването на речника включва преизчисляване на всички хеш функции на всички ключове и пренареждане на елементите в речника по нов начин! Затова е много важно предварително да планирате очакваната големина на речниците, които създавате. Автоматичното разширяване позволява да се намаляват колизиите и бързината на работа с HashMap винаги да е близо до константна - o(1).
Една честа задача е да се обходи хеш таблица и да се изведат всички нейни елементи. Това може да се направи чрез итератор, но в по-новите версии на Java се използва специален клас Map.Entry, който се генерира от метод entrySet() на речника. Следният пример демонстрира това:
import java.util.*;
public class Test{
public static void main(String[] args){
HashMap<String, Integer> hm = new HashMap<>();
hm.put("aaa", 5);
hm.put("aaa", 6);
hm.put("bbb", 6);
for(Map.Entry<String,Integer> es : hm.entrySet()){
System.out.println(es.getKey()+" "+es.getValue());
}
}
}
3. Клас ConcurrentHashMap и HashTable
HashMap не е "thread safe", т.е. не е синхронизиран за работа като споделен ресурс в многонишкова среда. Затова в Java има добавени три основни начина за автоматично избягване на този проблем. Първите два са чрез два готови класа:
- ConcurrentHashMap - намира се в java.util.concurrent и е препоръчителния начин за справяне с проблема. При него има значителна оптимизация на ниско ниво и се позволява повече от една нишка да достъпва ресурса едновременно, като операциите за промяна продължават да са атомарни;
- HashTable - синхронизацията е от доста примитивно ниво - практически само една нишка може да работи с таблицата в даден момент от време.
HashTable е просто остаряла концепция и не се препоръчва нейното използване. При това той имплементира остарелия клас Dictionary, а не интерфейс Map. Не го използвайте.
Употребата на ConcurrentHashMap е аналогична на тази на HashMap. Няма да даваме пример.
4. Collections.synchronizedMap
Третият начин за реализиране на речник в многонишкова среда е чрез синхронизирането на съществуващ HashMap чрез използването на Collections.syncronizedMap метода:
Map<K,V> = Collections.synchronizedMap(new HashMap<K,V>());
Така създаден списъка работи с интерфейс Map, но осигурява синхронизация подобно на HashTable - когато дадена нишка променя таблицата, тя заключва цялата таблица. Затова при почти всички случаи бихме посъветвали да използвате ConcurrentHashMap пред Collections.syncronizedMap. Правим това обаче с една важна уговорка - това важи само ако ще използвате HashMap. Collections.syncronizedMap позволява да бъде създадена синхронизиран речник и по други структури - например TreeMap и LinkedHashMap - при които подредбата на елементите трябва да се съхранява (ще ги опишем по-долу). В този случай Collections.syncronizedMap няма алтернатива.
5. Клас LinkedHashMap
HashMap не запазва реда на въведените елементи. Тоест ако въведете няколко елемента, впоследствие не можете да кажете кой е бил въведен първи, втори и т.н. Това пречи в случаите, когато искате да реализирате опашка или стек чрез хеш таблица (рядък, но не напълно непрактичен случай). Тук на помощ идва LinkedHashMap - този клас наследява класа HashMap и вътрешно пази допълнителен свързан списък (LinkedList), чрез който пази реда на въвеждане. От там насетне основната разлика между двата класа идва когато използвате Iterator по речниците - при HashMap итератора ще обхожда самия масив (и списъка на всеки въведен елемент в него), докато при LinkedHashMap ще се обхожда свързания списък. Няма друга съществена разлика - класовете се използват по аналогичен начин.
6. Клас TreeMap
TreeMap се различава съществено от речниците реализирани с хеш таблици. Този клас имплементира структура от данни "червено-черно дърво". Това е вид бинарно дърво, което няма да разглеждаме подробно в теоретичен план, но трябва поне да знаем, че при него ключовете са подредени по големина според определени от вас правила. Казано по друг начин това ще е един сортиран речник - пълната аналогия на примера ни с речниците по чужди езици, където думите са сортирани по азбучен ред. Използвайте TreeMap само в случай, че имате нужда от извличане на елементите, сортирани в нарастващ ред, защото бързината на операциите в общия случай е по-ниска от тази на HashMap - при TreeMap тя е o(log(n)).
Пример за използване на TreeMap - извеждаме списък с уникалните думи от текстови файл и броят на срещанията им, но подредени по азбучен ред:
import java.util.TreeMap;
import java.util.Map;
import java.util.Scanner;
import java.io.FileReader;
import java.io.IOException;
public class TreeMapExample{
public static void main(String[] args){
Scanner sc = null;
try{
sc = new Scanner(new FileReader("problems.txt"));
}
catch(IOException e){
System.out.println("Error reading the file");
return;
}
// Добавяме всяка дума в дървото
TreeMap<String, Integer> wordsOccurencies = new TreeMap<String, Integer>();
while(sc.hasNext()){
String word = sc.next();
Integer count = wordsOccurencies.get(word);
count = (count==null?1:count+1);
wordsOccurencies.put(word, count);
}
sc.close();
// Обхождаме дървото и отпечатваме само ключовете (думите)
System.out.println("List of words");
for (String treeKey : wordsOccurencies.keySet()){
System.out.println(treeKey);
}
// Обхождаме дървото и отпечатваме ключовете и стойностите
System.out.println("\nList of words and occurencies");
for (Map.Entry<String, Integer> entry: wordsOccurencies.entrySet()) {
String key = entry.getKey();
Integer value = entry.getValue();
System.out.println(key+": "+value);
}
}
}
Основно и много важно изискване за това да можете да добавите елементи в TreeMap е обектите да са сравними, т.е. да имат метод compare() - така например е в клас String, затова в горния пример нямаше проблеми със създаването на дървото. Ако вие правите свой собствен обект, който трябва да бъде включен в структура TreeMap, той трябва да има задължително compare метод.
Също от горния пример може да се види, че в TreeMap няма проблем с това при един и същи Key да има множество Value.
Добави коментар