6. บอกเราเกี่ยวกับรายการ
รายการคืออินเทอร์เฟซที่แสดงโครงสร้างที่เรียงลำดับของวัตถุ ซึ่งเรียกว่ารายการ “เคล็ดลับ” ของโครงสร้าง นี้- รับ - ส่งคืนองค์ประกอบในตำแหน่งที่ระบุ (ตามค่าดัชนี)
- ลบ - ลบองค์ประกอบในตำแหน่งที่ระบุ
- set - แทนที่องค์ประกอบในตำแหน่งที่ระบุด้วยองค์ประกอบที่ระบุในวิธีการ
- push - เพิ่มองค์ประกอบที่ส่งผ่านไปยังด้านบนของสแต็ก
- peek - ส่งคืนองค์ประกอบที่อยู่ด้านบนของสแต็ก
- pop - ส่งคืนองค์ประกอบที่อยู่ด้านบนของสแต็กด้วย แต่จะลบออก
- ว่างเปล่า - ตรวจสอบว่าสแต็กว่างเปล่า - จริงหรือไม่ - เท็จ ;
- ค้นหา - ค้นหาสแต็กสำหรับองค์ประกอบที่กำหนด หากพบองค์ประกอบ หมายเลขลำดับที่สัมพันธ์กับด้านบนของสแต็กจะถูกส่งกลับ หากไม่พบองค์ประกอบ ค่าจะถูกส่งกลับ -1
7. บอกเราเกี่ยวกับแผนที่
ตามที่ระบุไว้ข้างต้นแผนที่คือคอลเลกชันที่มีโครงสร้างแยกต่างหากของอินเทอร์เฟซและการใช้งาน แยกจากกันเพราะที่นี่ค่าจะไม่ถูกจัดเก็บทีละค่า แต่อยู่ในคู่ "คีย์-ค่า" วิธีการทำ แผนที่
- ใส่(คีย์ K, ค่า V) - การเพิ่มองค์ประกอบลงในแผนที่;
- รับ(คีย์วัตถุ) - ค้นหาค่าด้วยคีย์
- containsKey(คีย์วัตถุ) - ตรวจสอบแผนที่ว่ามีคีย์นี้อยู่หรือไม่
- containsValue(ค่าอ็อบเจ็กต์) - ตรวจสอบแผนที่ว่ามีค่านี้อยู่หรือไม่
- ลบ(คีย์วัตถุ) - ลบค่าด้วยคีย์
- HashMap - ออกแบบมาเพื่อจัดเก็บค่าตามลำดับแบบสุ่ม แต่ช่วยให้คุณค้นหาองค์ประกอบแผนที่ได้อย่างรวดเร็ว ช่วยให้คุณสามารถระบุคีย์โดยใช้ คีย์เวิร์ดnull ได้แต่ต้องไม่เกินหนึ่งครั้ง เนื่องจาก คู่กับคีย์เดียวกันจะถูกเขียนทับกัน เงื่อนไขหลักคือเอกลักษณ์ของคีย์: ค่าสามารถทำซ้ำได้ (อาจมีค่า Null หลายค่า)
- LinkedHashMapเป็นอะนาล็อกของ HashMapที่เก็บค่าตามลำดับที่เพิ่ม ดังนั้น เช่นเดียวกับLinkedListก็มีส่วนหัว - ส่วนหัวของรายการที่เชื่อมโยงแบบทวีคูณ เมื่อเริ่มต้น มันจะชี้ไปที่ตัวมันเอง
LinkedHashMapยังมีaccessOrderซึ่งระบุวิธีการเข้าถึงองค์ประกอบต่างๆ เมื่อใช้ตัววนซ้ำ หากaccessOrder เป็นเท็จ การเข้าถึงจะดำเนินการตามลำดับที่แทรกองค์ประกอบ หากเป็นจริงองค์ประกอบจะอยู่ในลำดับการเข้าถึงล่าสุด (องค์ประกอบที่เข้าถึงล่าสุดจะถูกวางไว้ที่ส่วนท้าย)
- TreeMapเป็นแผนที่ที่จัดเรียงองค์ประกอบตามค่าคีย์ คล้ายกับTreeSetแต่สำหรับคู่ที่ยึดตามค่าคีย์ ในการตั้ง ค่ากฎการเรียงลำดับ TreeMapคีย์ต้องใช้อินเทอร์เฟซที่เปรียบเทียบได้ มิฉะนั้น ควรมี Key-Orient Comparator (อันที่ระบุไว้ในTreeMap Constructor ), TreeSet - นำไปใช้กับอ็อบเจ็กต์ TreeMap ภายใน ซึ่งในความเป็นจริงแล้ว ความมหัศจรรย์ทั้งหมดเกิดขึ้น
คุณสามารถอ่านเพิ่มเติมเกี่ยวกับการเรียงลำดับใน TreeMap โดยใช้ต้นไม้สีแดงดำได้ในบทความเกี่ยวกับคุณสมบัติของ TreeMap
- Hashtableคล้ายกับHashMapแต่ไม่อนุญาต ให้เก็บ ค่าว่างเป็นคีย์หรือค่า มีการซิงโครไนซ์อย่างระมัดระวังจากมุมมองแบบมัลติเธรด ซึ่งหมายความว่าปลอดภัยจากมุมมองแบบมัลติเธรด แต่การใช้งานนี้ล้าสมัยและช้า ดังนั้นตอนนี้คุณจะไม่เห็นHashtableในโปรเจ็กต์ใหม่ไม่มากก็น้อย
8. ArrayList กับ LinkedList อันไหนดีกว่าที่จะใช้?
คำถามนี้อาจเป็นคำถามที่ได้รับความนิยมมากที่สุดในโครงสร้างข้อมูลและมีข้อผิดพลาดบางประการด้วย ก่อนที่จะตอบคำถาม มาเรียนรู้เพิ่มเติมเกี่ยวกับโครงสร้างข้อมูลเหล่านี้ก่อน ArrayListใช้ อินเทอร์เฟซ รายการและดำเนินการกับอาร์เรย์ภายในที่ขยายตามความจำเป็น เมื่ออาร์เรย์ภายในเต็มไปหมด และจำเป็นต้องแทรกองค์ประกอบใหม่ อาร์เรย์ใหม่จะถูกสร้างขึ้นโดยมีขนาด (oldSize * 1.5) +1 หลังจากนี้ ข้อมูลทั้งหมดจากอาร์เรย์เก่าจะถูกคัดลอกไปยังองค์ประกอบใหม่ + ใหม่ และตัวรวบรวมขยะเก่าจะถูกลบ วิธีการเพิ่มจะเพิ่มองค์ประกอบลงในเซลล์ว่างสุดท้ายของอาร์เรย์ นั่นคือถ้าเรามี 3 องค์ประกอบอยู่แล้ว มันจะเพิ่มองค์ประกอบถัดไปในเซลล์ที่ 4 มาดูประสิทธิภาพของวิธีการพื้นฐานกัน:- get(int index) - การรับองค์ประกอบในอาร์เรย์ด้วยดัชนีนั้นเร็วที่สุดในO(1) ;
- เพิ่ม(Object obj) - หากมีพื้นที่เพียงพอในอาร์เรย์ภายในสำหรับองค์ประกอบใหม่ จากนั้นจะใช้เวลาในการแทรกO(1) ปกติ เนื่องจากการเพิ่มถูกกำหนดเป้าหมายไปที่เซลล์สุดท้าย
หากเราจำเป็นต้องสร้างอาร์เรย์ใหม่และคัดลอกเนื้อหาลงไป เวลาของเราจะเป็นสัดส่วนโดยตรงกับจำนวนองค์ประกอบในอาร์เรย์O(n) ;
- ลบ(ดัชนี int) - เมื่อลบองค์ประกอบเช่นจากตรงกลางเราจะได้เวลา O(n/2) เนื่องจากเราจะต้องย้ายองค์ประกอบไปทางขวาของมันกลับไปหนึ่งเซลล์ ดังนั้นหากลบจากจุดเริ่มต้นของรายการ O(n) จากจุดสิ้นสุด - O(1);
- add(int index, Object obj) - สถานการณ์คล้ายกับการลบ: เมื่อเพิ่มตรงกลาง เราจะต้องย้ายองค์ประกอบทางขวาหนึ่งเซลล์ไปข้างหน้า ดังนั้นเวลาจึงเป็น O(n/2) แน่นอนตั้งแต่ต้น - O(n) จากจุดสิ้นสุด - O(1);
- set(int index, Object obj) - ที่นี่สถานการณ์แตกต่างออกไป เนื่องจากคุณเพียงแค่ต้องค้นหาองค์ประกอบที่ต้องการและเขียนทับมันโดยไม่ย้ายส่วนที่เหลือ ดังนั้น O(1)
- get(int index) - เมื่อค้นหาองค์ประกอบที่อยู่ตรงกลางรายการจะเริ่มค้นหาองค์ประกอบทั้งหมดตามลำดับจนกว่าจะพบองค์ประกอบที่ต้องการ ตามหลักเหตุผลแล้ว การค้นหาควรใช้O(n/2)แต่ LinkedList ก็มีส่วนท้ายด้วย ดังนั้นการค้นหาจึงดำเนินการพร้อมกันจากทั้งสองฝ่าย ดังนั้น เวลาจึงลดลงเหลือO(n/4 )
ถ้าองค์ประกอบนั้นอยู่ใกล้กับจุดเริ่มต้นของรายการหรือจุดสิ้นสุด เวลาจะเป็นO(1) ;
- เพิ่ม(Object obj) - เมื่อเพิ่มองค์ประกอบใหม่ องค์ประกอบ "tail" จะมีลิงก์ไปยังองค์ประกอบถัดไปที่เพิ่มเข้ามา และองค์ประกอบใหม่จะได้รับลิงก์ไปยังองค์ประกอบก่อนหน้านี้และกลายเป็น "ส่วนท้าย" ใหม่ ดังนั้นเวลาจะเป็นO(1) ;
- ลบ(ดัชนี int) - ตรรกะคล้ายกับ เมธอด get(int index ) หากต้องการลบองค์ประกอบออกจากตรงกลางรายการ คุณต้องค้นหาองค์ประกอบนั้นก่อน นี่เป็นอีกครั้งO(n/4)ในขณะที่การลบนั้นไม่ได้ทำอะไรเลยจริง ๆ เนื่องจากมันจะเปลี่ยนเพียงตัวชี้ของวัตถุที่อยู่ใกล้เคียงเท่านั้น (พวกมันเริ่มอ้างถึงกันและกัน) หากองค์ประกอบอยู่ที่จุดเริ่มต้นหรือจุดสิ้นสุด ให้อีกครั้ง - O(1) ;
- add(int index, Object obj)และset(int index, Object obj) - วิธีการจะมีความซับซ้อนของเวลาเหมือนกับget(int index)เนื่องจากใช้เวลาส่วนใหญ่ในการค้นหาองค์ประกอบ ดังนั้นสำหรับตรงกลางรายการ - O(n/4)สำหรับจุดเริ่มต้น - O(1)
การดำเนินการ | ArrayList | รายการที่เชื่อมโยง |
---|---|---|
รับโดยดัชนีรับ (ดัชนี) | โอ(1) | ตรงกลาง O(n/4) |
เพิ่มองค์ประกอบใหม่ add(obj) |
โอ(1) หากคุณต้องการคัดลอกอาร์เรย์ - O(n) |
โอ(1) |
ลบองค์ประกอบลบ (ดัชนี int) |
จากจุดเริ่มต้น - O(n) จากตรงกลาง - O(n/2) จากจุดสิ้นสุด - O(1) |
ตรงกลาง - O(n/4) ในตอนท้ายหรือตอนเริ่มต้น - O(n) |
เพิ่มองค์ประกอบเพิ่ม (ดัชนี int, obj วัตถุ) |
กลับไปด้านบน - O(n) ตรงกลาง - O(n/2) ถึงจุดสิ้นสุด - O(1) |
ตรงกลาง - O(n/4) ในตอนท้ายหรือตอนเริ่มต้น - O(n) |
แทนที่ชุดองค์ประกอบ (ดัชนี obj) | โอ(1) |
ตรงกลาง - O(n/4) ในตอนท้ายหรือตอนเริ่มต้น - O(n) |
- ตัวเลือกที่ดีที่สุดหากการดำเนินการบ่อยที่สุดคือการค้นหาองค์ประกอบโดยการเขียนทับองค์ประกอบ
- ทางเลือกที่แย่ที่สุดหากการดำเนินการเป็นการแทรกและการลบที่จุดเริ่มต้น-ตรงกลาง เนื่องจากการดำเนินการกะขององค์ประกอบทางด้านขวาจะเกิดขึ้น
- ทางเลือกที่ดีที่สุดหากการดำเนินการบ่อยครั้งของเราคือการแทรกและการลบที่จุดเริ่มต้นตรงกลาง
- ทางเลือกที่แย่ที่สุดหากการดำเนินการที่พบบ่อยที่สุดคือการค้นหา
9. องค์ประกอบต่างๆ ถูกจัดเก็บใน HashMap อย่างไร
คอลเลกชันHashMap มี ตาราง Node[]อาร์เรย์ภายในซึ่งเซลล์เหล่านี้เรียกว่าที่เก็บข้อมูล โหนดประกอบด้วย:- คีย์ - ลิงก์ไปยังคีย์
- ค่า - อ้างอิงถึงค่า
- แฮช - ค่าแฮช
- ถัดไป - เชื่อมโยงไปยังโหนด ถัด ไป
- คีย์ถูกตรวจสอบว่าเป็นโมฆะ หากเป็นnullคีย์จะถูกเก็บไว้ใน เซลล์ table[0]เนื่องจากรหัสแฮชสำหรับ null จะเป็น 0 เสมอ
- หากคีย์ไม่ใช่null ก็จะเรียกเมธอด hashcode()ของอ็อบเจ็กต์ คีย์ ซึ่งจะส่งคืนโค้ดแฮชของมัน รหัสแฮชนี้ใช้เพื่อกำหนดเซลล์อาร์เรย์ที่จะจัดเก็บวัตถุโหนด
- ถัดไป โค้ดแฮช นี้จะถูกวางไว้ใน เมธอด hash() ภายใน ซึ่งจะคำนวณแฮชโค้ด แต่จะอยู่ภายในขนาดของ อาร์เรย์ table[]
- ถัดไป ขึ้นอยู่กับค่าแฮช โหนดจะถูกวางในเซลล์เฉพาะใน อาร์เรย์ table[ ]
- หาก เซลล์ table[] ที่ใช้ในการบันทึกองค์ประกอบ Nodeปัจจุบันไม่ว่างเปล่า แต่มีองค์ประกอบบางส่วนอยู่แล้ว องค์ประกอบ Node จะถูกวนซ้ำใน ค่าถัดไปจนกว่าจะถึงองค์ประกอบสุดท้าย นั่นคืออันที่ฟิลด์ ถัดไปเป็นnull
ในระหว่างการค้นหานี้ คีย์ของ ออบเจ็กต์ Node ที่ได้รับการป้องกันจะถูกเปรียบเทียบ กับคีย์ของคีย์ที่กำลังค้นหา:
- หากพบการจับคู่ การค้นหาจะสิ้นสุด และโหนด ใหม่ จะเขียนทับโหนดที่พบการจับคู่ (เฉพาะ ฟิลด์ ค่า เท่านั้นที่จะถูกเขียนทับ );
- หากไม่พบคีย์ที่ตรงกันโหนด ใหม่ จะกลายเป็นโหนดสุดท้ายในรายการนี้ และโหนดก่อนหน้าจะมีลิงก์ถัดไป
10. อธิบายตัววนซ้ำ
ใน แผนภาพการแมปลำดับชั้นของคอล เลกชัน ด้านบน อินเทอร์เฟซของ คอลเลกชันคือจุดเริ่มต้นของลำดับชั้นทั้งหมด แต่ในทางปฏิบัติกลับไม่เป็นเช่นนั้น คอลเลกชันสืบทอดมาจากอินเทอร์เฟซด้วยเมธอดiterator()ซึ่งส่งคืนอ็อบเจ็กต์ที่ใช้ อินเทอร์เฟ ซ Iterator<E> อินเทอร์เฟซ Iterator มีลักษณะดังนี้:public interface Iterator <E>{
E next();
boolean hasNext();
void remove();
}
next() - โดยการเรียกใช้เมธอดนี้ คุณจะได้รับองค์ประกอบถัดไป hasNext() - ช่วยให้คุณค้นหาว่ามีองค์ประกอบถัดไปหรือไม่ และถึงจุดสิ้นสุดของคอลเลกชันแล้วหรือไม่ และเมื่อยังมีองค์ประกอบอยู่hasNext()จะส่งคืนค่าtrue โดยทั่วไปแล้วhasNext()จะถูกเรียกก่อน เมธอด next()เนื่องจากnext()จะส่งNoSuchElementException เมื่อถึงจุดสิ้นสุดของคอลเลก ชัน ลบ() - ลบองค์ประกอบที่ถูกดึงโดยการเรียกครั้งล่าสุดไปยัง next( ) วัตถุประสงค์ของ Iterator คือการวนซ้ำองค์ประกอบต่างๆ ตัวอย่างเช่น:
Set<Integer> values = new TreeSet<>();
values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);
Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
System.out.println(iter.next());
}
จริงๆ แล้วfor-each loopถูกนำมาใช้ภายใต้ประทุนโดยใช้ตัววนซ้ำ คุณสามารถอ่านเพิ่มเติมเกี่ยวกับเรื่องนี้ได้ ที่นี่ Listจัดเตรียมตัววนซ้ำในเวอร์ชันของตัวเอง แต่ตัววนซ้ำที่เจ๋งกว่าและซับซ้อนกว่า- ListIterator อินเทอร์เฟซนี้ขยายIteratorและมีวิธีการเพิ่มเติม:
- hasPreviousจะส่งคืนค่าจริงหากมีองค์ประกอบก่อนหน้าในคอลเลกชัน มิฉะนั้นจะเป็นเท็จ
- Previousส่งคืนองค์ประกอบปัจจุบันและย้ายไปยังองค์ประกอบก่อนหน้า หากไม่มีเลย NoSuchElementException จะถูกส่งออกไป
- addจะแทรกวัตถุที่ส่งผ่านก่อนที่องค์ประกอบที่จะถูกส่งกลับโดยการเรียกครั้งต่อไปที่next() ;
- ชุดกำหนดองค์ประกอบปัจจุบันการอ้างอิงไปยังวัตถุที่ส่งผ่าน;
- nextIndexส่งกลับดัชนีขององค์ประกอบถัดไป หากไม่มีสิ่งนั้น ขนาดของรายการจะถูกส่งคืน
- PreviousIndexส่งกลับดัชนีขององค์ประกอบก่อนหน้า หากไม่มี ก็จะส่งกลับตัวเลข -1
GO TO FULL VERSION