TreeMap sa Java

Kung binabasa mo ang artikulong ito, malamang na pamilyar ka sa interface ng Map at kung saan naaangkop na mailalapat. Kung hindi, pumunta ka dito . Ngayon ay pag-uusapan natin ang tungkol sa mga tampok ng pagpapatupad ng Java TreeMap, at higit na partikular, kung paano ito naiiba sa HashMap at kung paano ito gamitin nang tama.

Paghahambing ng TreeMap, HashMap, at LinkedHashMap

Ang pinaka ginagamit na pagpapatupad ng Map interface ay HashMap. Ito ay madaling gamitin at ginagarantiyahan ang mabilis na pag-access sa data, kaya ito ang pinakamahusay na kandidato para sa paglutas ng karamihan sa mga problema. Karamihan, ngunit hindi lahat. Minsan kailangan mong mag-imbak ng data sa isang structured na paraan at makapag-navigate dito. Sa kasong ito, isa pang pagpapatupad ng Map interface (TreeMap) ang darating sa pagsagip. Ipinapatupad ng TreeMap ang interface ng NavigableMap , na nagmamana ng SortedMap , na namamana naman ng interface ng Map. Sa pamamagitan ng pagpapatupad ng NavigableMap at SortedMap na mga interface, ang TreeMap ay tumatanggap ng karagdagang functionality na hindi available sa HashMap, ngunit nagbabayad ito ng presyo sa mga tuntunin ng pagganap. Mayroon ding LinkedHashMapclass , na nagpapahintulot din sa iyo na mag-imbak ng data sa isang partikular na pagkakasunud-sunod (ang pagkakasunud-sunod kung saan mo ito idinaragdag sa mapa). Upang maunawaan ang mga pagkakaiba sa pagitan ng tatlong klase na ito, tingnan ang talahanayang ito: Tulad ng nakikita mo, ang mga klase na ito ay may maraming pagkakatulad, ngunit mayroon ding ilang mga pagkakaiba. Bagama't ang klase ng TreeMap ay ang pinaka maraming nalalaman, hindi ito palaging mag-imbak ng null bilang isang susi. Bilang karagdagan, ang pag-access sa mga elemento ng isang TreeMap ay tumatagal ng pinakamahabang oras. Kaya, kung hindi mo kailangang mag-imbak ng data sa ilang pinagsunod-sunod na pagkakasunud-sunod, mas mainam na gamitin ang HashMap o LinkedHashMap .

Pula-itim na puno

Marahil ay napansin mo na, sa ilalim ng hood, ang TreeMap ay gumagamit ng isang istraktura ng data na tinatawag na isang pulang-itim na puno. Ang pag-iimbak ng data sa istrukturang ito ay tiyak na nagbibigay ng pag-order ng data. Kaya anong uri ng puno ito? Alamin natin ito! Isipin na kailangan mong mag-imbak ng mga pares ng Number-String. Ang mga numerong 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, at 101 ay magiging mga susi. Kung mag-imbak ka ng data sa isang tradisyunal na listahan at kailangan mong hanapin ang elementong may key 101, kakailanganin mong dumaan sa lahat ng 13 elemento upang mahanap ito. Para sa 13 elemento, hindi ito malaking bagay, ngunit kapag nagtatrabaho sa isang milyon, magkakaroon tayo ng malalaking problema. Upang malutas ang mga problemang ito, ang mga programmer ay gumagamit ng bahagyang mas kumplikadong mga istruktura ng data. Dito pumapasok sa entablado ang pulang-itim na puno!Ang paghahanap para sa isang elemento ay nagsisimula sa ugat ng puno, na sa aming kaso ay 61. Pagkatapos ay ihahambing namin ang mga halaga ng node sa halaga na aming hinahanap. Kung ang aming halaga ay mas mababa, pagkatapos ay pumunta kami sa kaliwa; kung ito ay mas malaki, pagkatapos ay pumunta kami sa kanan. Umuulit ang prosesong ito hanggang sa makita natin ang nais na halaga o makatagpo ng isang elemento na ang halaga ay null (isang dahon ng puno). Ang mga kulay na pula at itim ay ginagamit upang pasimplehin ang pag-navigate at pagbabalanse sa puno. Mayroong mga patakaran na dapat palaging sundin kapag nagtatayo ng isang pulang-itim na puno:

• Ang ugat ay dapat na itim.
• Ang mga dahon ng puno ay dapat na itim.
• Ang pulang node ay dapat may dalawang itim na child node.
• Ang isang itim na node ay maaaring magkaroon ng mga child node ng anumang kulay.
• Ang isang landas mula sa isang node patungo sa mga dahon nito ay dapat maglaman ng parehong bilang ng mga itim na node.
• Ang mga bagong node ay idinagdag sa mga dahon.

Kung isasaalang-alang mo ang Mga Panuntunan 3, 4 at 5 nang magkasama, mauunawaan mo kung paano nagbibigay-daan sa amin ang kulay ng node na mag-navigate sa puno nang mas mabilis: ang isang landas sa mga itim na node ay palaging mas maikli kaysa sa isa sa pamamagitan ng mga pulang node. Alinsunod dito, ang kabuuang sukat ng puno ay tinutukoy ng bilang ng mga itim na node, na tinatawag na "itim na taas". Ang istraktura ng data ng red-black tree ay ipinatupad sa iba't ibang mga programming language. Maraming mga pagpapatupad ng Java sa Internet, kaya hindi kami magtatagal dito. Sa halip, patuloy nating kilalanin ang functionality ng TreeMap.

Mga pamamaraan na nagmumula sa mga interface ng SortedMap at NavigableMap

Tulad ng HashMap, ipinapatupad ng TreeMap ang interface ng Map, na nangangahulugang nasa TreeMap ang lahat ng mga pamamaraan na umiiral sa HashMap. Ngunit ipinapatupad din ng TreeMap ang mga interface ng SortedMap at NavigableMap , at sa gayon ay nakakakuha ng karagdagang functionality mula sa kanila. Ang SortedMap ay isang interface na nagpapalawak ng Map at nagdaragdag ng mga pamamaraan na nauugnay sa isang pinagsunod-sunod na dataset:

• firstKey() : ibinabalik ang susi ng unang elemento sa mapa
• lastKey() : ibinabalik ang susi ng huling elemento
• headMap(K end) : nagbabalik ng mapa na naglalaman ng lahat ng elemento ng kasalukuyang mapa, mula sa simula hanggang sa elementong may key na dulo
• tailMap(K start) : nagbabalik ng mapa na naglalaman ng lahat ng elemento ng kasalukuyang mapa, mula sa panimulang elemento hanggang sa dulo
• subMap(K start, K ​​end) : nagbabalik ng mapa na naglalaman ng lahat ng elemento ng kasalukuyang mapa, mula sa panimulang elemento hanggang sa elementong may pangunahing dulo.

Ang NavigableMap ay isang interface na nagpapalawak ng SortedMap at nagdaragdag ng mga pamamaraan para sa pag-navigate sa pagitan ng mga elemento ng isang mapa:

• firstEntry() : ibinabalik ang unang key-value pair
• lastEntry() : ibinabalik ang huling key-value pair
• pollFirstEntry() : ibinabalik at tinatanggal ang unang pares
• pollLastEntry() : ibinabalik at tinatanggal ang huling pares
• ceilingKey(K obj) : ibinabalik ang pinakamaliit na key k na mas malaki sa o katumbas ng key obj. Kung walang ganoong susi, nagbabalik ng null
• floorKey(K obj) : ibinabalik ang pinakamalaking key k na mas mababa sa o katumbas ng key obj. Kung walang ganoong susi, nagbabalik ng null
• lowerKey(K obj) : ibinabalik ang pinakamalaking key k na mas mababa sa key obj. Kung walang ganoong susi, nagbabalik ng null
• higherKey(K obj) : ibinabalik ang pinakamaliit na key k na mas malaki kaysa sa key obj. Kung walang ganoong susi, nagbabalik ng null
• ceilingEntry(K obj) : katulad ng ceilingKey(K obj) method, nagbabalik lamang ng key-value pair (o null)
• floorEntry(K obj) : katulad ng floorKey(K obj) na paraan, nagbabalik lang ng key-value pair (o null)
• lowerEntry(K obj) : katulad ng lowerKey(K obj) na paraan, nagbabalik lamang ng key-value pair (o null)
• higherEntry(K obj) : katulad ng higherKey(K obj) na paraan, nagbabalik lamang ng key-value pair (o null)
• descendingKeySet() : nagbabalik ng NavigableSet na naglalaman ng lahat ng mga key na pinagsunod-sunod sa reverse order
• descendingMap() : nagbabalik ng NavigableMap na naglalaman ng lahat ng pares na pinagsunod-sunod sa reverse order
• navigableKeySet() : nagbabalik ng NavigableSet object na naglalaman ng lahat ng mga key sa pagkakasunud-sunod kung saan naka-imbak ang mga ito
• headMap(K upperBound, boolean incl) : nagbabalik ng mapa na naglalaman ng mga pares mula sa simula hanggang sa upperBound na elemento. Isinasaad ng incl parameter kung isasama ang upperBound na elemento sa ibinalik na mapa
• tailMap(K lowerBound, boolean incl) : functionality na katulad ng nakaraang pamamaraan, nagbabalik lamang ng mga pares mula lowerBound hanggang sa dulo
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl) : tulad ng mga nakaraang pamamaraan, nagbabalik ng mga pares mula lowerBound hanggang upperBound; ang mga argumento na lowIncl at highIncl ay nagpapahiwatig kung isasama ang mga elemento ng hangganan sa bagong mapa.

Bilang karagdagan sa mga karaniwang constructor, ang TreeMap ay may isa pang constructor na tumatanggap ng isang instance ng isang comparator. Ang paghahambing na ito ay may pananagutan para sa pagkakasunud-sunod kung saan iniimbak ang mga elemento.

Mga halimbawa ng TreeMap

Ang kasaganaan ng mga karagdagang pamamaraan na ito ay maaaring mukhang hindi kailangan, ngunit ang mga ito ay nagiging mas kapaki-pakinabang kaysa sa maaari mong mapagtanto sa unang tingin. Sama-sama nating galugarin ang sumusunod na halimbawa. Isipin na nagtatrabaho kami sa departamento ng marketing ng isang malaking kumpanya, at mayroon kaming database ng mga tao na gusto naming magpakita ng mga ad. Mayroong dalawang detalye na dapat tandaan:

• Kailangan nating subaybayan ang bilang ng mga impression para sa bawat tao
• Iba ang algorithm para sa pagpapakita ng mga ad sa mga menor de edad.

Gumawa tayo ng klase ng Tao , na mag-iimbak ng lahat ng nauugnay na impormasyon tungkol sa bawat tao:

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

Ipinapatupad namin ang lohika sa Pangunahing klase:

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map) {}
   public static void showAdvertisementToAdult(Map map) {}
}

Sa Pangunahing klase, lumikha ng TreeMap, kung saan ang bawat key ay kumakatawan sa isang partikular na tao, at ang bawat halaga ay ang bilang ng mga ad impression sa buwang ito. Ipapasa namin sa constructor ang isang comparator na nag-uuri ng mga tao ayon sa edad. Pinupuno namin ang mapa ng mga arbitrary na halaga. Ngayon gusto naming makakuha ng reference sa unang adult sa aming maliit na imbakan ng data. Ginagawa namin ito gamit ang Stream API. Pagkatapos ay nakakakuha kami ng dalawang magkahiwalay na mapa, na ipinapasa namin sa mga pamamaraan na nagpapakita ng mga ad. Mayroong maraming, maraming mga paraan upang maisagawa natin ang gawaing ito. Ang arsenal ng mga pamamaraan ng klase ng TreeMap ay nagbibigay-daan sa amin na lumikha ng mga custom na solusyon para sa bawat pangangailangan. Hindi mo kailangang tandaan ang lahat ng ito, dahil maaari mong palaging gamitin ang dokumentasyon o mga tip mula sa iyong IDE. Upang palakasin ang iyong natutunan, iminumungkahi naming manood ka ng isang video lesson mula sa aming Java Course Yun lang muna! Umaasa ako na ang klase ng TreeMap ay malinaw na sa iyo ngayon, at ilalapat mo ito nang maayos sa paglutas ng mga praktikal na gawain sa coding.