SortedMap

ในบทเรียนนี้ เราจะศึกษาอินเทอร์เฟซSortedMap เราจะสำรวจวิธีการใหม่ๆ ที่ ปรากฏในอินเทอร์เฟซนี้ ตลอดจนคุณลักษณะของการนำSortedMap มาใช้ — TreeMap — และความแตกต่างระหว่างการนำไปใช้ ตลอดจนข้อดีเมื่อเปรียบเทียบกับHashMap

มาดูกันว่าลำดับชั้นของแผนที่เป็นอย่างไร ให้ความสนใจเป็นพิเศษกับ อินเทอร์เฟ ซ SortedMapและ การใช้งาน TreeMapซึ่งเป็นจุดสนใจของเราในวันนี้:

อินเทอร์เฟ ซ SortedMapขยายอินเทอร์เฟซแผนที่ ในหลาย ๆ ด้าน จะคล้ายกับSortedSet (ซึ่งจะขยายSet ) เนื่องจากทั้งคู่อธิบายการทำงานที่คล้ายกันสำหรับการจัดเก็บและการใช้ค่าที่เรียงลำดับ

SortedSetทำงานร่วมกับและจัดเก็บ<TValue>แต่ SortedMap จัดเก็บคู่<TKey, TValue> เป็นแผนที่ที่เก็บองค์ประกอบทั้งหมดตามลำดับคีย์จากน้อยไปหามาก

อินเท อ ร์เฟ ซ SortedMap ขยายMap มันเพิ่มวิธีการดังต่อไปนี้:

วิธี คำอธิบาย
TKey คีย์แรก () ส่งกลับคีย์ขององค์ประกอบแรกของแผนที่
TKey คีย์สุดท้าย () ส่งกลับคีย์ขององค์ประกอบสุดท้ายของแผนที่
SortedMap<TKey, TValue> headMap(สิ้นสุด TKey) ส่งกลับSortedMapที่มีองค์ประกอบทั้งหมดของSortedMap ดั้งเดิม จนถึงและรวมถึงองค์ประกอบที่มีจุดสิ้นสุด ของคีย์
SortedMap<TKey, Tvalue> tailMap (เริ่มต้น K) ส่งคืนSortedMapที่มีองค์ประกอบทั้งหมดของSortedMap ดั้งเดิม โดยเริ่มต้นที่องค์ประกอบด้วยปุ่มเริ่มต้น (รวม)
SortedMap<TKey, TValue> subMap (เริ่มต้น TKey, สิ้นสุด TKey) ส่งคืนSortedMapที่มีองค์ประกอบทั้งหมดของSortedMap ดั้งเดิม จากองค์ประกอบที่มีปุ่มเริ่มต้นไปยังองค์ประกอบที่มีปุ่มสิ้นสุด (ไม่รวมจุดสิ้นสุด)

คลาส TreeMap

คลาสTreeMapเป็นการใช้งานอินเทอร์เฟซ SortedMap นั่นคือTreeMapใช้วิธีทั้งหมดที่เพิ่มโดยSortedMapรวมถึงวิธีมาตรฐานจากส่วนต่อประสานแผนที่

Java webinar

คุณสามารถสร้าง วัตถุ TreeMapโดยใช้ตัวสร้างดังต่อไปนี้:

  • TreeMap() : สร้างแผนที่เปล่าที่ใช้เป็นต้นไม้

  • TreeMap(Map<? expands TKey, ? expands TValue> map) : สร้างแผนผังและเพิ่มองค์ประกอบทั้งหมดจากแผนที่อินพุต

  • TreeMap(SortedMap<TKey, ? extends TValue> smap) : สร้างแผนผังและเพิ่มองค์ประกอบทั้งหมดจากแผนที่จัดเรียงอินพุต

  • TreeMap(Comparator<? super TKey> comparator) : สร้างแผนผังว่าง — ตัวเปรียบเทียบจะถูกใช้เพื่อจัดเรียงองค์ประกอบทั้งหมดเมื่อมีการเพิ่มในภายหลัง

ที่นี่TKeyคือประเภทของคีย์ในคู่ที่เก็บไว้ และTValue คือประเภทของค่าในคู่ที่จัดเก็บไว้ในTreeMap

ตัวเปรียบเทียบ มีความสำคัญ มากสำหรับ SortedMap / TreeMap กำหนดกฎสำหรับการจัดเรียง — หรือลำดับ — แผนที่ของเรา หากเราไม่ได้จัดเตรียมตัวเปรียบเทียบ การเรียงลำดับปกติของคีย์ของเราจะถูกใช้เมื่อเราสร้าง SortedMap

การเพิ่มองค์ประกอบใน TreeMap

องค์ประกอบถูกเพิ่มลงในแผนที่เป็นคู่โดยใช้เมธอดput() คีย์ถูกส่งผ่านเป็นอาร์กิวเมนต์แรก และค่าจะถูกส่งเป็นอาร์กิวเมนต์ที่สอง ตัวอย่างเช่น สมมติว่าเราต้องการสร้างรายชื่อนักเรียนและเกรดของนักเรียน


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

ผลลัพธ์:

{แอนโทนี่=5, นิค=4, โอลิเวอร์=5, ร็อกซี่=5, ซาร่า=5, เจฟฟ์=4}

เมื่อเราเพิ่มคู่คีย์-ค่า หากมีคีย์อยู่แล้วในคอลเล็กชัน ค่าเก่าจะถูกแทนที่ด้วยค่าใหม่ พฤติกรรมนี้แสดงให้เห็นในตัวอย่างของเราโดยมี คู่2 คู่ที่มีรหัสเดียวกัน — ("Oliver", 3)และ("Oliver", 5)

ลองดูตัวอย่างด้วยComparatorที่เราสร้างขึ้น สมมติว่าเราต้องการเก็บองค์ประกอบที่เรียงตามความยาวของคีย์สตริง หากความยาวของคีย์เท่ากัน เราจะเรียงตามตัวอักษร (การเรียงลำดับสตริงตามธรรมชาติ):


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

นี่คือลำดับผลลัพธ์:

lengthComparedMap: {Jan=4, Jeff=4, Roxy=4, Oliver=5}

พฤติกรรมนี้ทำให้TreeMapเหมือนอาร์เรย์หรือรายการที่เรียงลำดับซึ่งมีดัชนีเป็นคำ ( String ) แทนที่จะเป็นตัวเลข

โปรดทราบว่าเกือบทุกประเภทสามารถเป็น KeyType หรือ ValueType ได้ มีข้อกำหนดเพิ่มเติมเล็กน้อยสำหรับ KeyType และคุณจะได้เรียนรู้เกี่ยวกับข้อกำหนดเหล่านี้เมื่อคุณศึกษาคอลเลกชันโดยละเอียดยิ่งขึ้น

วิธีการ SortedMap ในคลาส TreeMap

  1. หากคุณต้องการรับรหัสของนักเรียนคนแรก คุณสามารถใช้ เมธอด firstKey() ได้ :

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

    ผลลัพธ์: คีย์แรก → แอนโทนี่

  2. หากคุณต้องการรับรหัสของนักเรียนคนสุดท้าย คุณสามารถใช้ เมธอด lastKey() ได้ :

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

    ผลลัพธ์: คีย์สุดท้าย → เจฟฟ์

  3. รับวัตถุทั้งหมดที่อยู่หลังวัตถุด้วยปุ่ม " Sara ":

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

    ผลลัพธ์: tailMap: {Sara=5, Jeff=4}

  4. รับวัตถุทั้งหมดที่มาก่อนวัตถุด้วยปุ่ม " นิค ":

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

    ผลลัพธ์: headMap: {Anthony=5}

  5. รับวัตถุทั้งหมดที่อยู่หลังวัตถุด้วยคีย์ " Oliver " และมาก่อนวัตถุด้วยคีย์ " Sara ":

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

    ผลลัพธ์: แผนที่ย่อย: {Oliver=5, Roxy=5}

การเปรียบเทียบ HashMap และ SortedMap/TreeMap

เรามาพูดถึงวิธีการสั่งซื้อและจัดเก็บองค์ประกอบกัน:

  • เนื่องจากHashMapไม่ได้ให้การรับประกันใดๆ แก่เราเกี่ยวกับลำดับเมื่อมีการวนซ้ำ ลำดับอาจเปลี่ยนแปลงโดยสิ้นเชิงเมื่อมีการเพิ่มองค์ประกอบใหม่

  • ในTreeMapลำดับจะขึ้นอยู่กับ "ลำดับตามธรรมชาติ" ของคีย์ตามวิธีการของexpandTo() (หรือตัวเปรียบเทียบที่เราจัดเตรียมไว้ให้) นอกจากนี้ อย่าลืมว่าTreeMapใช้ อินเทอร์เฟซ SortedMapซึ่งมีวิธีการที่ขึ้นอยู่กับลำดับการจัดเรียงนี้

ตอนนี้เรามาพิจารณาประสิทธิภาพและความเร็ว:

  • HashMapเป็นแผนที่ที่ใช้คีย์การแฮช มันสามารถแทรกและรับองค์ประกอบในO(1)เวลาคงที่ เพื่อรองรับสิ่งนี้ คีย์ต้องใช้hashCode()และเท่ากับ()

  • TreeMapเป็นแผนที่แบบต้นไม้ การดำเนินการแทรกและดึงข้อมูลจะใช้เวลาแบบลอการิทึม เช่นO(log n)ซึ่งขึ้นอยู่กับจำนวนองค์ประกอบในแผนที่ สิ่งนี้จำเป็นเพื่อให้องค์ประกอบมีกลไกการเปรียบเทียบบางประเภทที่จัดเตรียมโดยคีย์ของเราหรือตัวเปรียบเทียบภายนอก กลไกนี้กำหนดลำดับการวนซ้ำ

และปัจจัยเหล่านี้ช่วยให้เราตัดสินใจได้ว่าจะใช้คอลเลกชันใดและเมื่อใด

หากเราต้องการเก็บค่าตามลำดับที่แน่นอน ทางเลือกที่ชัดเจนคือเราต้องการSortedMap แม้ว่าจะช้ากว่าHashMap เล็กน้อย แต่ก็ทำงานที่สำคัญสำหรับเรา

ตามที่กล่าวไว้ก่อนหน้านี้SortedMapสามารถให้คีย์แรก (หรือสุดท้าย) หรือค่า หรือคู่คีย์-ค่าในแผนที่ของเรา โดยไม่คำนึงว่าค่านั้นจะถูกเพิ่มเมื่อใด การใช้งาน HashMapไม่สามารถทำได้

ตัวอย่างเช่น พิจารณาแผนผังที่มีคีย์ (ชื่อนักเรียน) และค่า (เกรด) สมมติว่าเราต้องการทำงานกับรายการตามลำดับตัวอักษรแบบย้อนกลับ

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

ตัวอย่างแสดงให้เห็นว่าการใช้HashMapทำให้งานซับซ้อนขึ้น เนื่องจากHashMapไม่รับประกันลำดับการจัดเก็บหรือลำดับการรับองค์ประกอบจากแผนที่