Fitur TreeMap ing Jawa

Yen sampeyan maca artikel iki, kemungkinan sampeyan wis ngerti antarmuka Peta lan panggunaane. Yen ora, banjur kene sampeyan pindhah. Dina iki kita bakal ngomong babagan fitur implementasine TreeMap, lan luwih khusus, kepiye bedane karo HashMap lan cara nggunakake kanthi bener.

Perbandingan TreeMap, HashMap lan LinkedHashMap

Implementasi antarmuka Peta sing paling umum digunakake yaiku HashMap . Gampang digunakake lan njamin akses cepet menyang data, dadi calon paling apik kanggo akeh tugas. Paling, nanging ora kabeh. Kadhangkala perlu kanggo nyimpen data ing wangun terstruktur kanthi kemampuan kanggo navigasi. Ing kasus iki, implementasine liyane saka antarmuka Peta teka kanggo ngluwari - TreeMap . TreeMap ngleksanakake antarmuka NavigableMap , sing diturunake saka SortedMap , sing dadi warisan saka antarmuka Peta . Kanthi ngleksanakake antarmuka NavigableMap lan SortedMap , TreeMap entuk fungsi tambahan sing ora HashMap , nanging iki ana rega ing babagan kinerja. Ana uga kelas LinkedHashMap , sing uga ngidini sampeyan nyimpen data kanthi urutan tartamtu - miturut urutan sing ditambahake. Kanggo mbantu sampeyan ngerti bedane telung kelas kasebut, deleng tabel iki: Nalika sampeyan bisa ndeleng, kelas iki duwe akeh sing padha, nanging ana uga sawetara beda. Senajan kelas TreeMappaling multifunctional, iku ora tansah bisa disimpen nullminangka tombol. Kajaba iku, wektu akses menyang unsur TreeMap bakal paling dawa. Mulane, yen sampeyan ora perlu kanggo nyimpen data ing wangun diurutake, iku luwih apik kanggo nggunakake HashMaputawa LinkedHashMap.

Wit eboni abang

Kaya sing sampeyan ngerteni, ing ngisor tutup TreeMapkasebut nggunakake struktur data sing diarani wit abang-ireng. Panyimpenan data ing struktur iki sing njamin supaya data disimpen. Apa wit iki? Ayo dipikirake! Bayangake sampeyan kudu nyimpen pasangan Number-String. Nomer 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101 bakal dadi kunci. Yen sampeyan nyimpen data ing dhaptar tradisional lan kudu nemokake unsur karo tombol 101, sampeyan kudu ngubengi kabeh 13 unsur kanggo nemokake. Kanggo 13 unsur iki ora kritis; nalika nggarap sejuta kita bakal ngalami masalah gedhe. Kanggo ngatasi masalah kasebut, programer nggunakake struktur data sing rada rumit. Mulane, ketemu wit abang-ireng!

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

Panelusuran kanggo unsur sing dibutuhake diwiwiti saka oyod wit, ing kasus kita yaiku 61. Sabanjure, perbandingan digawe karo nilai sing dibutuhake. Yen regane kurang, banjur ngiwa, yen luwih, nengen. Iki kedadeyan nganti kita nemokake nilai sing dibutuhake utawa mencet unsur kanthi nilai null(godhong wit). Werna abang lan ireng digunakake kanggo nggawe wit luwih gampang navigasi lan imbangan. Ana aturan sing kudu ditindakake nalika mbangun wit abang-ireng:

• Oyod kudu diwarnai ireng.
• Godhong wit kudu ireng.
• A simpul abang kudu loro simpul anak ireng.
• A simpul ireng bisa duwe sembarang kelenjar anak.
• Path saka simpul menyang godhong kudu ngemot nomer simpul ireng sing padha.
• Node anyar ditambahake ing panggonan godhong.

Yen sampeyan ndeleng aturan 3, 4, lan 5 bebarengan, sampeyan bisa ngerti carane simpul pewarnaan nyepetake pandhu arah liwat wit: dalan liwat kelenjar ireng tansah luwih cendhek tinimbang liwat abang. Mulane, ukuran total wit ditemtokake dening jumlah simpul ireng, lan ukuran iki diarani "dhuwur ireng". Wit abang-ireng diimplementasikake ing macem-macem basa pamrograman. Ana akeh implementasine kanggo Jawa ing Internet, mula kita ora bakal mikir babagan iki nganti suwe, nanging bakal terus kenal karo fungsi kasebut TreeMap.

Metode sing diturunake saka antarmuka SortedMap lan NavigableMap

Kaya HashMap, TreeMapiku ngleksanakake antarmuka Map, kang tegese iku TreeMapwis kabeh cara sing HashMap. Nanging ing Kajaba iku, TreeMapiku ngleksanakake antarmuka SortedMaplan NavigableMap, entuk fungsi tambahan saka wong-wong mau. SortedMap- antarmuka sing ngluwihi Maplan nambah cara sing cocog karo set data sing diurutake:

• firstKey(): ngasilake kunci unsur pisanan ing peta;
• lastKey(): ngasilake kunci saka unsur pungkasan;
• headMap(K end): ngasilake peta sing ngemot kabeh unsur sing saiki, saka wiwitan nganti unsur kanthi kunci end;
• tailMap(K start): ngasilake peta sing ngemot kabeh unsur sing saiki, diwiwiti karo unsur startlan pungkasan;
• subMap(K start, K end): ngasilake peta sing ngemot kabeh unsur sing saiki, diwiwiti karo unsur startlan diakhiri karo unsur karo tombol end.

NavigableMap- antarmuka sing ngluwihi SortedMaplan nambah cara kanggo navigasi antarane unsur peta:

• firstEntry(): ngasilake pasangan kunci-nilai pisanan;
• lastEntry(): ngasilake pasangan kunci-nilai pungkasan;
• pollFirstEntry(): bali lan mbusak pasangan pisanan;
• pollLastEntry(): bali lan mbusak pasangan pungkasan;
• ceilingKey(K obj): Ngasilake tombol k cilik sing luwih gedhe utawa padha karo tombol obj. Yen ora ana tombol kuwi, bali null;
• floorKey(K obj): Ngasilake kunci paling gedhe k sing kurang saka utawa padha karo tombol obj. Yen ora ana tombol kuwi, bali null;
• lowerKey(K obj): Ngasilake kunci paling gedhe k sing luwih cilik tinimbang tombol obj. Yen ora ana tombol kuwi, bali null;
• higherKey(K obj): Ngasilake kunci paling cilik k sing luwih gedhe tinimbang tombol obj. Yen ora ana tombol kuwi, bali null;
• ceilingEntry(K obj): padha cara ceilingKey (K obj), nanging ngasilake pasangan tombol-nilai (utawa null);
• floorEntry(K obj): padha karo cara floorKey (K obj), nanging ngasilake pasangan kunci-nilai (utawa null);
• lowerEntry(K obj): padha karo cara lowerKey (K obj), nanging ngasilake pasangan kunci-nilai (utawa null);
• higherEntry(K obj): padha karo cara higherKey (K obj), nanging ngasilake pasangan kunci-nilai (utawa null);
• descendingKeySet(): ngasilake NavigableSet sing ngemot kabeh tombol sing diurutake kanthi urutan mbalikke;
• descendingMap(): ngasilake NavigableMap sing ngemot kabeh pasangan sing diurutake kanthi urutan mbalikke;
• navigableKeySet(): ngasilake obyek NavigableSet sing ngemot kabeh tombol ing urutan panyimpenan;
• headMap(K upperBound, boolean incl): ngasilake peta sing ngemot pasangan saka awal kanggo unsur upperBound. Argumentasi incl nemtokake manawa unsur upperBound kudu dilebokake ing peta bali;
• tailMap(K lowerBound, boolean incl): fungsi padha karo cara sadurunge, mung pasangan saka lowerBound kanggo mburi bali;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Kaya ing cara sadurunge, pasangan saka lowerBound kanggo upperBound bali, bantahan lowIncl lan highIncl nuduhake apa kudu kalebu unsur wates ing peta anyar.

Ing implementasine dhewe TreeMap, saliyane konstruktor sing kita kenal, ditambahake siji liyane, sing nampa conto komparator. Comparator iki bakal tanggung jawab kanggo urutan kang unsur disimpen.

Conto nggunakake TreeMap

Cara tambahan sing kaya ngono bisa uga ora perlu, nanging asring banget migunani tinimbang sing katon. Ayo ndeleng conto iki karo sampeyan. Bayangake yen kita kerja ing departemen pemasaran perusahaan gedhe, lan kita duwe database wong sing pengin dituduhake pariwara. Ana rong nuansa kanggo iki:

• kita kudu nglacak jumlah tayangan kanggo saben wong;
• Algoritma kanggo nampilake iklan kanggo bocah cilik beda.

Ayo nggawe kelas Personsing bakal nyimpen kabeh informasi sing kasedhiya kanggo kita babagan wong:

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;
   }
}

Kita ngetrapake logika ing kelas 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){}
}

Ing kelas Mainkita nggawe TreeMap, ngendi keyiku wong tartamtu, lan valuenomer tayangan iklan sasi iki. Ing konstruktor kita ngliwati komparator sing bakal ngurutake wong miturut umur. Isi karo mapnilai acak. Saiki kita kudu njaluk referensi kanggo wong diwasa pisanan ing nyimpen data mini kita. Kita nindakake iki nggunakake Stream API. Sawise iki, kita entuk rong peta independen, sing diterusake menyang metode sing nampilake pariwara. Ana akeh, akeh cara kanggo ngatasi masalah iki. Arsenal metode kelas TreeMapngidini sampeyan nemokake solusi sing cocog karo saben rasa. Ora perlu ngelingi kabeh, amarga sampeyan bisa nggunakake dokumentasi utawa pitunjuk saka lingkungan pangembangan. Iku kabeh! Mugi kelas saiki TreeMapcetha kanggo sampeyan, lan sampeyan bakal nemokake aplikasi sing tepat kanggo ngrampungake masalah praktis.