TreeMap ใน Java

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

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

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

ต้นแดง-ดำ

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

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

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

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

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

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

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

• firstEntry() : คืนค่าคู่คีย์-ค่าแรก
• lastEntry() : คืนค่าคู่คีย์-ค่าสุดท้าย
• pollFirstEntry() : ส่งคืนและลบคู่แรก
• pollLastEntry() : ส่งคืนและลบคู่สุดท้าย
• ceilingKey(K obj) : ส่งคืนคีย์ที่เล็กที่สุด k ที่มากกว่าหรือเท่ากับคีย์ obj หากไม่มีคีย์ดังกล่าว จะคืนค่า null
• floorKey(K obj) : ส่งคืนคีย์ที่ใหญ่ที่สุด k ที่น้อยกว่าหรือเท่ากับคีย์ obj หากไม่มีคีย์ดังกล่าว จะคืนค่า null
• lowerKey(K obj) : ส่งคืนคีย์ที่ใหญ่ที่สุด k ที่น้อยกว่าคีย์ obj หากไม่มีคีย์ดังกล่าว จะคืนค่า null
• สูงกว่าคีย์ (K obj) : ส่งคืนคีย์ที่เล็กที่สุด k ที่มีขนาดใหญ่กว่าคีย์ obj หากไม่มีคีย์ดังกล่าว จะคืนค่า null
• 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

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

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

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

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

เราใช้ตรรกะใน คลาส หลัก :

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("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 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) {}
}

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