วันหนึ่งที่มหาวิทยาลัย ฉันต้องเขียนโค้ดเพื่อจัดเรียงนามสกุลของเพื่อนร่วมชั้น ซึ่งทำหน้าที่เป็นกุญแจสู่ข้อมูลส่วนตัวของพวกเขา โดยเรียงลำดับจากน้อยไปหามาก ฉันใช้เวลามากกับเรื่องนี้ แต่ถ้าฉันรู้เกี่ยวกับ คลาส 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 ทั้งหมดจึงมีที่ของมัน
เท่านี้คุณก็รู้แล้วว่าจะใช้อะไรเมื่อต้องจัดเก็บค่าตามลำดับการจัดเรียง และวิธีตั้งกฎสำหรับการเรียงลำดับ