SortedMap

SortedMap

Sa araling ito, pag-aaralan natin ang interface ng SortedMap . Mag-e-explore kami ng mga bagong pamamaraan na lumalabas sa interface na ito, pati na rin ang mga feature ng isang pagpapatupad ng SortedMap — TreeMap — at ang mga pagkakaiba sa pagitan ng mga pagpapatupad, pati na rin ang kanilang mga pakinabang kumpara sa HashMap .

Tingnan natin kung ano ang hitsura ng hierarchy ng mga mapa. Bigyang-pansin ang interface ng SortedMap at ang pagpapatupad ng TreeMap nito — sila ang ating pokus ngayon:

Pinapalawak ng interface ng SortedMap ang interface ng Map . Sa maraming paraan, ito ay katulad ng SortedSet (na kung saan ay umaabot sa Set ), dahil pareho silang naglalarawan ng magkatulad na pag-andar para sa pag-iimbak at paggamit ng mga pinagsunod-sunod na halaga.

Gumagana ang SortedSet at nag-iimbak ng <TValue>ng mga bagay, ngunit ang SortedMap ay nag-iimbak ng<TKey, TValue>ng mga pares. Ito ay isang mapa na nag-iimbak ng lahat ng elemento nito sa pataas na pagkakasunud-sunod ng kanilang mga susi.

Ang interface ng SortedMap ay nagpapalawak ng Map . Nagdaragdag ito ng mga sumusunod na pamamaraan:

klase ng TreeMap

Ang klase ng TreeMap ay isang pagpapatupad ng interface ng SortedMap . Iyon ay, ipinapatupad ng TreeMap ang lahat ng mga pamamaraan na idinagdag ng SortedMap pati na rin ang mga karaniwang mula sa interface ng Map .

Maaari kang lumikha ng isang bagay na TreeMap gamit ang mga konstruktor tulad nito:

• TreeMap() : lumilikha ng isang walang laman na mapa na ipinatupad bilang isang puno;

• TreeMap(Map<? extends TKey, ? extends TValue> map) : lumilikha ng puno at idinaragdag ang lahat ng elemento mula sa input map;

• TreeMap(SortedMap<TKey, ? extends TValue> smap) : lumilikha ng isang puno at nagdaragdag ng lahat ng elemento mula sa input sorted map;

• TreeMap(Comparator<? super TKey> comparator) : lumilikha ng walang laman na puno — ang comparator ay gagamitin upang pag-uri-uriin ang lahat ng mga elemento habang ang mga ito ay kasunod na idinaragdag.

Narito ang TKey ay ang uri ng mga susi sa mga nakaimbak na pares, at ang TValue ay ang uri ng mga halaga sa mga pares na nakaimbak sa TreeMap .

Ang comparator ay medyo mahalaga para sa SortedMap / TreeMap . Itinatag nito ang mga panuntunan para sa pag-uuri — o pag-order — sa aming mapa. Kung hindi kami magbibigay ng comparator, ang natural na pagkakasunud-sunod ng aming mga key ay gagamitin kapag gumawa kami ng SortedMap .

Pagdaragdag ng mga elemento sa isang TreeMap

Ang mga elemento ay idinaragdag sa isang mapa bilang mga pares gamit ang put() na paraan. Ang susi ay ipinasa bilang ang unang argumento, at ang halaga ay ipinasa bilang ang pangalawa. Halimbawa, ipagpalagay na gusto naming lumikha ng isang listahan ng mga mag-aaral at ang kanilang mga marka.

SortedMap<String, Integer> map =new TreeMap <String,Integer>();

map.put("Anthony", 5);
map.put("Sara", 5);
map.put("Roxy", 5);
map.put("Jeff", 4);
map.put("Nick", 4);
map.put("Oliver", 3);
map.put("Oliver", 5);

System.out.println(map);

Resulta:

Kapag nagdagdag kami ng key-value pair, kung ang key ay mayroon na sa koleksyon, ang lumang value ay papalitan ng bagong value. Ang pag-uugali na ito ay inilalarawan sa aming halimbawa na may dalawang pares na may parehong susi — ("Oliver", 3) at ("Oliver", 5) .

Tingnan natin ang isang halimbawa sa isang Comparator na aming nilikha. Ipagpalagay na gusto naming iimbak ang mga elemento na pinagsunod-sunod ayon sa haba ng key string. Kung ang haba ng mga susi ay pantay, pagkatapos ay pag-uuri-uriin namin ayon sa alpabeto (ang natural na pagkakasunud-sunod ng mga string):

class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

SortedMap<String, Integer> lengthComparedMap = new TreeMap<String, Integer>(new LengthComparator());

lengthComparedMap.put("Jeff", 4);
lengthComparedMap.put("Oliver", 5);
lengthComparedMap.put("Roxy", 4);
lengthComaredMap.put("Jan", 4);

Narito ang resultang sequence:

Ang gawi na ito ay gumagawa ng TreeMap na parang pinagsunod-sunod na hanay o listahan na ang mga indeks ay mga salita ( String ) sa halip na mga numero.

Mga pamamaraan ng SortedMap sa klase ng TreeMap

1. Kung kailangan mong kunin ang susi ng unang mag-aaral, maaari mong gamitin ang firstKey() na paraan:

   String firstKey = map.firstKey();
   	System.out.println("First key → " + firstKey);

   Resulta: Unang susi → Anthony

2. Kung kailangan mong kunin ang susi ng huling estudyante, maaari mong gamitin ang lastKey() na pamamaraan:

   String lastKey = map.lastKey();
   System.out.println("Last key → " + lastKey);

   Resulta: Huling Susi → Jeff

3. Kunin ang lahat ng mga bagay na kasunod ng bagay na may susi na " Sara ":

   Map<String, Integer> tailMap = map.tailMap("Sara");
            	System.out.println("tailMap: " + tailMap);

   Resulta: tailMap: {Sara=5, Jeff=4}

4. Kunin ang lahat ng mga bagay na nauuna sa bagay na may susi na " Nick ":

   System.out.println("headMap: " + headMap);
    Map<String, Integer> headMap = map.headMap("Nick");

   Resulta: headMap: {Anthony=5}

5. Kunin ang lahat ng bagay na kasunod ng bagay na may susi na " Oliver " at unahan ang bagay na may susi na " Sara ":

   Map<String, Integer> subMap = map.subMap("Oliver", "Sara");
   System.out.println("subMap: " + subMap);

   Resulta: subMap: {Oliver=5, Roxy=5}

Paghahambing ng HashMap at SortedMap/TreeMap

Pag-usapan natin kung paano inayos at iniimbak ang mga elemento:

• Dahil ang HashMap ay hindi nagbibigay sa amin ng anumang mga garantiya tungkol sa order kapag umuulit, ang order ay maaaring ganap na magbago kapag ang mga bagong elemento ay idinagdag.

• Sa TreeMap , ang pagkakasunud-sunod ay batay sa "natural na pagkakasunud-sunod" ng mga susi ayon sa kanilang compareTo() na paraan (o isang Comparator na ibinibigay namin). Gayundin, huwag kalimutan na ang TreeMap ay nagpapatupad ng SortedMap interface, na naglalaman ng mga pamamaraan na nakadepende sa ganitong pagkakasunud-sunod.

Ngayon ay bumaling tayo sa isang pagsasaalang-alang sa pagganap at bilis:

• Ang HashMap ay isang mapa batay sa mga hashing key. Maaari itong magpasok at makakuha ng mga elemento saO(1), pare-parehong oras. Upang suportahan ito, ang mga susi ay dapat magpatupad nghashCode()atequals().

• Ang TreeMap ay isang tree-based na mapa. Ang insert at fetch operations nito ay tumatagal ng logarithmic time, ieO(log n), na depende sa bilang ng mga elemento sa mapa. Ito ay kinakailangan upang ang mga elemento ay may isang uri ng mekanismo ng paghahambing na ibinigay ng alinman sa aming susi o isang panlabas na Comparator. Tinutukoy ng mekanismong ito ang pagkakasunud-sunod ng pag-ulit.

At ang mga salik na ito ay tumutulong sa amin na magpasya kung aling mga koleksyon ang gagamitin at kung kailan.

Kung kailangan naming mag-imbak ng mga halaga sa isang tiyak na pagkakasunud-sunod, ang pagpipilian ay halata — kailangan namin ng SortedMap . Bagama't mas mabagal ito ng kaunti kaysa sa HashMap , nagsasagawa ito ng mahahalagang gawain para sa amin.

Gaya ng nabanggit kanina, maibibigay sa amin ng SortedMap ang una (o huling) key, o value, o key-value pair sa aming mapa, kahit kailan idinagdag ang value na iyon. Hindi ito magagawa ng pagpapatupad ng HashMap .

Halimbawa, isaalang-alang ang isang mapa na may mga susi (pangalan ng mga mag-aaral) at mga halaga (kanilang mga marka). Sabihin nating gusto naming gumawa ng isang listahan sa reverse alphabetical order.

1.

SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anthony", 5);
sorted.put("Sara", 5);
sorted.put("Jeff", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.

HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Anthony", 5);
hash.put("Sara", 5);
hash.put("Jeff", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Or sort manually, storing elements in an array or list (preserving the insertion order)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

Ipinapakita ng halimbawa na ang paggamit ng HashMap ay ginagawang mas kumplikado ang gawain, dahil hindi ginagarantiya ng HashMap ang pagkakasunud-sunod ng imbakan o ang pagkakasunud-sunod ng pagkuha ng mga elemento mula sa mapa.