ขอแนะนำคอลเลกชั่น TreeMap

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

TreeMapคืออะไร? เป็นโครงสร้างข้อมูลแบบพจนานุกรมที่เก็บองค์ประกอบเป็นคู่คีย์-ค่า โดยเรียงลำดับตามคีย์

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

มันเรียงลำดับประเภทเช่นIntegerและStringจากน้อยไปหามาก แต่ถ้าคุณต้องการใส่ประเภทที่คุณกำหนดเองในTreeMapคลาสของคุณจะต้องใช้ อินเทอร์เฟซ Comparableเพื่อให้ใช้เมธอดของexpandTo()ซึ่งระบุวิธีจัดเรียงอินสแตนซ์ของคลาสของคุณ

public class Person implements Comparable<Person> {
 
    private String firstName;
    private String lastName;
 
    public Person(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }
 
    public String getFirstName() {
        return firstName;
    }
 
    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }
 
  …
 
    @Override
    public int compareTo(Person person) {
        return person.getFirstName().compareTo(firstName);
    }
 
    @Override
    public String toString() {
        return "Person{" +
                "firstName='" + firstName + '\'' +
                ", lastName='" + lastName + '\'' +
                '}';
    }
}

เรามาแทนที่เมธอดcomparisonTo()เพื่อให้เรียงลำดับค่าตามชื่อโดยเรียงลำดับตามตัวอักษรแบบย้อนกลับ:

TreeMap map = new TreeMap<Person, String>();
 
map.put(new Person("AA","BB"), "aa");
map.put(new Person("BB","BB"), "aa");
map.put(new Person("DD","BB"), "aa");
map.put(new Person("CC","BB"), "aa");

ค่าจะถูกจัดเก็บตามลำดับต่อไปนี้:

Person{firstName='DD', lastName='BB'}
Person{firstName='CC', lastName='BB'}
Person{firstName='BB', lastName='BB'}
Person{firstName='AA', lastName='BB'}

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

พูดง่ายๆ ก็คือ ต้นไม้สีแดง-ดำเป็นโครงสร้างข้อมูลที่เก็บค่าไว้ในทรีย่อยด้านขวาหากมีค่ามากกว่ารูท และในทรีย่อยด้านซ้ายหากมีค่าน้อยกว่า การใช้งานนี้สามารถค้นหาค่าในโครงสร้างได้อย่างรวดเร็ว

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

ตอนนี้คุณรู้แล้วว่าTreeMapคืออะไรและทำงานอย่างไร

โปรดจำไว้ว่าTreeMapสามารถเก็บได้เฉพาะวัตถุที่มีคลาสที่ใช้ อินเทอร์เฟซ Comparableและแทนที่เมธอดของexpandTo ()

แต่ถ้าเราใช้คลาสของบุคคลที่สามที่โหลดจากไลบรารีต่างๆ และไม่สามารถใช้Comparable ได้ ล่ะ มีวิธีแก้ไขดังนี้: เขียนComparator ของคุณ เอง

Comparatorเป็นอินเทอร์เฟซที่มีวิธีการเปรียบเทียบ () เราสามารถใช้เพื่อเปรียบเทียบวัตถุและเก็บไว้ใน TreeMap

Comparator<Person> comparator = new Comparator<Person>() {
 
    @Override
    public int compare(Person person1, Person person2) {
        return person1.getFirstName().compareTo(person2.getFirstName());
    }
};
 
 
TreeMap map = new TreeMap<Person, String>(comparator);

ในตัวอย่างนี้ เราสร้างเครื่องมือเปรียบเทียบ แบบกำหนดเอง และส่งTreeMapไปยังชั้นเรียน

เริ่มต้นใน Java 8 เราสามารถเขียนสิ่งนี้โดยใช้นิพจน์แลมบ์ดา:

TreeMap map = new TreeMap<Person, String>((Person person1, Person person2) -> person1.getFirstName().compareTo(person2.getFirstName()));

กล่าวอีกนัยหนึ่ง ในการจัดเก็บค่าในTreeMapคุณต้องระบุวิธีการจัดเรียง มีสองวิธีในการทำเช่นนี้: ใช้Comparableหรือใช้Comparator ของคุณ เอง

แต่ถ้าเราต้องการใส่nullลงในTreeMapเป็นคีย์ล่ะ? HashMapช่วยให้คุณทำสิ่งนี้ได้ ใช่ แต่TreeMapจัดการกับสิ่งนี้ อย่างไร

TreeMap map = new TreeMap<Person, String>();
map.put (null, "Person");

การเรียกใช้รหัสนี้ทำให้เรามีข้อผิดพลาด:

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

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

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

เท่านี้คุณก็รู้แล้วว่าจะใช้อะไรเมื่อต้องจัดเก็บค่าตามลำดับการจัดเรียง และวิธีตั้งกฎสำหรับการเรียงลำดับ