Глава 18. Речници, хеш-таблици и множества

Автор

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

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

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

Съдържание


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

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

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

clip_image002

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

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

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

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

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

При структурата речник този ключ може да на е просто номерче, а всяка­къв друг обект. В случая, когато имаме ключ (номер), можем да реа­лизи­раме такава структура като обикновен масив. Тогава множеството от ключове е предварително ясно – числата от 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 – имплементация с хеш-таблица.

clip_image002[1]

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

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

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

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

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

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

clip_image002[2]

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

Класът 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>. То гласи следното:

clip_image002[3]

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

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

Хеш-таблици

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

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

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

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

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

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

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

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

clip_image004

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

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

index = hash(key) % m

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

clip_image006

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

clip_image002[4]

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

Капацитетът на таблицата се увеличава, когато броят на наредените двойки в хеш-таблицата стане равен или по-голям от дадена константа, наречена максимална степен на запълване (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) = s0*31n-1 + s1*31n-2 + … + sn

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

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

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

@Override

public int hashCode() {

    return 53;

}

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

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

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

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

clip_image008

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

clip_image010

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

Имплементиране на метода 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() не е реализиран напълно коректно, но проблемът трудно може да се прояви. Наистина в пове­чето случаи тази реализация ще работи без проблем. Но какво ще стане, ако добавяме елементи до безкрай? В един прекрасен момент, когато капацитетът е станал 231 и се наложи да го разширим, то при умножение на това число с 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 от позицията, в която имаме колизия.

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

clip_image002[5]

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

Квадратично пробване (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 година. Името му идва от поведението, наблюдавано при някои видове кукувици. Майките кукувици избутват яйца и/или малките на други птици извън гнездото им, за да оставят техните яйца там и така други птици да се грижат за техните яйца (и малки след излюпването).

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

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

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

clip_image012

Нека също предположим, че това е клетката, в която се намира 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:

accept

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.  Дадени са три редици от числа, дефинирани чрез формулите:

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

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

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

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

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]

-     [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 най-дълги подредици. По този начин ще консумираме много по-малко памет и ще избегнем сортирането накрая. Имплементацията няма да е лесна, така че отделете достатъчно време!

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

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

Share

Коментирай