คุณสมบัติของ TreeMap ใน Java

หากคุณกำลังอ่านบทความนี้ คุณอาจคุ้นเคยกับ อินเทอร์เฟซ แผนที่และการใช้งาน ถ้าไม่อย่างนั้นก็ไปเถอะ วันนี้เราจะพูดถึงคุณสมบัติการใช้งานของ TreeMap และโดยเฉพาะอย่างยิ่งว่ามันแตกต่างจากHashMap อย่างไร และวิธีใช้อย่างถูกต้อง

การเปรียบเทียบ TreeMap, HashMap และ LinkedHashMap

การใช้งานอินเทอร์เฟซ แผนที่ ที่ใช้ กันมากที่สุดคือHashMap ใช้งานง่ายและรับประกันการเข้าถึงข้อมูลได้อย่างรวดเร็ว ทำให้เป็นตัวเลือกที่ดีที่สุดสำหรับงานส่วนใหญ่ ส่วนใหญ่แต่ไม่ใช่ทั้งหมด บางครั้งจำเป็นต้องจัดเก็บข้อมูลในรูปแบบที่มีโครงสร้างซึ่งสามารถนำทางผ่านข้อมูลได้ ในกรณีนี้ การใช้งานอินเทอร์เฟซ Map อีกครั้งจะ ช่วย ได้ - TreeMap TreeMapใช้ อินเท อ ร์เฟซ NavigableMapซึ่งสืบทอดมาจากSortedMapซึ่งจะสืบทอดมาจาก อินเทอร์เฟ ซแผนที่ ด้วยการใช้ อินเทอร์เฟซNavigableMapและSortedMap TreeMap จะได้รับฟังก์ชันเพิ่มเติมที่HashMap ไม่มี แต่สิ่ง นี้มาในราคาในแง่ของประสิทธิภาพ นอกจากนี้ยังมี คลาส LinkedHashMapซึ่งช่วยให้คุณจัดเก็บข้อมูลตามลำดับที่แน่นอน - ตามลำดับที่เพิ่มเข้าไป เพื่อช่วยให้คุณเข้าใจความแตกต่างระหว่างสามคลาสนี้ โปรดดูตารางนี้: อย่างที่คุณเห็น คลาสเหล่านี้มีอะไรเหมือนกันหลายอย่าง แต่ก็มีความแตกต่างกันเล็กน้อยเช่นกัน แม้ว่าคลาสจะTreeMapเป็นคลาสที่มีฟังก์ชันหลากหลายที่สุด แต่ก็ไม่สามารถจัดเก็บnullเป็นคีย์ ได้เสมอไป นอกจากนี้ เวลาในการเข้าถึงองค์ประกอบ TreeMap จะนานที่สุด ดังนั้นหากไม่จำเป็นต้องเก็บข้อมูลในรูปแบบที่เรียงลำดับก็ควรใช้ HashMapหรือLinkedHashMap

ต้นมะเกลือแดง

ดังที่คุณคงสังเกตเห็นว่า ภายใต้ประทุนTreeMapนั้นใช้โครงสร้างข้อมูลที่เรียกว่าต้นไม้สีแดงดำ เป็นการจัดเก็บข้อมูลในโครงสร้างนี้ที่ช่วยให้มั่นใจในลำดับการจัดเก็บข้อมูล ต้นไม้นี้คืออะไร? ลองคิดดูสิ! ลองนึกภาพว่าคุณจำเป็นต้องจัดเก็บคู่ Number-String ตัวเลข 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101 จะเป็นกุญแจ หากคุณเก็บข้อมูลไว้ในรายการแบบเดิมและจำเป็นต้องค้นหาองค์ประกอบที่มีคีย์ 101 คุณจะต้องวนซ้ำองค์ประกอบทั้ง 13 รายการเพื่อค้นหา สำหรับองค์ประกอบทั้ง 13 ประการนั้นไม่สำคัญ แต่เมื่อทำงานกับคนนับล้าน เราจะประสบปัญหาใหญ่ เพื่อแก้ไขปัญหาดังกล่าว โปรแกรมเมอร์จะใช้โครงสร้างข้อมูลที่ซับซ้อนกว่าเล็กน้อย เลยมาเจอต้นแดง-ดำ!

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

การค้นหาองค์ประกอบที่ต้องการเริ่มต้นจากรากของต้นไม้ ในกรณีของเราคือ 61 จากนั้นจะทำการเปรียบเทียบกับค่าที่ต้องการ ถ้าค่าเราน้อยลงเราก็ไปทางซ้าย ถ้ามีค่ามากกว่าเราก็ไปทางขวา สิ่งนี้จะเกิดขึ้นจนกว่าเราจะพบค่าที่ต้องการหรือตีองค์ประกอบที่มีค่าnull(ใบของต้นไม้) สีแดงและสีดำใช้เพื่อทำให้ต้นไม้ง่ายต่อการนำทางและทรงตัว มีกฎที่ต้องปฏิบัติตามเสมอเมื่อสร้างต้นไม้สีแดงดำ:

• รากควรเป็นสีดำ
• ใบของต้นไม้ควรเป็นสีดำ
• โหนดสีแดงต้องมีโหนดลูกสีดำสองโหนด
• โหนดสีดำสามารถมีโหนดลูกใดก็ได้
• เส้นทางจากโหนดหนึ่งไปอีกโหนดหนึ่งต้องมีโหนดสีดำจำนวนเท่ากัน
• มีการเพิ่มโหนดใหม่แทนที่ใบไม้

หากคุณดูกฎข้อ 3, 4 และ 5 ร่วมกัน คุณจะเข้าใจได้ว่าจุดระบายสีช่วยเร่งความเร็วการนำทางผ่านต้นไม้ได้อย่างไร เส้นทางผ่านจุดสีดำจะสั้นกว่าจุดสีแดงเสมอ ดังนั้นขนาดรวมของต้นไม้จึงถูกกำหนดโดยจำนวนโหนดสีดำ และขนาดนี้เรียกว่า "ความสูงสีดำ" ต้นไม้สีแดงดำถูกนำมาใช้ในภาษาการเขียนโปรแกรมที่แตกต่างกัน มีการใช้งาน Java บนอินเทอร์เน็ตมากมายดังนั้นเราจะไม่อยู่กับมันเป็นเวลานาน แต่จะทำความคุ้นเคยกับฟังก์ชันนี้ต่อTreeMapไป

วิธีการที่ได้มาจากอินเทอร์เฟซ SortedMap และ NavigableMap

เช่นเดียวกับที่HashMapมันTreeMapใช้อินเทอร์เฟซMapซึ่งหมายความว่ามันTreeMapมีวิธีการทั้งหมดHashMapนั้น แต่นอกเหนือจากนั้นTreeMapมันยังใช้อินเทอร์เฟซSortedMapและNavigableMapได้รับฟังก์ชันเพิ่มเติมจากพวกเขา SortedMap— อินเทอร์เฟซที่ขยายMapและเพิ่มวิธีการที่เกี่ยวข้องกับชุดข้อมูลที่เรียงลำดับ:

• firstKey(): ส่งคืนคีย์ขององค์ประกอบแรกของแผนที่
• lastKey(): ส่งคืนคีย์ขององค์ประกอบสุดท้าย
• headMap(K end): ส่งคืนแผนที่ที่มีองค์ประกอบทั้งหมดของแผนที่ปัจจุบัน ตั้งแต่จุดเริ่มต้นไปจนถึงองค์ประกอบที่มีคีย์end;
• tailMap(K start): ส่งคืนแผนที่ที่มีองค์ประกอบทั้งหมดของแผนที่ปัจจุบัน โดยเริ่มจากองค์ประกอบstartและลงท้ายด้วยจุดสิ้นสุด
• subMap(K start, K end): ส่งคืนแผนที่ที่มีองค์ประกอบทั้งหมดของแผนที่ปัจจุบัน โดยเริ่มต้นด้วยองค์ประกอบstartและลงท้ายด้วยองค์ประกอบด้วยendคีย์

NavigableMap— อินเทอร์เฟซที่ขยายSortedMapและเพิ่มวิธีการนำทางระหว่างองค์ประกอบแผนที่:

• firstEntry(): ส่งคืนคู่คีย์-ค่าคู่แรก
• lastEntry(): ส่งคืนคู่คีย์-ค่าสุดท้าย
• pollFirstEntry(): ส่งคืนและลบคู่แรกออก
• pollLastEntry(): ส่งคืนและลบคู่สุดท้าย
• ceilingKey(K obj): ส่งกลับคีย์ที่เล็กที่สุด k ที่มากกว่าหรือเท่ากับคีย์ obj หากไม่มีคีย์ดังกล่าว จะส่งคืนค่าว่าง
• floorKey(K obj): ส่งกลับคีย์ k ที่ใหญ่ที่สุดที่น้อยกว่าหรือเท่ากับคีย์ obj หากไม่มีคีย์ดังกล่าว จะส่งคืนค่าว่าง
• lowerKey(K obj): ส่งคืนคีย์ k ที่ใหญ่ที่สุดซึ่งเล็กกว่าคีย์ obj หากไม่มีคีย์ดังกล่าว จะส่งคืนค่าว่าง
• higherKey(K obj): ส่งคืนคีย์ที่เล็กที่สุด k ซึ่งมากกว่าคีย์ obj หากไม่มีคีย์ดังกล่าว จะส่งคืนค่าว่าง
• ceilingEntry(K obj): คล้ายกับเมธอด CeilingKey(K obj) แต่ส่งคืนคู่คีย์-ค่า (หรือ null)
• floorEntry(K obj): คล้ายกับเมธอด floorKey(K obj) แต่ส่งคืนคู่คีย์-ค่า (หรือ null)
• lowerEntry(K obj): คล้ายกับเมธอด lowerKey(K obj) แต่ส่งคืนคู่คีย์-ค่า (หรือ null)
• higherEntry(K obj): คล้ายกับเมธอด HigherKey(K obj) แต่ส่งคืนคู่คีย์-ค่า (หรือ null)
• descendingKeySet(): ส่งคืน NavigableSet ที่มีคีย์ทั้งหมดที่เรียงลำดับแบบย้อนกลับ
• descendingMap(): ส่งคืน NavigableMap ที่มีคู่ทั้งหมดที่เรียงลำดับแบบย้อนกลับ
• navigableKeySet(): ส่งคืนอ็อบเจ็กต์ NavigableSet ที่มีคีย์ทั้งหมดในลำดับการจัดเก็บ
• headMap(K upperBound, boolean incl): ส่งคืนแผนที่ที่มีคู่ตั้งแต่จุดเริ่มต้นจนถึงองค์ประกอบ upperBound อาร์กิวเมนต์ incl ระบุว่าองค์ประกอบ upperBound ควรรวมอยู่ในแผนที่ที่ส่งคืนหรือไม่
• tailMap(K lowerBound, boolean incl): ฟังก์ชันการทำงานจะคล้ายกับวิธีก่อนหน้า แต่จะส่งคืนเฉพาะคู่จาก lowerBound ไปยังจุดสิ้นสุดเท่านั้น
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): เช่นเดียวกับในวิธีการก่อนหน้านี้ คู่จาก lowerBound ถึง upperBound จะถูกส่งกลับ อาร์กิวเมนต์ lowIncl และ highIncl ระบุว่าจะรวมองค์ประกอบขอบเขตในแผนที่ใหม่หรือไม่

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

ตัวอย่างการใช้งาน TreeMap

วิธีการเพิ่มเติมมากมายดังกล่าวอาจดูเหมือนไม่จำเป็น แต่บ่อยครั้งที่วิธีการเหล่านั้นกลับกลายเป็นว่ามีประโยชน์มากกว่าที่คิดในตอนแรก ลองดูตัวอย่างนี้กับคุณ ลองนึกภาพว่าเราทำงานในแผนกการตลาดของบริษัทขนาดใหญ่ และเรามีฐานข้อมูลบุคคลที่เราต้องการแสดงโฆษณาให้ มีความแตกต่างสองประการในเรื่องนี้:

• เราจำเป็นต้องติดตามจำนวนการแสดงผลของแต่ละคน
• อัลกอริธึมในการแสดงโฆษณาต่อผู้เยาว์นั้นแตกต่างออกไป

มาสร้างคลาสPersonที่จะเก็บข้อมูลทั้งหมดเกี่ยวกับบุคคลที่เรามีอยู่:

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

เราใช้ตรรกะในชั้นเรียน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){}
}

ในชั้นเรียนMainที่เราสร้างTreeMapโดยที่keyคือบุคคลใดบุคคลหนึ่ง และvalueคือจำนวนการแสดงโฆษณาในเดือนนี้ ใน Constructor เราผ่านตัวเปรียบเทียบที่จะเรียงลำดับผู้คนตามอายุ เติมmapค่าสุ่ม ตอนนี้เราจำเป็นต้องได้รับการอ้างอิงถึงผู้ใหญ่คนแรกในที่เก็บข้อมูลขนาดเล็กของเรา เราทำสิ่งนี้โดยใช้ Stream API หลังจากนี้ เราจะได้แผนที่สองแผนที่แยกกัน ซึ่งเราส่งต่อไปยังวิธีการแสดงโฆษณา มีหลายวิธีในการแก้ไขปัญหานี้ คลังวิธีการของชั้นเรียนTreeMapช่วยให้คุณคิดค้นวิธีแก้ปัญหาที่เหมาะกับทุกรสนิยมได้ ไม่จำเป็นต้องจดจำทั้งหมด เนื่องจากคุณสามารถใช้เอกสารประกอบหรือคำแนะนำจากสภาพแวดล้อมการพัฒนาได้ตลอดเวลา นั่นคือทั้งหมด! ฉันหวังว่าชั้นเรียนนี้คงTreeMapชัดเจนสำหรับคุณแล้ว และคุณจะพบการนำไปประยุกต์ใช้ได้อย่างแม่นยำในการแก้ปัญหาเชิงปฏิบัติ