หากคุณกำลังอ่านบทความนี้ คุณอาจคุ้นเคยกับ อินเทอร์เฟซ แผนที่และการใช้งาน ถ้าไม่อย่างนั้นก็ไปเถอะ วันนี้เราจะพูดถึงคุณสมบัติการใช้งานของ TreeMap และโดยเฉพาะอย่างยิ่งว่ามันแตกต่างจากHashMap อย่างไร และวิธีใช้อย่างถูกต้อง
ด้วยการใช้ อินเทอร์เฟซNavigableMapและSortedMap TreeMap จะได้รับฟังก์ชันเพิ่มเติมที่HashMap ไม่มี แต่สิ่ง นี้มาในราคาในแง่ของประสิทธิภาพ นอกจากนี้ยังมี คลาส LinkedHashMapซึ่งช่วยให้คุณจัดเก็บข้อมูลตามลำดับที่แน่นอน - ตามลำดับที่เพิ่มเข้าไป เพื่อช่วยให้คุณเข้าใจความแตกต่างระหว่างสามคลาสนี้ โปรดดูตารางนี้:
อย่างที่คุณเห็น คลาสเหล่านี้มีอะไรเหมือนกันหลายอย่าง แต่ก็มีความแตกต่างกันเล็กน้อยเช่นกัน แม้ว่าคลาสจะ
การค้นหาองค์ประกอบที่ต้องการเริ่มต้นจากรากของต้นไม้ ในกรณีของเราคือ 61 จากนั้นจะทำการเปรียบเทียบกับค่าที่ต้องการ ถ้าค่าเราน้อยลงเราก็ไปทางซ้าย ถ้ามีค่ามากกว่าเราก็ไปทางขวา สิ่งนี้จะเกิดขึ้นจนกว่าเราจะพบค่าที่ต้องการหรือตีองค์ประกอบที่มีค่า
การเปรียบเทียบ TreeMap, HashMap และ LinkedHashMap
การใช้งานอินเทอร์เฟซ แผนที่ ที่ใช้ กันมากที่สุดคือHashMap ใช้งานง่ายและรับประกันการเข้าถึงข้อมูลได้อย่างรวดเร็ว ทำให้เป็นตัวเลือกที่ดีที่สุดสำหรับงานส่วนใหญ่ ส่วนใหญ่แต่ไม่ใช่ทั้งหมด บางครั้งจำเป็นต้องจัดเก็บข้อมูลในรูปแบบที่มีโครงสร้างซึ่งสามารถนำทางผ่านข้อมูลได้ ในกรณีนี้ การใช้งานอินเทอร์เฟซ Map อีกครั้งจะ ช่วย ได้ - TreeMap TreeMapใช้ อินเท อ ร์เฟซ NavigableMapซึ่งสืบทอดมาจากSortedMapซึ่งจะสืบทอดมาจาก อินเทอร์เฟ ซแผนที่
แฮชแมป | เชื่อมโยงHashMap | ทรีแมป | |
---|---|---|---|
ลำดับการจัดเก็บข้อมูล | สุ่ม ไม่มีการรับประกันว่าคำสั่งซื้อจะยังคงอยู่เมื่อเวลาผ่านไป | ตามลำดับการบวก | ตามลำดับจากน้อยไปหามากหรือขึ้นอยู่กับตัวเปรียบเทียบที่กำหนด |
เวลาในการเข้าถึงองค์ประกอบ | โอ(1) | โอ(1) | O(บันทึก(n)) |
อินเทอร์เฟซที่นำไปใช้ | แผนที่ | แผนที่ | NavigableMap แผนที่ เรียงลำดับ |
การนำไปใช้งานตามโครงสร้างข้อมูล | ถัง | ถัง | ต้นแดง-ดำ |
ความสามารถในการทำงานกับปุ่ม Null | สามารถ | สามารถ | เป็นไปได้ถ้าคุณใช้ตัวเปรียบเทียบที่อนุญาตให้มีค่าว่าง |
ด้ายปลอดภัย | เลขที่ | เลขที่ | เลขที่ |
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/
null
(ใบของต้นไม้) สีแดงและสีดำใช้เพื่อทำให้ต้นไม้ง่ายต่อการนำทางและทรงตัว มีกฎที่ต้องปฏิบัติตามเสมอเมื่อสร้างต้นไม้สีแดงดำ:
- รากควรเป็นสีดำ
- ใบของต้นไม้ควรเป็นสีดำ
- โหนดสีแดงต้องมีโหนดลูกสีดำสองโหนด
- โหนดสีดำสามารถมีโหนดลูกใดก็ได้
- เส้นทางจากโหนดหนึ่งไปอีกโหนดหนึ่งต้องมีโหนดสีดำจำนวนเท่ากัน
- มีการเพิ่มโหนดใหม่แทนที่ใบไม้
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
ชัดเจนสำหรับคุณแล้ว และคุณจะพบการนำไปประยุกต์ใช้ได้อย่างแม่นยำในการแก้ปัญหาเชิงปฏิบัติ
GO TO FULL VERSION