1. Общ преглед
В тази статия ще изследваме внедряването на TreeMap на интерфейса Map от Java Collections Framework (JCF).
TreeMap е реализация на карта, която запазва записите си сортирани според естественото подреждане на ключовете си или още по-добре, използвайки сравнител, ако е предоставен от потребителя по време на изграждането.
По-рано разгледахме внедряванията на HashMap и LinkedHashMap и ще разберем, че има доста малко информация за това как работят тези класове, която е подобна.
Споменатите статии са силно препоръчителни за четене, преди да продължите с тази.
2. Сортиране по подразбиране в TreeMap
По подразбиране TreeMap сортира всички свои записи според естествения им ред. За цяло число това би означавало възходящ ред, а за низове - азбучен ред.
Нека да видим естественото подреждане в тест:
@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() { TreeMap map = new TreeMap(); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString()); }Забележете, че поставихме целочислените ключове по неподреден начин, но при извличането на набора ключове потвърждаваме, че те наистина се поддържат във възходящ ред. Това е естественото подреждане на цели числа.
По същия начин, когато използваме низове, те ще бъдат сортирани в естествения им ред, т.е. по азбучен ред:
@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2() { TreeMap map = new TreeMap(); map.put("c", "val"); map.put("b", "val"); map.put("a", "val"); map.put("e", "val"); map.put("d", "val"); assertEquals("[a, b, c, d, e]", map.keySet().toString()); }TreeMap , за разлика от хеш картата и свързаната хеш карта, не използва принципа на хеширане никъде, тъй като не използва масив за съхраняване на записите си.
3. Персонализирано сортиране в TreeMap
Ако не сме доволни от естественото подреждане на TreeMap , можем също да дефинираме нашето собствено правило за подреждане с помощта на компаратор по време на изграждането на дървовидна карта.
В примера по-долу искаме целочислените ключове да бъдат подредени в низходящ ред:
@Test public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() { TreeMap map = new TreeMap(Comparator.reverseOrder()); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString()); }Хеш картата не гарантира реда на съхранените ключове и по-конкретно не гарантира, че тази поръчка ще остане същата с течение на времето, но дървовидната карта гарантира, че ключовете винаги ще бъдат сортирани според посочения ред.
4. Значение на сортирането на TreeMap
Сега знаем, че TreeMap съхранява всички свои записи в сортиран ред. Поради този атрибут на дървесни карти можем да изпълняваме заявки като; намери „най-голям“, намери „най-малък“, намери всички ключове, по-малки или по-големи от определена стойност и т.н.
Кодът по-долу обхваща само малък процент от тези случаи:
@Test public void givenTreeMap_whenPerformsQueries_thenCorrect() { TreeMap map = new TreeMap(); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); Integer highestKey = map.lastKey(); Integer lowestKey = map.firstKey(); Set keysLessThan3 = map.headMap(3).keySet(); Set keysGreaterThanEqTo3 = map.tailMap(3).keySet(); assertEquals(new Integer(5), highestKey); assertEquals(new Integer(1), lowestKey); assertEquals("[1, 2]", keysLessThan3.toString()); assertEquals("[3, 4, 5]", keysGreaterThanEqTo3.toString()); }5. Вътрешно внедряване на TreeMap
TreeMap реализира интерфейса NavigableMap и основава вътрешната си работа на принципите на червено-черните дървета:
public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, java.io.SerializableПринципът на червено-черните дървета е извън обхвата на тази статия, но има ключови неща, които трябва да запомните, за да разберете как се вписват в TreeMap .
На първо място , червено-черното дърво е структура от данни, която се състои от възли; представете обърнато мангово дърво с корен в небето и клони, растящи надолу. Коренът ще съдържа първия елемент, добавен към дървото.
Правилото е, че като се започне от корена, всеки елемент в левия клон на който и да е възел винаги е по-малък от елемента в самия възел. Тези отдясно винаги са по-големи. Това, което определя по-голямо или по-малко от това, се определя от естественото подреждане на елементите или дефинирания компаратор при изграждане, както видяхме по-рано.
Това правило гарантира, че записите на дървовидна карта винаги ще бъдат в сортиран и предвидим ред.
На второ място , червено-черното дърво е самобалансиращо се двоично дърво за търсене. Този атрибут и горното гарантират, че основните операции като търсене, извличане, пускане и премахване отнемат логаритмично време O (log n) .
Да бъдеш самобалансиран е ключово тук. Докато продължаваме да вмъкваме и изтриваме записи, си представяйте как дървото расте по-дълго на единия ръб или по-късо на другия.
Това би означавало, че една операция ще отнеме по-кратко време на по-късия клон и по-дълго време на клона, който е най-отдалечен от корена, нещо, което не бихме искали да се случи.
Ето защо за това се полагат грижи при проектирането на червено-черни дървета. За всяко вмъкване и изтриване, максималната височина на дървото на който и да е ръб се поддържа на O (log n), т.е. дървото се балансира непрекъснато.
Подобно на хеш картата и свързаната хеш карта, дървовидната карта не се синхронизира и следователно правилата за използването й в многонишкова среда са подобни на тези в другите две реализации на картата.
6. Избор на правилната карта
След като разгледахме внедряванията на HashMap и LinkedHashMap по- рано и сега TreeMap , важно е да направим кратко сравнение между трите, за да ни насочим коя къде се вписва.
Хеш картата е добра като реализация на карта с общо предназначение, която осигурява бързи операции за съхранение и извличане. Той обаче не успява поради хаотичното си и неподредено подреждане на записите.
Това го кара да се представя лошо в сценарии, при които има много итерации, тъй като целият капацитет на базовия масив влияе върху обхождането, различен от броя на записите.
Свързана хеш карта притежава добрите атрибути на хеш карти и добавя ред към записите. Той се представя по-добре там, където има много итерации, тъй като се взема предвид само броят на записите, независимо от капацитета.
Дървовидната карта отвежда подреждането на следващото ниво, като предоставя пълен контрол върху начина на сортиране на ключовете. От друга страна, той предлага по-лошо общо представяне от другите две алтернативи.
Можем да кажем, че свързана хеш карта намалява хаоса при подреждането на хеш карта, без да се налага наказание за ефективност на дървесна карта .
7. Заключение
В тази статия разгледахме класа Java TreeMap и неговата вътрешна реализация. Тъй като това е последното в поредица от общи реализации на интерфейса на Map, ние също продължихме накратко, за да обсъдим къде той се вписва най-добре спрямо другите две.
Пълният изходен код за всички примери, използвани в тази статия, може да бъде намерен в проекта GitHub.