Free C# / Java / JavaScript / Python / C++ Programming Books » Глава 18. Речници, хеш-таблици и множества

Автор

Владимир Цанев

В тази тема...

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

Съдържание

Видео

Презентация

18. Java associative arrays from Intro C# Book

Структура от данни "речник"

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

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

При речниците заедно с данните, които държим, пазим и ключ, по който ги намираме. Елементите на речниците са двойки (ключ, стойност), като ключът се използва при търсене.

Структура от данни "речник" – пример

Ще илюстрираме какво точно представлява тази структура от данни с един конкретен пример от ежедневието.

Когато отидете на театър, опера или концерт често преди да влезете в залата или стадиона има гардероб, в който може да оставите дрехите си. Там давате дрехата си на служителката от гардероба, тя я оставя на определено място и ви дава номерче. След като свърши представлението, на излизане давате вашето номерче, и чрез него служителката намира точно вашата дреха и ви я връща.

Чрез този пример виждаме, че идеята да разполагаме с ключ (номерче, което ви дава служителката) за данните (вашата дреха) и да ги достъпваме чрез него, не е толкова нереална. В действителност това е подход, който се среща на много места, както в програмирането така и в много сфери на реалния живот.

При структурата речник този ключ може да на е просто номерче, а всякакъв друг обект. В случая, когато имаме ключ (номер), можем да реализираме такава структура като обикновен масив. Тогава множеството от ключове е предварително ясно – числата от 0 до n, където n е размерът на масива. Целта на речниците е да ни освободи, до колкото е възможно, от ограниченията за множеството на ключовете.

При речниците обикновено множеството от ключове е произволно множество от стойности, примерно реални числа или символни низове. Единственото задължително изискване е да можем да различим един ключ от друг. След малко ще се спрем по-конкретно на някои допълнителни изисквания към ключовете, необходими за различните реализации.

Речниците съпоставят на даден ключ дадена стойност. На един ключ може да се съпостави точно една стойност. Съвкупността от всички двойки (ключ, стойност) съставя речника.

Абстрактна структура данни "речник" (асоциативен масив, карта)

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

Задължителни операции, които тази структура дефинира, са следните:

- Object put(key, value) – добавя в речника зададената наредена двойка. Ако вече имаме двойка с такъв ключ стойността за него се заменя с новата, а старата стойност се връща като резултат.

- Object get(key) – връща стойността по даден ключ. Ако в речника няма двойка с такъв ключ, връща null.

- boolean remove(key) – премахва стойността за този ключ от речника. Освен това връща дали е премахнат елемент от речника.

Ето и някои операции, които различните реализации на речници често предлагат:

- boolean isEmpty() – връща true, ако нямаме данни в речника и false, ако той съдържа поне една двойка (ключ, стойност).

- boolean contains(key) – връща true, ако в речникът има двойка с дадения ключ.

- int size() – връща броя елементи в речника.

- Други операции – например извличане на всички ключове, стойности или наредени двойки, в друга структура (масив, списък, множество), която лесно може да бъде обходена чрез цикъл.

Интерфейсът Map<K, V>

В Java има дефиниран стандартен интерфейс Map<K, V>, който дефинира всички основни операции, които речниците трябва да реализират. Този интерфейс съответства на абстрактната структура от данни "речник" и дефинира операциите, изброени по-горе, но без да предоставя конкретна реализация за всяка от тях.

В Java интерфейсите представляват спецификации за методите на даден клас. Те дефинират празни методи, които след това могат да бъдат имплементирани от конкретен клас, който обявява, че поддържа дадения интерфейс. Как работят интерфейсите и наследяването ще разгледаме подробно в главата "Принципи на обектно-ориентираното програмиране". За момента е достатъчно да знаете, че интерфейсите задават какви методи трябва да има в даден клас.

В настоящата тема ще разгледаме двата най-разпространени начина за реализация на речници – балансирано дърво и хеш-таблица. Изключително важно е да знаете, по-какво се отличават те един от друг и какви са основните принципи, свързани с тях. В противен случай рискувате да ги използвате неправилно и неефективно.

В Java има две важни имплементации на интерфейса Map: TreeMap и HashMap. TreeMap представлява имплементация с балансирано (червено-черно) дърво, а HashMap – имплементация с хеш-таблица.

Освен HashMap и TreeMap в Java има още имплементации на интерфейса Map, които обаче не трябва да се ползват освен, ако не ги познавате добре. Такива са например класовете Hashtable, ConcurrentHashMap и много други. Правилото е, че когато не знаете каква имплементация да ползвате винаги ползвайте HashMap или TreeMap.

От тази и следващата тема ще разберете в кои случаи да ползвате TreeMap<K, V> и в кои HashMap<K, V>.

Реализация на речник с червено-черно дърво

Тъй като имплементацията на речник чрез балансирано дърво е изключително сложна, няма да я разглеждаме във вид на сорс код. Вместо това ще разгледаме класа TreeMap<K, V>, който идва наготово заедно със стандартните библиотеки на Java.

Както беше обяснено вече в предната глава, червено-черното дърво е подредено двоично балансирано дърво за претърсване. Ето защо едно от важните изисквания, които са наложени върху множеството от ключове при използването на TreeMap<K, V>, е те да имат наредба. Това означава, че ако имаме два ключа, то или единият е по-голям от другия, или те са равни.

Използването на двоично дърво ни носи едно силно предимство: ключовете в речника се пазят сортирани. Благодарение на това свойство, ако данните ни трябват подредени по ключ, няма нужда да ги сортираме допълнително. Всъщност това свойство е единственото предимство на тази реализация пред реализацията с хеш-таблица. Пазенето на ключовете сортирани идва със своята цена. Работата с балансирани дървета е малко по-бавна от работата с хеш-таблици. По тази причина, ако няма специални изисквания за наредба на ключовете, за предпочитане е да се използва HashMap<K, V>.

Използвайте реализация на речник чрез балансирано дърво само когато се нуждаете от свойството наредените двойки винаги да са сортирани по ключ.

Класът TreeMap<K, V>

Класът TreeMap<K, V> представлява имплементация на речник чрез червено-черно дърво. Този клас имплементира всички стандартни операции, типични за абстрактната структура данни речник и дефинирани в интерфейса Map<K, V>. В допълнение към тях TreeMap<K, V> дефинира още операции, свързани с наредбата на елементите:

- извличане на най-малък и най-голям елемент – firstEntry(), lastEntry(), firstKey(), lastKey();

- извличане на всички елементи, по-малки или по-големи от даден ключ – headMap(key), tailMap(key);

- извличане на всички елементи в даден диапазон (примерно със стойност на ключа между 100 и 200) – subMap(startKey, endKey).

Тези операции може да са много полезни при решавани на задачи, свързани с бързо извличане на подмножества на дадено множество.

Използване на класа TreeMap – пример

Сега ще решим един практически проблем, където използването на класа TreeMap е уместно. Нека имаме някакъв текст. Нашата задача ще бъде да намерим всички различни думи в текста, както и колко пъти се срещат всяка от тях в текста. Като допълнително условие искаме да изведем намерените думи по азбучен ред.

При тази задача използването на речник е особено подходящо. За ключове трябва да изберем думите от текста, а стойността записана в речника за всеки ключ ще бъде броят срещания на съответната дума.

Алгоритъмът за броене на думите се състои в следното: четем текста дума по дума и за всяка дума проверяваме дали вече присъства в речника. Ако отговорът е не, добавяме нов елемент в речника с ключ думата и стойност 1 (едно срещане). Ако отговорът е да, презаписваме стойността за текущата дума със старата й стойност + 1 (увеличаваме с единица броя срещания на думата).

Използването на реализация на речник чрез балансирано дърво ни дава свойството, че когато обхождаме елементите му те ще бъдат сортирани по ключа. По този начин реализираме допълнително наложеното условие думите да са сортирани по азбучен ред. Следва реализация на описания алгоритъм:

TreeMapExample.java

import java.util.Map;

import java.util.TreeMap;

import java.util.Scanner;

/**

* This class demonstrates using of {@link TreeMap} class.

* @author Vladimir Tsanev

public class TreeMapDemo {

private static final String TEXT = "Test text words Count " +

"words count teSt";

public static void main(String[] args) {

Map<String, Integer> wordsCounts = createWordsCounts(TEXT);

printWordsCount(wordsCounts);

}

private static Map<String, Integer> createWordsCounts(

String text) {

Scanner textScanner = new Scanner(text);

Map<String, Integer> words = new TreeMap<String, Integer>();

while (textScanner.hasNext()) {

String word = textScanner.next();

Integer count = words.get(word);

if (count == null) {

count = 0;

}

words.put(word, count + 1);

}

return words;

}

private static void printWordsCount(

Map<String, Integer> wordsCounts) {

for (Map.Entry<String, Integer> wordEntry

: wordsCounts.entrySet()) {

System.out.printf(

"word '%s' is seen %d times in the text%n",

wordEntry.getKey(), wordEntry.getValue());

}

Изходът от примерната програма е следният:

word 'Count' is seen 1 times in the text

word 'Test' is seen 1 times in the text

word 'count' is seen 1 times in the text

word 'teSt' is seen 1 times in the text

word 'text' is seen 1 times in the text

word 'words' is seen 2 times in the text

В този пример за пръв път демонстрираме обхождане на всички елементи на речник – методът printWordsCount(SortedMap<String, Integer>). За целта използваме подобрената версия на конструкцията за цикъл for (enhanced for loop). Начинаещите програмисти често срещат проблем при обхождане на речници, тъй като за разлика от списъците и масивите елементите на тази структура от данни са наредени двойки (ключ и стойност), а не просто единични обекти.

В примера използваме метода entrySet(), който ни връща множество с обекти, имплементиращи интерфейса Map.Entry. Този интерфейс декларира методите getKey() и getValue(), които ни дават достъп съответно до ключа и до стойността. Важно е да се разбере ясно, че самият речник не може да бъде обходен, но можем да обходим множество от неговите наредени двойки. Това разбира се не ни ограничава по никакъв начин.

Интерфейсът Comparable<K>

При използване на TreeMap<K, V> има задължително изискване ключовете да са от тип, чиито стойности могат да се сравняват по големина. В нашия пример ползваме за ключ обекти от тип String.

Класът String имплементира интерфейса Comparable, като сравнението е стандартно. Какво означава това? Тъй като низовете в Java са case sensitive (т.е. има разлика между главна и малка буква), то думи като "Count" и "count" се смятат за различни, а думите, които започват с малка буква, са след тези с голяма. Понякога това може да е неудобство, но то е следствие от естествената наредба на низовете дефинирана в класа String. Тази дефиниция идва от имплементацията на метода compareTo( String), чрез който класът String имплементира интерфейса Comparable.

Интерфейсът Comparator<K>

Какво можем да направим, когато естествената наредба не ни удовлетворява? Например, ако искаме при сравнението на думите да не се прави разлика между малки и главни букви.

Един вариант е след като прочетем дадена дума да я преобразуваме към малки или главни букви. Този подход ще работи за символни низове, но понякога ситуацията е по-сложна. Затова сега ще покажем друго решение, което работи за всеки произволен клас, който няма естествена наредба (не имплементира Comparable) или има естествена наредба, но ние искаме да я променим.

За сравнение на обекти по изрично дефинирана наредба в Java е има един интерфейс Comparator<E>. Той дефинира функция за сравнение compare(E o1, E o2), която задава алтернативна на естествената наредба. Нека разгледаме в детайли този интерфейс. За интерфейсите ще ви разкажем подробно в главата "Принципи на ООП". За момента приемете, че те представляват дефиниции на един или няколко метода, които могат да бъдат имплементирани от даден клас.

Когато създаваме обект от класа TreeMap<K, V> можем да подадем на конструктора му референция към Comparator<K> и той да използва него при сравнение на ключовете (които са елементи от тип K).

Ето една реализация чрез анонимен клас на интерфейса Comparator<K>, която решава проблема с главните и малките букви:

Comparator<String> caseInsensitiveComparator =

new Comparator<String>(){

@Override

public int compare(String o1, String o2) {

return o1.compareToIgnoreCase(o2);

}

};

Нека използваме този Comparator<Е> при създаването на речника:

Map<String, Integer> words =

new TreeMap<String, Integer>(caseInsensitiveComparator);

След тази промяна резултатът от изпълнението на програмата ще бъде:

word 'Count' is seen 2 times in the text

word 'Test' is seen 2 times in the text

word 'text' is seen 1 times in the text

word 'words' is seen 2 times in the text

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

Използвайки Comparator<Е> ние на практика сменихме дефиницията за подредба на ключове в рамките на нашия речник. Ако за ключ използвахме клас, дефиниран от нас, примерно Student, който имплементира Comparable<Е>, бихме могли да постигнем същия ефект чрез подмяна на реализацията на метода му compareTo(Student). Има обаче едно изискване, което трябва винаги да се стремим да спазваме, когато имплементираме Comparable<K>. То гласи следното:

Винаги, когато два обекта са еднакви (equals(Object) връща true), compareTo(Е) трябва да връща 0.

Удовлетворяването на това условие ще ни позволи да ползваме обектите от даден клас за ключове, както в реализация с балансирано дърво (TreeMap, конструиран без Comparator), така и в реализация с хеш-таблица (HashMap).

Хеш-таблици

Нека сега се запознаем със структурата от данни хеш-таблица, която реализира по един изключително ефективен начин абстрактната структура данни речник. Ще обясним в детайли как работят хеш-таблиците и защо са толкова ефективни.

Реализация на речник с хеш-таблица

Реализацията с хеш-таблица има важното предимство, че времето за достъп до стойност от речника, при правилно използване, не зависи от броя на елементите в него (поне на теория).

За сравнение да вземем списък с елементи, които са подредени в случаен ред. Искаме да проверим дали даден елемент се намира в него. В най-лошия случай, трябва да проверим всеки един елемент от него, за да дадем категоричен отговор на въпроса "съдържа ли списъкът елемента или не". Очевидно е, че броят на тези сравнения зависи (линейно) от броят на елементите в списъка.

При хеш-таблиците, ако разполагаме с ключ, броят сравнения, които трябва да извършим, за да установим има ли стойност с такъв ключ, е константен и не зависи от броя на елементите в нея. Как точно се постига такава ефективност ще разгледаме в детайли по-долу.

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

Какво е хеш-таблица?

Хеш-таблицата обикновено е реализирана с масив. Тя съдържа наредени двойки (ключ, стойност), които са разположени в масива на пръв поглед случайно и непоследователно. В позициите, в които нямаме наредена двойка, имаме празен елемент (null):

Размерът на таблицата (масива), наричаме капацитет (capacity) на хеш-таблицата. Степен на запълненост наричаме реално число между 0 и 1, което съответства на отношението между броя на запълнените елементи и текущия капацитет. На фигурата имаме хеш-таблица с 3 елемента и капацитет m. Степента на запълване на хеш-таблицата е 3/m.

Добавянето и търсенето на елементи става, като върху ключа се приложи някаква функция hash(key), която връща число, наречено хеш-код. Като вземем остатъка при деление на този хеш-код с капацитета m получаваме число между 0 и m-1:

index = hash(key) % m

На фигурата е показана хеш-таблица T с капацитет m и хеш-функция hash(key):

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

Използвайте реализация на речник чрез хеш-таблици, когато се нуждаете от максимално бързо намиране на стойностите по ключ.

Капацитетът на таблицата се увеличава, когато броят на наредените двойки в хеш-таблицата стане равен или по-голям от дадена константа, наречена максимална степен на запълване (load factor). При разширяване на капацитета (най-често удвояване) всички елементи се преподреждат според своя хеш-код и стойността на новия капацитет. Степента на запълване след преподреждане значително намалява. Операцията е времеотнемаща, но се извършва достатъчно рядко, за да не влияе на цялостната производителност на операцията добавяне.

Класът HashMap<K, V>

Класът HashMap<K, V> е стандартна имплементация на речник с хеш-таблица в Java Collections Framework. Ще се спрем на основните операции, които той предоставя, както и на един конкретен пример, който илюстрира използването на класа и неговите методи.

Основни операции с класа HashMap<K, V>

Създаването на хеш-таблица става чрез извикването на някои от конструкторите на HashMap<K, V>. Чрез тях можем да зададем начални стойности за капацитет и максимална степен на запълване. Добре е, ако предварително знаем приблизителният брой на елементите, които ще бъдат добавени в нашата хеш-таблица, да го укажем още при създаването й. Така ще избегнем излишното разширяване на таблицата и ще постигнем по-добра ефективност. По подразбиране стойността на началния капацитет 16, а на максималната степен на запълване е 0.75.

Да разгледаме какво прави всеки един от методите реализирани в класа HashMap<K, V>:

- V put(K, V) добавя нова стойност за даден ключ или презаписва вече съществуващата за този ключ. В резултат се връща старата стойност за посочения ключ или null, ако няма стара стойност. Операцията работи изключително бързо.

- void putAll(Map<K, V>) добавя всички наредени двойки от друг речник в текущия. Извикването на този метод е еквивалентно на извикването на put(K, V) за всеки един елемент на речника, който е подаден като параметър.

- V get(Object) връща стойността за дадения ключ или null, ако няма елемент с такъв ключ. Операцията работи изключително бързо.

- V remove(K) изтрива от речника елемента с този ключ. Операцията работи изключително бързо.

- void clear() премахва всички елементи от речника.

- boolean containsKey(K) проверява дали в речника присъства наредена двойка с посочения ключ. Операцията работи изключително бързо.

- boolean containsValue(V) проверява дали в речникa присъстват една или повече наредени двойки с посочената стойност. Тази операция работи бавно, тъй като проверява всеки елемент на хеш-таблицата.

- boolean isEmpty() връща true ако в речника няма нито една наредена двойка и false в противен случай.

- int size() връща броя на наредените двойки в речника.

- Set<Map.Entry<K, V> entriesSet() връща множество от наредените двойки в речника. Така можем лесно да ги обходим в цикъл.

- Set<K> keySet() връща множество от всички ключове в речника.

- Collection<V> values() връща колекция (може да има повторения) от всички стойности в речника.

Студенти и оценки – пример

Сега ще илюстрираме как се ползват някои от описаните по-горе операции чрез един пример. Имаме студенти. Всеки от тях би могъл да има най-много една оценка. Искаме да съхраняваме оценките в някаква структура, в която можем бързо да търсим по име на студент.

За тази задача ще създадем хеш-таблица с начален капацитет 6. Тя ще има за ключове имената на студентите, а за стойности – някакви техни оценки. Добавяме 6 примерни студента, след което наблюдаваме какво се случва като отпечатваме на стандартния изход техните данни. Ето как изглежда кодът от този пример:

Map<String, Double> studentsNarks =

new HashMap<String, Double>(6);

studentsNarks.put("Pesho", 3.00);

studentsNarks.put("Gosho", 4.50);

studentsNarks.put("Nakov", 5.50);

studentsNarks.put("Vesko", 3.50);

studentsNarks.put("Tsanev", 4.00);

studentsNarks.put("Nerdy", 6.00);

Double tsanevMark = studentsNarks.get("Tsanev");

System.out.printf("Tsanev's mark: %.2f %n", tsanevMark);

studentsNarks.remove("Tsanev");

System.out.println("Tsanev removed.");

System.out.printf("Is Tsanev in the hash table: %b %n",

studentsNarks.containsKey("Tsanev"));

studentsNarks.put("Nerdy", 3.25);

System.out.println("Nerdy's mark changed.");

System.out.println("Students and marks:");

for (Map.Entry<String, Double> studentMark

: studentsNarks.entrySet()) {

System.out.printf("%s has %.2f%n",

studentMark.getKey(), studentMark.getValue());

}

System.out.printf("There are %d students.%n",

studentsNarks.size());

studentsNarks.clear();

System.out.println("Students hashmap cleared.");

System.out.printf("Is hash table empty: %b%n",

studentsNarks.isEmpty());

Изходът от изпълнението на този код е следният:

Tsanev's mark: 4,00

Tsanev removed.

Is Tsanev in the hash table: false

Nerdy's mark changed.

Students and marks:

Nerdy has 3,25

Nakov has 5,50

Vesko has 3,50

Gosho has 4,50

Pesho has 3,00

There are 5 students.

Students hashmap cleared.

Is hash table empty: true

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

Важно е да се запомни, че при хеш-таблиците не можем да разчитаме на никаква наредба на елементите. Ако се нуждаем от такава, можем преди отпечатване да сортираме елементите. Друг вариант е да използваме TreeMap<K, V>.

Хеш-функции и хеширане

Сега ще се спрем по-детайлно на понятието, хеш-код, което употребихме малко по-рано. Хеш-кодът представлява числото, което ни връща т.нар. хеш-функция, приложена върху ключа. Това число трябва да е различно за всеки различен ключ или поне с голяма вероятност при различни ключове хеш-кодът трябва да е различен.

Хеш-функции

Съществува понятието перфектна хеш-функция (perfect hash function). Това означава, че ако имаме N ключа, тази функция на всеки ключ ще съпоставя различно цяло число в някакъв смислен интервал (например от 0 до N-1). Намирането на такава функция в общия случай е доста трудна, почти невъзможна задача. Такива функции си струва да се използват само при множества от ключове, които са с предварително известни елементи или ако множеството от ключове поне рядко се променя.

В практиката се използват други, не чак толкова "перфектни" хеш-функции. Сега ще разгледаме няколко примера за хеш-функции, които се използват директно в Java библиотеките.

Методът hashCode() в Java платформата

Всички Java класове имат метод hashCode(), който връща стойност от тип int. Този метод се наследява от класа Object, който стои в корена на йерархията на всички Java класове.

Имплементацията в класа Object на класа hashCode() е native метод (метод имплементиран на ниско ниво от доставчика на виртуалната машина), който обикновено връща число базирано на адреса на обекта в паметта, но това въобще не е задължително. Тъй като този метод е имплементиран от създателя на виртуалната машина, не се знае каква точно ще е имплементацията. Връщаната стойност от този метод е непредсказуема и затова никога не трябва да разчитате на нея.

Друг пример за хеш-функция, която идва директно от Java, е тази, която се ползва от класовете, дефиниращи цели числа като, Integer, Byte и Short. Там за хеш-код се ползва стойността на самото число.

Да разгледаме един по-сложен пример за хеш-функция, който също идва от вградените в Java класове. Става въпрос за имплементацията на хеш-функция, която се ползва от класа String. Тя връща 0, ако низът е празен, а в противен случай хеш-кодът се изчислява по формулата:

hash(s) = s₀*31^n-1 + s₁*31^n-2 + … + s_n

където s_i, е i-ият символ на низа, a n е неговата дължина.

На читателя оставяме да разгледа други имплементации на метода hashCode() в някои от най-често използваните класове като Date, Long, Float и Double.

Сега, нека се спрем на въпроса как да имплементираме сами този метод за нашите класове. Вече обяснихме, че оставянето на имплементацията, която идва наготово от Object, не е допустимо решение. Друга много проста имплементация е винаги да връщаме някаква фиксирана константа, примерно:

@Override

public int hashCode() {

return 53;

}

Ако използваме хеш-таблица и ползваме за ключовете й обекти от клас, който има горната имплементация на hashCode(), ще получим много лоша производителност, защото всеки път, когато добавяме нов елемент в таблицата, ще трябва да го слагаме на едно и също място. Когато търсим, всеки път ще попадаме в една и съща клетка на таблицата.

За да се избягва описаното неблагоприятно поведение, трябва хеш-функцията да разпределя ключовете максимално равномерно сред възможните стойности за хеш-код.

Колизии при хеш-функциите

Ситуация, при която два различни ключа връщат едно и също число за хеш-код наричаме колизия:

Как да решим проблема с колизиите ще разгледаме подробно в следващия параграф. Най-простото решение, обаче е очевидно: двойките, които имат ключове с еднакви хеш-кодове да нареждаме в списък:

Следователно при използване на константа за хеш-код, нашата хеш-таблица се изражда в линеен списък и употребата й става неефективна.

Имплементиране на метода hashCode()

Ще дадем един стандартен алгоритъм, по който можем сами да имплементираме hashCode(), когато ни се наложи:

Първо трябва да определим полетата на класа, които участват по някакъв начин в имплементацията на equals() метода. Това е необходимо, тъй като винаги, когато equals() е true трябва резултатът от hachCode() да е един и същ. Така полетата, които не участват в пресмятането на equals(), не трябва да участват и в изчисляване на hashCode().

След като сме определили полетата, които ще участват в изчислението на hashCode(), трябва по някакъв начин да получим за тях стойности от тип int. Ето една примерна схема:

- Ако полето е boolean, за true взимаме 1, а за false взимаме 0.

- Ако полето е от тип int, byte, short, char можем да го преобразуваме към int, чрез оператора за явно преобразуване (int). Ако е от тип long, го разделяме на 2 части по 32 бита и получаваме от него две int стойности.

- Ако полето е от тип float или double, можем да го превърнем в целочислен вид чрез методите Float.floatToIntBits() или Double.doubleToLongBits(). В случая с double резултатът третираме както long от горната точка.

- Ако полето не е от примитивен тип, просто извикваме метода hashCode() на този обект. Ако стойността на полето е null, връщаме 0.

- Ако полето е масив или някаква колекция, извличаме хеш-кода за всеки елемент на тази колекция.

Накрая сумираме получените int стойности, като преди всяко събиране умножаваме временния резултат с някое просто число (например 31), като игнорираме евентуалните препълвания на типа int.

В крайна сметка получаваме хеш-код, който е добре разпределен в пространството от всички 32-битови стойности. Можем да очакваме, че при така изчислен хеш-код колизиите ще са рядкост, тъй като всяка промяна в някое от полетата, участващи в описаната схема за изчисление, води до съществена промяна в хеш-кода.

Имплементиране на hashCode() – пример

Да илюстрираме горният алгоритъм с един пример. Нека имаме клас, чиито обекти представляват точка в тримерното пространство. И нека точката вътрешно представяме чрез нейните координати по трите измерения x, y и z:

Point3D.java

/**

* Class representing points in three dimensional space.

* @author Vladimir Tsanev

public class Point3D {

private double x;

private double y;

private double z;

/**

* Construct new {@link Point3D} instance by specified

* Cartesian coordinates of the point.

* @param x - x coordinate of the point

* @param y - y coordinate of the point

* @param z - z coordinate of the point

public Point3D(double x, double y, double z) {

super();

this.x = x;

this.y = y;

this.z = z;

}

Можем лесно да реализираме hashCode() по описания по-горе алгоритъм.

Автоматично генериране на hashCode() в Eclipse

Eclipse, както и повечето модерни среди за разработка, могат автоматично да генерират кода за методите equals() и hashCode(). При Еclipse имплементацията на hashCode() ще бъде по алгоритъм, сходен на описания по-горе. Можете да генерирате автоматично методите equals() и hashCode() за даден клас по следния начин: от менюто Source избирате Generate hasCode and equals()... След това избирате полетата, които искате да участват в изчисленията за двата метода и натискате бутона [OK]. За нашия клас Point3D генерираният код е следният:

@Override

public int hashCode() {

final int prime = 31;

int result = 1;

long temp;

temp = Double.doubleToLongBits(x);

result = prime * result + (int) (temp ^ (temp >>> 32));

temp = Double.doubleToLongBits(y);

result = prime * result + (int) (temp ^ (temp >>> 32));

temp = Double.doubleToLongBits(z);

result = prime * result + (int) (temp ^ (temp >>> 32));

return result;

}

@Override

public boolean equals(Object obj) {

if (this == obj)

return true;

if (obj == null)

return false;

if (getClass() != obj.getClass())

return false;

Point3D other = (Point3D) obj;

if (Double.doubleToLongBits(x)

!= Double.doubleToLongBits(other.x))

return false;

if (Double.doubleToLongBits(y)

!= Double.doubleToLongBits(other.y))

return false;

if (Double.doubleToLongBits(z)

!= Double.doubleToLongBits(other.z))

return false;

return true;

}

Тази имплементация е несравнимо по-добра, от това да не правим нищо или да връщаме константа. Въпреки това колизиите и при нея се срещат, но доста по-рядко.

Решаване на проблема с колизиите

На практика колизиите могат да се избегнат в изключително редки и специфични ситуации. За това е необходимо да живеем с идеята за тяхното присъствие в нашите хеш таблици и да се съобразяваме с тях. Нека разгледаме няколко стратегии за справяне с колизиите:

Нареждане в списък (chaining)

Най-разпространеният начин за решаване на проблема с колизиите е нареждането в списък (chaining). Той се състои в това двойките ключ и стойност, които имат еднакъв хеш-код за ключа да се нареждат в списък един след друг.

Реализация на речник чрез хеш-таблица и chaining

Нека си поставим за задача да реализираме структурата от данни речник чрез хеш-таблица с решаване на колизиите чрез нареждане в списък (cahining). Да видим как може да стане това. Първо ще дефинираме клас, който описва наредена двойка (entry). Той капсулира в себе си двойка ключ и стойност:

DictionaryEntry.java

/**

* This class is used by Dictionary Abstract Data Type (ADT).

* It encapsulates Key and Value objects.

* @author Vladimir Tsanev

* @param <K> - type of the keys.

* @param <V> - type of the values.

public class DictionaryEntry<K, V> {

private K key;

private V value;

public DictionaryEntry(K key, V value) {

this.key = key;

this.value = value;

}

public K getKey() {

return this.key;

}

public V getValue() {

return this.value;

}

@Override

public String toString() {

return String.format("[%s, %s]", key, value);

}

Този клас има конструктор, който приема ключ и стойност. Дефинирани са два метода за достъп съответно за ключа (getKey()) и стойността (getValue()). Ще отбележим, че нарочно нямаме публични методи, чрез които да променяме стойностите на ключа и стойността. Това прави този клас непроменяем (immutable). Това е добра идея, тъй като обектите, които ще се пазят вътрешно в реализациите на речника, ще бъдат същите като тези, които ще връщаме например при реализацията на метод за вземане на всички наредени двойки.

Предефинирали сме метода toString(), за да можем лесно да отпечатваме наредената двойка на стандартния изход или в текстов поток.

Следва примерен шаблонен интерфейс, който дефинира най-типичните операции за типа речник:

Dictionary.java

/**

* Interface that defines basic methods needed

* for a class which maps keys to values.

* @param <K> - type of the keys

* @param <V> - type of the values

* @author Vladimir Tsanev

public interface Dictionary<K, V>

extends Iterable<DictionaryEntry<K, V>> {

/**

* Adds specified value by specified key to the dictionary.

* If the key already exists its value is replaced with the

* new value and the old value is returned.

* @param key - key for the new value

* @param value - value to be mapped with that key

* @return the old value for the specified key or null if the

* key does not exists

* @throws NullPointerException if specified key is null.

public V put(K key, V value);

/**

* Finds the value mapped by specified key.

* @param key - key for which the value is needed.

* @return value for the specified key if present,

* or null if there is no value with such key.

public V get(K key);

/**

* Removes a value mapped by specified key.

* @param key - key for which the value will be removed

* @return <code>true</code> if value for the specified

* key if present, or <code>false</code> if there is

* no value with such key in the dictionary.

public boolean remove(K key);

/**

* Checks if there are any elements in the dictionary.

* @return <code>true</code> if there is more than

* one element in the dictionary, and

* <code>false</code> otherwise.

public boolean isEmpty();

/**

* Removes all elements from the dictionary.

public void clear();

}

В интерфейса по-горе, както и в предходния клас използваме шаблонни типове (generics), чрез които декларираме параметри за типа на ключовете (K) и типа стойностите (V). Това позволява нашият речник да бъде използват с произволни типове за ключовете и за стойностите. Единственото изискване е ключовете да дефинират коректно методите equals() и hashCode().

Нашият интерфейс Dictionary<K, V> прилича много на интерфейса Map<K, V>, но е по-прост от него и описва само най-важните операции върху типа данни "речник". Той наследява системния интерфейс Iterable <DictionaryEntry<K, V>>, за да позволи речникът да бъде обхождан във for цикъл.

Следва примерна имплементация на речник, в който проблемът с колизиите се решава чрез нареждане в списък (chaining):

HashDictionary.java

import java.util.List;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Iterator;

/**

* Implementation of {@link Dictionary} interface

* using hash table. Collisions are resolved by chaining.

* @author Vladimir Tsanev

* @param <K> - the type of the keys

* @param <V> - the type of the values

public class HashDictionary<K, V> implements Dictionary<K, V> {

private static final int DEFAULT_CAPACITY = 2;

private static final float DEFAULT_LOAD_FACTOR = 0.75f;

private List<DictionaryEntry<K, V>>[] table;

private float loadFactor;

private int threshold;

private int size;

public HashDictionary() {

this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);

}

@SuppressWarnings("unchecked")

private HashDictionary(int capacity, float loadFactor) {

this.table = new List[capacity];

this.loadFactor = loadFactor;

this.threshold =

(int) (this.table.length * this.loadFactor);

}

@Override

public void clear() {

Arrays.fill(this.table, null);

this.size = 0;

}

private List<DictionaryEntry<K, V>> findChain(

K key, boolean createIfMissing) {

int index = key.hashCode();

index = index % this.table.length;

if (table[index] == null && createIfMissing) {

table[index] = new ArrayList<DictionaryEntry<K, V>>();

}

return table[index];

}

@Override

public V get(K key) {

List<DictionaryEntry<K, V>> chain = findChain(key, false);

if (chain != null) {

for (DictionaryEntry<K, V> dictionaryEntry : chain) {

if (dictionaryEntry.getKey().equals(key)) {

return dictionaryEntry.getValue();

}

return null;

}

@Override

public boolean isEmpty() {

return size == 0;

}

@Override

public V put(K key, V value) {

List<DictionaryEntry<K, V>> chain = findChain(key, true);

for (int i=0; i<chain.size(); i++) {

DictionaryEntry<K, V> entry = chain.get(i);

if (entry.getKey().equals(key)) {

// Key found -> replace its value with the new value

DictionaryEntry<K, V> newEntry =

new DictionaryEntry<K, V>(key, value);

chain.set(i, newEntry);

return entry.getValue();

}

chain.add(new DictionaryEntry<K, V>(key, value));

if (size++ >= threshold) {

expand();

}

return null;

}

/**

* Expands the underling table

@SuppressWarnings("unchecked")

private void expand() {

int newCapacity = 2 * this.table.length;

List<DictionaryEntry<K, V>>[] oldTable = this.table;

this.table = new List[newCapacity];

this.threshold = (int) (newCapacity * this.loadFactor);

for (List<DictionaryEntry<K, V>> oldChain : oldTable) {

if (oldChain != null) {

for (DictionaryEntry<K, V> dictionaryEntry : oldChain){

List<DictionaryEntry<K, V>> chain =

findChain(dictionaryEntry.getKey(), true);

chain.add(dictionaryEntry);

}

@Override

public boolean remove(K key) {

List<DictionaryEntry<K, V>> chain = findChain(key, false);

if (chain != null) {

for (int i=0; i<chain.size(); i++) {

DictionaryEntry<K, V> entry = chain.get(i);

if (entry.getKey().equals(key)) {

// Key found -> remove it

chain.remove(i);

return true;

}

return false;

}

@Override

public Iterator<DictionaryEntry<K, V>> iterator() {

List<DictionaryEntry<K, V>> entries =

new ArrayList<DictionaryEntry<K, V>>(this.table.length);

for (List<DictionaryEntry<K, V>> chain : this.table) {

if (chain != null) {

entries.addAll(chain);

}

return entries.iterator();

}

Ще обърнем внимание на по-важните моменти в този код. Нека започнем от конструктора. Единственият публичен конструктор е конструкторът по подразбиране. Той в себе си извиква друг конструктор като му подава някакви предварително зададени стойности за капацитет и степен на запълване. На читателя предоставяме да реализира валидация на тези параметри и да направи и този конструктор публичен, за да предостави повече гъвкавост на ползвателите на този клас.

Следващото нещо, на което ще обърнем внимание, е това как е реализирано нареждането в списък. При конструирането на хеш-таблицата в конструктора инициализираме масив от списъци, които ще съдържат нашите DictionaryEntry обекти. За вътрешно ползване сме реализирали един метод findChain(), който изчислява хеш-кода на ключа като вика метода hashCode() и след това разделя върнатата хеш-стойност на дължината на таблицата (капацитета). Така се получава индексът на текущия ключ в масива, съхраняващ елементите на хеш-таблицата. Списъкът с всички елементи, имащи съответния хеш-код се намира в масива на изчисления индекс. Ако списъкът е празен, той има стойност null. В противен случай в съответната позиция има списък от елементи за съответния ключ.

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

Другото нещо, на което ще обърнем внимание, е методът expand(), който разширява текущата таблица, когато се достигне максималното допустимо запълване. За целта създаваме нова таблица (масив), двойно по-голяма от старта. Изчисляваме новото максимално допустимо запълване, това е полето threshold. Следва най-важната част. Разширили сме таблицата и по този начин сме сменили стойността на this.table.length. Ако потърсим някой елемент, който вече сме добавили, методът findChain(K key), изобщо няма да върне правилната верига, в която да го търсим. Затова се налага всички елементи от старата таблица да се прехвърлят, като не просто се копират веригите, а се добавят наново обектите от клас DictionaryEntry в новосъздадени вериги.

За да имплементираме коректно обхождането на хеш-таблицата, реализирахме интерфейса Iterable<DictionaryEntry<K, V>>, който има метод, връщащ итератор по елементите на хеш-таблицата. За да реализираме метода итератора, първо прехвърляме всички елементи в ArrayList, а след това връщаме неговия итератор. Следва пример как можем да използваме нашата реализация на хеш-таблица и нейният итератор:

public class HashDictionaryExample {

public static void main(String[] args) {

HashDictionary<String, Integer> marks =

new HashDictionary<String, Integer>();

marks.put("Pepi", 3);

marks.put("Kiro", 4);

marks.put("Mimi", 6);

marks.put("Pepi", 5); // replace key "Pepi"

marks.remove("Kiro"); // remove key "Kiro"

marks.remove("123"); // key not found

// Use the iterator to traverse all entries

for (DictionaryEntry<String, Integer> entry : marks) {

System.out.print(entry + " ");

}

// Output: [Mimi, 6] [Pepi, 5]

}

В примерната имплементация на хеш-таблица има още една особеност. Методът findChain() не е реализиран напълно коректно, но проблемът трудно може да се прояви. Наистина в повечето случаи тази реализация ще работи без проблем. Но какво ще стане, ако добавяме елементи до безкрай? В един прекрасен момент, когато капацитетът е станал 2³¹ и се наложи да го разширим, то при умножение на това число с 2 ще получим -2 (вж. секцията за представяне на отрицателни числа в главата "Бройни системи"). След това при опит за създаване на нов масив с размер -2 естествено ще бъде хвърлено изключение и изпълнението на метода ще бъде прекратено.

За да напълните тази реализация на хеш-таблица с толкова много двойки (ключ, стойност) ви е необходима доста RAM памет. При зададена 1024MB памет на виртуалната машина изключението OutOfMemmoryError се хвърля още преди да са добавени 6 милиона и 300 хиляди двойки от тип Integer на ключа и стойността. На практика не е добра идея да се работи с изключително много данни на веднъж. Ето защо не трябва да ви притеснява и фактът, че максималната стойност за брой на елементи на масиви и колекции в Java е 2 147 483 647.

За да зададете максималната памет, която да заеме ваша програма преди получаването на изключителната ситуация OutOfMemmoryError, трябва при стартиране на виртуалната машина да подадете параметъра -XmxSIZE, където SIZE е обемът памет, който искате да зададете. По подразбиране тази стойност е само 64 MB. Например: ако искате да стартирате вашата програма с най-много 512 MB оперативна памет, трябва да изпълните:

java -Xmx512m SomeClassWithMainMethod

Методи за решаване на колизиите от тип отворена адресация (open addressing)

Нека сега разгледаме методите за разрешаване на колизиите, алтернативни на нареждането в списък. Най-общо идеята при тях е, че в случай на колизия се опитваме да сложим новата двойка на някоя свободна позиция от таблицата. Методите се различават по това как се избира къде да се търси свободно място за новата двойка. Освен това трябва да е възможно и намирането на тази двойка на новото й място.

Основен недостатък на този тип методи спрямо нареждането в списък е, че са неефективни при голяма степен на запълненост (близка до 1).

Линейно пробване (linear probing)

Този метод е един от най-лесните за имплементация. Линейното пробване най-общо представлява следният простичък код:

int newPosition = (oldPosition + i) % capacity;

Тук capacity е капацитетът на таблицата, oldPostion е позицията, за която получаваме колизия, а i е номер на поредното пробване. Ако новополучената позиция е свободна, то мястото се използва за новодобавената двойка, в противен случай пробваме отново, като увеличаваме i с единица. Възможно е пробването да е както напред така и назад. Пробване назад става като вместо да прибавяме, вадим i от позицията, в която имаме колизия.

Предимство на този метод е сравнително бързото намиране на нова позиция. За нещастие има изключително висока вероятност, ако на едно място е имало колизия, след време да има и още. Това на практика води до силна неефективност.

Използването на линейно пробване като метод за решаване на проблема с колизиите е неефективно и трябва да се избягва.

Квадратично пробване (Quadratic probing)

Това е класически метод за решаване на проблема с колизиите. Той се различава от линейното пробване с това, че за намирането на нова позиция се използва квадратна функция на i (номер на поредно пробване). Ето как би изглеждало едно такова решение:

int newPosition = (oldPosition + c1*i + c2*i*i) % capacity;

Тук се появяват две константи c1 и c2. Иска се c2 да е различна от 0, защото в противен случай се връщаме на линейно пробване.

От избора на c1 и c2 зависи на кои позиции спрямо началната ще пробваме. Например, ако c1 и c2 са равни на 1, ще пробваме последователно oldPosition, oldPosition + 2, oldPosition + 6, …. За таблица с капацитет от вида 2n, е най-добре да се изберат c1 и c2 равни на 0.5.

Квадратичното пробване е по-ефективно от линейното.

Двойно хеширане (double hashing)

Както става ясно и от името на този метод, при повторното хеширане за намиране на нова позиция се прави повторно хеширане на получения хеш-код, но с друга хеш-функция, съвсем различна от първата. Този метод е по-добър от линейното и квадратичното пробване, тъй като всяко следващо пробване зависи от стойността на ключа, а не от позицията определена за ключа в таблицата. Това има смисъл, защото позицията за даден ключ зависи от текущия капацитет на таблицата.

Кукувиче хеширане (cuckoo hashing)

Кукувичето хеширане е сравнително нов метод с отворена адресация за справяне с колизиите. Той е бил представен за пръв път от R. Pagh и F. Rodler през 2001 година. Името му идва от поведението, наблюдавано при някои видове кукувици. Майките кукувици избутват яйца и/или малките на други птици извън гнездото им, за да оставят техните яйца там и така други птици да се грижат за техните яйца (и малки след излюпването).

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

На картинката по-долу е показана примерна схема на хеш-таблица, която използва кукувиче хеширане. Всяка клетка, която съдържа елемент има връзка към алтернативната клетка за ключа, който се намира в нея. Сега ще проиграем различни ситуации за добавяне на нов елемент.

Ако поне една от двете хеш-функции ни даде свободна клетка, то няма проблем. Слагаме елемента в една от двете. Нека обаче и двете хеш функции са дали заети клетки и на случаен принцип сме избрали една от тях.

Нека също предположим, че това е клетката, в която се намира A. Новият елемент изритва A от неговото място, A на свой ред отива на алтернативната си позиция и изритва B, от неговото място. Алтернативното място за B обаче е свободно, така че добавянето завършва успешно.

Да предположим, че клетката, от която се опитва да изрита елемент, новият елемент е тази, в която се намира H. Тогава се получава зацикляне тъй като H и W образуват цикъл. В този случай трябва да се изпълни пресъздаване на таблицата, използвайки нови хеш-функции и по-голям размер.

В най-опростената си версия този метод има константен достъп до елементите си и то в най-лошия случай, но това е изпълнено само при ограниченото, че фактора на запълване е по-малък от 0.5.

Използването на три различни хеш-функции, вместо две може да доведе до ефективна горна граница на фактора на запълване до над 0.9.

Проучвания показват, че кукувичето хеширане и неговите варианти могат да бъдат много по-ефективни от широко използваните днес нареждане в списък и методите с отворено адресиране. Въпреки това все още този метод остава широко неизвестен и неизползван в практиката.

Структура от данни "множество"

В тази секция ще разгледаме абстрактната структура от данни множество (set) и две нейни типични реализации. Ще обясним предимствата и недостатъците им и в какви ситуации коя от имплементациите да предпочитаме.

Абстрактна структура данни "множество"

Множествата са колекции, в които няма повтарящи се елементи. В контекста на Java това ще означава, че за всеки обект от множества извиквайки метода му equals(), като подаваме като аргумент някои от другите обекти във множеството резултатът винаги ще е false.

Някои множества позволяват присъствието в себе си и на null, други не.

Освен, че не допуска повтарящи се обекти, друго важно нещо, което отличава множеството от списъците и масивите е, че неговите елементи си нямат номер. Елементите на множеството не могат да бъдат достъпвани по някакъв друг ключ, както е при речниците. Самите елементи играят ролята на ключ.

Единственият начин да достъпите обект от множество е като разполагате със самия обект или евентуално с обект, който е еквивалентен на него. Затова на практика достъпваме всички елементи на дадено множество наведнъж, докато го обхождаме в цикъл. Например чрез разширената конструкцията за for цикъл.

Основните операции, които се дефинират от структурата множество са следните:

- boolean add(element) – добавя в множеството зададен елемент, като ако вече има такъв елемент, връща false, а в противен случай true.

- boolean contains(element) – проверява дали множеството съдържа посочения елемент. Ако го има връща true, a в противен случай false.

- boolean remove(element) – премахва посочения елемент от множеството, ако съществува. Връща дали е елементът е бил намерен.

- Set intersect(Set other) – връща сечението на две множества – множество, което съдържа всички елементи, които са едновременно и в едното и в другото множество.

- Set union(Set other) – връща обединението на две множества – множество, което съдържа всички елементи, които са или в едното или в другото множество или и в двете.

- boolean containsAll(Set other) – проверява дали дадено множество е подмножество на текущото. Връща true при положителен отговор и false при отрицателен.

В Java имаме основен интерфейс, който описва структурата от данни множество. Това е интерфейсът java.util.Set. Той има две основни имплементации и те са чрез хеш-таблица (HashSet) и чрез червено-черно дърво (TreeSet). Ако разгледаме внимателно имплементацията на тези класове ще видим, че те всъщност представляват речници, при които елементът е едновременно ключ и стойност за наредената двойка. Естествено, когато е удобно да работим с множества, трябва да ги предпочитаме, пред това да използваме речник.

Операции обединение и сечение на множества

Повечето от описаните по-горе методи ги има декларирани и в интерфейса Set. Някои от операциите, обаче нямат стандартна имплементация и се реализират малко по-специфично.

За да реализираме операцията union (обединение), трябва сами да напишем кода, реализиращ такава функционалност, примерно чрез използване на метода AddAll():

public static <E> Set<E> union(Set<E> set1, Set<E> set2) {

// Here we use HashSet but you can use TreeSet if appropriate

Set<E> union = new HashSet<E>();

union.addAll(set1);

union.addAll(set2);

return union;

}

Забележете, че създаваме нов обект за множеството, съдържащо обединението, а не добавяме първото множество към второто. Тук използваме описаната в следващият параграф имплементация HashSet. Благодарение на това след изпълнението на кода първото и второто множество продължават да съдържат точно елементите, които са съдържали и преди това.

Друга операция, която не ни е дадена наготово, е сечението на множества (intersection). За да я реализираме можем да използваме метода retainAll(), който премахва всички елементи от дадено множество, които не се съдържат в друго подадено като параметър. Ето една реализация на сечение, отново използваща HashSet:

public static <E> Set<E> intersect(Set<E> set1, Set<E> set2) {

// Here we use HashSet but you can use TreeSet if appropriate

Set<E> intersect = new HashSet<E>();

intersect.addAll(set1);

intersect.retainAll(set2);

return intersect;

}

Отново създаваме нов обект за резултата. Добавяме в резултата всички елементи от първото множество и след това премахваме от резултата всички елементи, които не се съдържат във второто множество.

Реализация с хеш-таблица – клас HashSet<T>

Реализацията на множество с хеш-таблица в Java е класът HashSet<T>. Този клас подобно на HashMap<K, V> има конструктори, в които може да се зададат степен на запълване и начален капацитет. Те имат същият смисъл, защото тук отново използваме хеш-таблица. Винаги е добре, ако знаете предварително приблизително размерът на множеството, да го задавате изрично.

За обединението може да използвате следната оценка на максималния брой елементи в резултата:

set1.size() + set2.size()

За сечението оценката на максималния брой елементи в резултата е:

Math.min(set1.size(), set2.size())

Ето един изключително прост пример, който демонстрира използване на множества и описаните в предния параграф методи за обединение и сечение:

Set<String> javaStudents = new HashSet<String>();

javaStudents.add("S. Nakov");

javaStudents.add("V. Kolev");

javaStudents.add("V. Tsanev");

Set<String> linuxStudents = new HashSet<String>();

linuxStudents.add("D. Alexiev");

linuxStudents.add("V. Tsanev");

System.out.println("Java Students: " + javaStudents);

System.out.println("Linux Students: " + linuxStudents);

System.out.println("Java or Linux Students: " +

union(javaStudents, linuxStudents));

System.out.println("Java and Linux Students: " +

intersect(javaStudents, linuxStudents));

Резултатът от изпълнението е:

Java Students: [V. Tsanev, S. Nakov, V. Kolev]

Linux Students: [D. Alexiev, V. Tsanev]

Java or Linux Students: [D. Alexiev, V. Tsanev, S. Nakov, V. Kolev]

Java and Linux Students: [V. Tsanev]

Обърнете внимание, че V. Tsanev присъства и в двете множества, но в обединението се появява само веднъж. Именно това показва че един елемент може да се съдържа най-много веднъж в дадено множество.

Реализация с черно-червено дърво – клас TreeSet<T>

Класът TreeSet<T> представлява множество, реализирано чрез червено-черно дърво. То има свойството, че в него елементите се пазят подредени по големина. Това е причината в него да можем да добавяме само елементи които са сравними. Припомняме, че в Java това обикновено означава, че обектите са от клас, който имплементира Comparable<T>. Ако това не е така, тук също можем да използваме интерфейса Comparator<T>, чрез който да задаваме наредба или да подменяме естествената.

Ще демонстрираме работата с класа TreeSet<T> с един не толкова формален и скучен пример. Нека имаме софтуерна компания, която искала всички нейни служители да се чувстват възможно най-добре по време на работния ден. Една от задачите, които си е поставило ръководството, била да се събере списък с всички любими на служителите музикални групи. Целта била да се състави списък с групите, подредени по азбучен ред. Всеки ден случайно се избирала една буква и звучали песни на групите започващи с тази буква. За простота всички имена написани от фирмените служители били на латиница. След като получили данните за всеки от служителите и уволнили хората с музикални вкусове противоречащи на фирмената политика, се получил списък с не много групи. Проблемът бил, че имало много повторения. Нашата цел е от даден неподреден по никакъв начин списък с групи да премахнем повторенията и да оставим само различните групи, като ги изведем по азбучен ред. Използването на TreeSet не е единственият начин да се реши тази задача, но тук ще демонстрираме колко просто става това с негова помощ:

String[] bandNames = new String[] {

"manowar", "blind guardian", "dio",

"grave digger", "slayer", "seputltura", "kiss", "sodom",

"manowar", "megadeth", "dio", "judas priest", "slayer",

"manowar", "kreator", "blind guardian", "iron maiden",

"accept", "seputltura", "iced earth", "manowar", "slayer",

"manowar", "helloween", "running wild", "manowar",

"sodom", "kiss", "iron maiden", "manowar", "manowar",

"sodom", "manowar", "slayer", "blind guardian", "accept",

"grave digger", "accept", "seputltura", "dio",

"running wild", "manowar", "iron maiden", "kiss",

"manowar", "manowar", "kiss", "manowar", "slayer",

"seputltura", "manowar", "manowar", "blind guardian",

"iron maiden", "sodom", "dio", "accept", "manowar",

"slayer", "megadeth", "dio", "manowar", "running wild",

"grave digger", "accept", "kiss", "manowar", "iron maiden",

"manowar", "judas priest", "sodom", "iced earth",

"manowar", "dio", "iron maiden", "manowar", "slayer",

"manowar" };

SortedSet<String> uniqueBandNames = new TreeSet<String>();

for (String bandName : bandNames) {

uniqueBandNames.add(bandName);

}

System.out.println("List of sorted and unique band names:");

for (String bandName : uniqueBandNames) {

System.out.println(bandName);

}

След изпълнението на програмата получаваме списъка:

List of sorted and unique band names:

blind guardian

dio

grave digger

helloween

iced earth

iron maiden

judas priest

kiss

kreator

manowar

megadeth

running wild

seputltura

slayer

sodom

Фирмата била изненадана от резултата, но пък тъй като за щастие всяка от групите е била достатъчно продуктивна през годините на нейното съществуване, лесно можели да заменят случайната буква със случайна група от списъка.

В крайна сметка важно е да си дадете сметка, че работата с множества е наистина лесна и проста. Ако познавате добре тяхната структура, ще можете и да ги ползвате ефективно и на място.

Упражнения

1. Напишете програма, която премахва всички числа, които се срещат нечетен брой пъти в дадена редица. Например, ако имаме началната редица {4, 2, 2, 5, 2, 3, 2, 3, 1, 5, 2, 6, 6, 6}, трябва да я редуцираме до редицата {5, 3, 3, 5}.

2. Реализирайте клас DictHashSet<Т>, базиран на класа HashDictionary <K, V>, който разгледахме по-горе.

3. Реализирайте хеш-таблица, която съхранява тройки стойности (ключ1, ключ2, стойност) и позволява бързо търсене по двойка ключове и добавяне на тройки стойности.

4. Реализирайте хеш-таблица, която позволява по даден ключ да съхраняваме повече от една стойност.

5. Реализирайте хеш-таблица, която използва кукувиче хеширане с 3 хеш функции за разрешаване на колизиите.

6. Дадени са три редици от числа, дефинирани чрез формулите:

- f₁(0) = 1; f₁(k) = 2*f₁(k-1) + 3; f₁ = {1, 5, 13, 29, …}

- f₂(0) = 2; f₂(k) = 3*f₂(k-1) + 1; f₂= {2, 7, 22, 67, …}

- f₃(0) = 2; f₃(k) = 2*f₃(k-1) - 1; f₃= {2, 3, 5, 9, …}

Напишете програма, която намира сечението и обединението на множествата от членовете на редиците в интервала [0; 100000]: f₁* f₂; f₁* f₃; f₂* f₃; f₁ * f₂ * f₃; f₁+ f₂; f₁+ f₃; f₂+ f₃; f₁ + f₂ + f₃. Със символите + и * означаваме съответно обединение и сечение на множества.

7. * Дефинирайте клас TreeMultiSet<T>, който позволява да пазим съвкупност от елементи, подредени по големина и позволява повторения на някои от елементите. Реализирайте операциите добавяне на елемент, търсене на броя срещания на даден елемент, изтриване на елемент, итератор, намиране на най-малък / най-голям елемент, изтриване на най-малък / най-голям елемент. Реализирайте възможност за подаване на външен Comparator<T> за сравнение на елементите.

8. * Даден е списък с времената на пристигане и заминаване на всички автобуси от дадена автогара. Да се напише програма, която използвайки TreeSet и HashSet класовете по даден интервал (начало, край) намира броя автобуси, които успяват да пристигнат и да напуснат автогарата. Пример:

Имаме данните за следните автобуси: [08:24-08:33], [08:20-09:00], [08:32-08:37], [09:00-09:15]. Даден е интервалът [08:22-09:05]. Броят автобуси, които идват и си тръгват в рамките на този интервал е 2.

9. * Дадена е редица P с цели числа (1 < P < 50 000) и число N. Щастлива подредица в редицата P наричаме всяка съвкупност, състояща се от последователни числа от P, чиято сума е N. Да си представим, че имаме редицата S, състояща се от всички щастливи подредици в P, подредени в намаляващ ред спрямо дължината им. Напишете програма, която извежда първите 10 елемента на S. Пример:

Имаме N=5 и редицата P={1, 1, 2, 1, -1, 2, 3, -1, 1, 2, 3, 5, 1, -1, 2, 3}.

Редицата S се състои от следните 13 подредици на P:

- [1, -1, 2, 3, -1, 1]

- [1, 2, 1, -1, 2]

- [1, -1, 2, 3]

- [2, 3, -1, 1]

- [3, -1, 1, 2]

- [-1, 1, 2, 3]

- [1, -1, 2, 3]

- [1, 1, 2, 1]

- [5, 1, -1]

- [2, 3]

- [2, 3]

- [5]

Първите 10 елемента на P са дадени с удебелен шрифт.

Решения и упътвания

1. Използвайте HashMap и ArrayList.

2. Използвайте за ключ и за стойност една и съща стойност – елементът от множеството.

3. Използвайте хеш-таблица от хеш-таблици.

4. Ползвайте HashMap<K, ArrayList<V>>.

5. Можете за първа хеш-функция да ползвате hashCode() % size, за втора да ползвате (hashCode() * 31 + 7) % size, a за трета – (hashCode() * hashCode() + 19) % size).

6. Намерете всички членове на трите редици в посочения интервал и след това използвайки HashSet<Integer> реализирайте обединение и сечение на множества, след което направете исканите пресмятания.

7. Класът TreeMultiSet<T> можете да реализираме чрез TreeMap<K, Integer>, който пази броя срещания на всеки от ключовете.

8. Очевидното решение е да проверим всеки от автобусите дали пристига и си тръгва в посочения интервал. Според условието на задачата, обаче, трябва да ползваме класовете TreeSet и HashSet.

Решението е такова: можем да дефинираме клас TimeInterval и да си направим две множества TreeSet<TimeInterval>, в които да пазим разписанията на автобусите, подредени съответно по час на пристигане и по час на отпътуване. Ще трябва да дефинираме и две имплементации на Comparator<TimeInterval>. Накрая можем да намерим множествата на всички автобуси, които пристигат след началния час и на всички автобуси, отпътуващи преди крайния час. Сечението на тези множества дава търсените автобуси. Сечението можем да намерим с HashSet< TimeInterval> при подходящо дефинирани hashCode() и equals().

9. Първата идея за решаване на задачата е проста: с два вложени цикъла намираме всички щастливи подредици на редицата P, след което ги сортираме по дължината им и накрая извеждаме първите 10. Това, обаче няма да работи добре, ако броят щастливи подредици са десетки милиони.

Ще опишем една идея за по-ефективно решение. Ще използваме класа TreeMultiSet<T>. В него ще съхраняваме първите 10 подредици от S, т.е. мултимножество от щастливите подредици на P, подредени по дължина в намаляващ ред. Когато имаме 10 подредици в мултимножеството и добавим нова 11-та подредица, тя ще застане на мястото си заради компаратора, който сме дефинирали. След това можем веднага да изтрием последната подредица от мултимножеството, защото тя не е сред първите 10. Така във всеки един момент ще пазим текущите 10 най-дълги подредици. По този начин ще консумираме много по-малко памет и ще избегнем сортирането накрая. Имплементацията няма да е лесна, така че отделете достатъчно време!

Дискусионен форум

Коментирайте книгата и задачите в нея във: форума на софтуерната академия.

Коментирай

Трябва да сте влезнали, за да коментирате.