Mga Tampok ng TreeMap sa Java

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

Paghahambing ng TreeMap, HashMap at LinkedHashMap

Ang pinakakaraniwang ginagamit na pagpapatupad ng Map interface ay HashMap . Madali itong gamitin at ginagarantiyahan ang mabilis na pag-access sa data, na ginagawa itong pinakamahusay na kandidato para sa karamihan ng mga gawain. Karamihan, ngunit hindi lahat. Minsan kinakailangan na mag-imbak ng data sa isang structured na form na may kakayahang mag-navigate dito. Sa kasong ito, isa pang pagpapatupad ng interface ng Map ang sasagipin - TreeMap . Ipinapatupad ng TreeMap ang interface ng NavigableMap , na nagmamana mula sa SortedMap , na namamana naman mula sa interface ng Map . Sa pamamagitan ng pagpapatupad ng mga interface ng NavigableMap at SortedMap , nakakakuha ang TreeMap ng karagdagang functionality na hindi ginagawa ng HashMap , ngunit ito ay may presyo sa mga tuntunin ng pagganap. Mayroon ding LinkedHashMap class , na nagpapahintulot din sa iyo na mag-imbak ng data sa isang tiyak na pagkakasunud-sunod - sa pagkakasunud-sunod ng mga ito ay idinagdag. Upang matulungan kang maunawaan ang mga pagkakaiba sa pagitan ng tatlong klaseng 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 TreeMapay ang pinaka-multifunctional, hindi ito palaging maiimbak nullbilang isang susi. Bilang karagdagan, ang oras ng pag-access sa mga elemento ng TreeMap ang magiging pinakamatagal. Samakatuwid, kung hindi mo kailangang mag-imbak ng data sa pinagsunod-sunod na anyo, mas mainam na gamitin HashMapo LinkedHashMap.

Puno ng pulang ebony

Tulad ng malamang na napansin mo, sa ilalim ng hood TreeMapay gumagamit ito ng istraktura ng data na tinatawag na pulang-itim na puno. Ito ay ang pag-iimbak ng data sa istrukturang ito na nagsisiguro sa pagkakasunud-sunod kung saan ang data ay naka-imbak. Ano ang punong 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, 101 ang magiging mga susi. Kung mag-imbak ka ng data sa isang tradisyunal na listahan at kailangan mong maghanap ng elementong may key 101, kakailanganin mong ulitin ang lahat ng 13 elemento upang mahanap ito. Para sa 13 elemento hindi ito kritikal; kapag nagtatrabaho sa isang milyon magkakaroon tayo ng malalaking problema. Upang malutas ang mga naturang problema, ang mga programmer ay gumagamit ng bahagyang mas kumplikadong mga istruktura ng data. Samakatuwid, salubungin ang pulang-itim na puno!

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

Ang paghahanap para sa kinakailangang elemento ay nagsisimula mula sa ugat ng puno, sa aming kaso ito ay 61. Susunod, ang isang paghahambing ay ginawa gamit ang kinakailangang halaga. Kung ang ating halaga ay mas mababa, pumunta tayo sa kaliwa, kung ito ay higit pa, tayo ay pupunta sa kanan. Nangyayari ito hanggang sa makita namin ang kinakailangang halaga o maabot ang isang elemento na may halaga null(isang dahon ng isang puno). Ang pula at itim na mga kulay ay ginagamit upang gawing mas madaling i-navigate at balanse ang puno. Mayroong mga patakaran na dapat palaging sundin kapag nagtatayo ng pulang-itim na puno:

• Ang ugat ay dapat na kulay 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 anumang mga child node.
• Ang 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 bilang kapalit ng mga dahon.

Kung titingnan mo ang mga panuntunan 3, 4, at 5 nang magkasama, mauunawaan mo kung paano pinapabilis ng mga pangkulay na node ang pag-navigate sa puno: ang landas sa mga itim na node ay palaging mas maikli kaysa sa mga pulang node. Samakatuwid, ang kabuuang sukat ng puno ay tinutukoy ng bilang ng mga itim na node, at ang laki na ito ay tinatawag na "itim na taas". Ang pulang-itim na puno ay ipinatupad sa iba't ibang mga programming language. Mayroong maraming mga pagpapatupad para sa Java sa Internet, kaya't hindi namin ito tatalakayin nang matagal, ngunit patuloy na makikilala ang pagpapagana TreeMap.

Mga pamamaraan na nagmula sa mga interface ng SortedMap at NavigableMap

Tulad ng HashMap, TreeMapito ay nagpapatupad ng interface Map, na nangangahulugan na ito TreeMapay may lahat ng mga pamamaraan na HashMap. Ngunit bilang karagdagan, TreeMapnagpapatupad ito ng mga interface SortedMapat NavigableMap, pagkuha ng karagdagang pag-andar mula sa kanila. SortedMap— isang interface na nagpapalawak Mapat nagdaragdag ng mga pamamaraan na nauugnay sa isang pinagsunod-sunod na set ng data:

• firstKey(): ibinabalik ang susi ng unang elemento ng mapa;
• lastKey(): ibinabalik ang susi ng huling elemento;
• headMap(K end): nagbabalik ng isang mapa na naglalaman ng lahat ng mga elemento ng kasalukuyang isa, mula sa simula hanggang sa elemento na may susi end;
• tailMap(K start): nagbabalik ng mapa na naglalaman ng lahat ng elemento ng kasalukuyang isa, simula sa elemento startat nagtatapos sa dulo;
• subMap(K start, K end): nagbabalik ng isang mapa na naglalaman ng lahat ng mga elemento ng kasalukuyang isa, na nagsisimula sa elemento startat nagtatapos sa elemento na may susi end.

NavigableMap— isang interface na nagpapalawak SortedMapat nagdaragdag ng mga pamamaraan para sa pag-navigate sa pagitan ng mga elemento ng mapa:

• firstEntry(): ibinabalik ang unang key-value pair;
• lastEntry(): ibinabalik ang huling key-value pair;
• pollFirstEntry(): ibinabalik at inaalis ang unang pares;
• pollLastEntry(): ibinabalik at inaalis 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 maliit 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, ngunit nagbabalik ng key-value pair (o null);
• floorEntry(K obj): katulad ng floorKey(K obj) na paraan, ngunit nagbabalik ng key-value pair (o null);
• lowerEntry(K obj): katulad ng lowerKey(K obj) na paraan, ngunit nagbabalik ng key-value pair (o null);
• higherEntry(K obj): katulad ng higherKey(K obj) na paraan, ngunit nagbabalik 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 mga pares na pinagsunod-sunod sa reverse order;
• navigableKeySet(): nagbabalik ng NavigableSet object na naglalaman ng lahat ng mga susi sa pagkakasunud-sunod ng imbakan;
• headMap(K upperBound, boolean incl): nagbabalik ng mapa na naglalaman ng mga pares mula sa simula hanggang sa upperBound na elemento. Ang incl argument ay tumutukoy kung ang upperBound na elemento ay dapat isama sa ibinalik na mapa;
• tailMap(K lowerBound, boolean incl): ang functionality ay katulad ng nakaraang pamamaraan, ang mga pares lamang mula lowerBound hanggang sa dulo ang ibinalik;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Tulad ng sa mga nakaraang pamamaraan, ang mga pares mula lowerBound hanggang upperBound ay ibinalik, ang mga argumento na lowIncl at highIncl ay tumutukoy kung isasama ang mga elemento ng hangganan sa bagong mapa.

Sa mismong pagpapatupad TreeMap, bilang karagdagan sa mga constructor na pamilyar sa atin, isa pa ang idinagdag, na tumatanggap ng isang halimbawa ng comparator. Ang paghahambing na ito ay magiging responsable para sa pagkakasunud-sunod kung saan iniimbak ang mga elemento.

Mga halimbawa ng paggamit ng TreeMap

Ang ganitong kasaganaan ng mga karagdagang pamamaraan ay maaaring mukhang hindi kailangan, ngunit kadalasan sila ay nagiging mas kapaki-pakinabang kaysa sa una. Tingnan natin ang halimbawang ito kasama mo. Isipin na nagtatrabaho kami sa departamento ng marketing ng isang malaking kumpanya, at mayroon kaming database ng mga taong gusto naming magpakita ng advertising. Mayroong dalawang mga nuances dito:

• kailangan nating subaybayan ang bilang ng mga impression sa bawat tao;
• Iba ang algorithm para sa pagpapakita ng advertising sa mga menor de edad.

Gumawa tayo ng klase Personna mag-iimbak ng lahat ng impormasyong magagamit natin tungkol sa isang 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 klase Main:

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("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 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 klase Mainna nilikha namin TreeMap, kung saan keyang isang partikular na tao, at valueang bilang ng mga ad impression sa buwang ito. Sa constructor pumasa kami ng isang comparator na mag-uuri ng mga tao ayon sa edad. Punan ng mapmga random na halaga. Ngayon ay kailangan naming kumuha ng reference sa unang adult sa aming mini data store. Ginagawa namin ito gamit ang Stream API. Pagkatapos nito, nakakakuha kami ng dalawang independiyenteng mapa, na ipinapasa namin sa mga pamamaraan na nagpapakita ng advertising. Mayroong maraming, maraming mga paraan kung saan maaaring malutas ang problemang ito. Ang arsenal ng mga pamamaraan ng klase TreeMapay nagpapahintulot sa iyo na mag-imbento ng mga solusyon na angkop sa bawat panlasa. Hindi kinakailangang tandaan ang lahat, dahil maaari mong palaging gamitin ang dokumentasyon o mga pahiwatig mula sa kapaligiran ng pag-unlad. Iyon lang! Sana ay TreeMapmalinaw na sa iyo ang klase, at makakahanap ka ng tumpak na aplikasyon para dito sa paglutas ng mga praktikal na problema.