
คอลเลกชัน
84. บอกเราเกี่ยวกับตัววนซ้ำและวิธีการใช้งาน
คอลเลกชั่นเป็นหัวข้อโปรดในการสัมภาษณ์นักพัฒนา Java เมื่อตอบคำถามเกี่ยวกับลำดับชั้นของคอลเลกชัน ผู้สมัครมักจะบอกว่าเริ่มต้นด้วยอินเทอร์เฟซของคอลเลกชัน แต่นี่ไม่เป็นเช่นนั้น มีอินเทอร์เฟซอื่นที่สูงกว่าหนึ่งระดับ: Iterable อินเทอร์เฟซนี้ประกอบด้วย เมธอด iterator()ซึ่งช่วยให้คุณเข้าถึง อ็อบเจ็กต์ Iteratorสำหรับคอลเลกชันปัจจุบัน และวัตถุ Iteratorนี้คืออะไรกันแน่? อ อบเจ็กต์ Iteratorช่วยให้สามารถเคลื่อนที่ผ่านคอลเลกชันและวนซ้ำองค์ประกอบต่างๆ ได้ และผู้ใช้ไม่จำเป็นต้องทราบรายละเอียดการใช้งานเฉพาะของคอลเลกชัน กล่าวอีกนัยหนึ่ง มันเป็นตัวชี้ประเภทหนึ่งไปยังองค์ประกอบของคอลเลกชัน ราวกับว่ามันกำลังมองเข้าไปข้างในองค์ประกอบใดองค์ประกอบหนึ่ง ตัววนซ้ำมีวิธีการเช่น:-
hasNext() — คืนค่าเป็นจริงหากการวนซ้ำมีองค์ประกอบอื่น (วิธีนี้ช่วยให้คุณทราบเมื่อคุณมาถึงจุดสิ้นสุดของคอลเลกชัน)
-
ถัดไป() - ส่งคืนรายการถัดไปในการวนซ้ำ หากไม่มีเลยNoSuchElementExceptionจะถูกส่งออกไป นั่นหมายความว่าก่อนที่คุณจะใช้วิธีนี้ วิธีที่ดีที่สุดคือใช้เมธอดhasNext()เพื่อให้แน่ใจว่ามีองค์ประกอบถัดไปอยู่
-
ลบ() - ลบองค์ประกอบสุดท้ายที่ได้รับโดยใช้ เมธอด next() ออกจากคอล เลกชัน หาก ไม่เคยมีการเรียก next()การเรียกRemove()จะทำให้IllegalStateExceptionถูกส่งออกไป
-
forEachRemaining(<Consumer>) — ดำเนินการการกระทำที่ส่งผ่านในแต่ละองค์ประกอบของคอลเลกชัน (วิธีนี้ปรากฏใน Java 8)
List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();
while(iterator.hasNext()) {
iterator.next();
iterator.remove();
}
System.out.println(list.size());
คอนโซลจะแสดงสิ่งต่อไปนี้:
iterator.forEachRemaining(x -> System.out.print(x));
แต่เมื่อเราทำเช่นนี้ ตัววนซ้ำจะไม่เหมาะสำหรับการใช้งานต่อไป: มันได้ข้ามผ่านรายการทั้งหมดแล้ว และตัววนซ้ำธรรมดาไม่มีวิธีในการวนซ้ำแบบย้อนกลับ และนั่นทำให้เกิดความต่อเนื่องที่ดีในการอภิปรายLinkedListโดยเฉพาะ เมธอด listIterator()ซึ่งส่งคืนตัววนซ้ำประเภทที่ได้รับการปรับปรุง: ListIterator นอกเหนือจากวิธีการของตัววนซ้ำปกติ (มาตรฐาน) แล้ว ชนิดนี้มีดังต่อไปนี้:
-
add(<Element>) — เพิ่มองค์ประกอบใหม่ในรายการ;
-
hasPrevious() — คืนค่าเป็นจริงหากมีองค์ประกอบอยู่ก่อนองค์ประกอบถัดไป (หากมีองค์ประกอบก่อนหน้า)
-
nextIndex() - ส่งคืนดัชนีขององค์ประกอบถัดไป
-
ก่อนหน้า() - ส่งคืนองค์ประกอบก่อนหน้า (องค์ประกอบก่อนหน้าองค์ประกอบถัดไป);
-
PreviousIndexส่งกลับดัชนีขององค์ประกอบก่อนหน้า
-
set(<Element>) — แทนที่องค์ประกอบสุดท้ายที่ส่งคืนโดยnext ()หรือPrevious()

85. Java Collection Framework มีลำดับชั้นของคอลเลกชันใดบ้าง
Java มีลำดับชั้นการรวบรวมอยู่สองลำดับ ลำดับชั้นแรกคือลำดับชั้นของคอลเลกชันซึ่งมีโครงสร้างดังต่อไปนี้:
-
Setคืออินเทอร์เฟซที่อธิบายชุด ซึ่งเป็นโครงสร้างข้อมูลที่มีองค์ประกอบเฉพาะที่ไม่เรียงลำดับ (ไม่ซ้ำกัน) อินเทอร์เฟซ นี้มีการใช้งานมาตรฐานบางอย่าง: TreeSet , HashSetและLinkedHashSet
-
รายการเป็นอินเทอร์เฟซที่อธิบายโครงสร้างข้อมูลที่จัดเก็บลำดับของออบเจ็กต์ ออบเจ็กต์ในรายการสามารถแทรกและลบออกได้โดยดัชนีในรายการ (เช่นอาร์เรย์ แต่ด้วยการปรับขนาดแบบไดนามิก) อินเทอร์เฟซนี้มีการใช้งานมาตรฐานบางอย่าง: ArrayList , Vector (เลิกใช้แล้วและไม่ได้ใช้จริง ) และLinkedList
-
Queueคืออินเทอร์เฟซที่อธิบายโครงสร้างข้อมูลที่จัดเก็บรายการต่างๆ ในคิวเข้าก่อนออกก่อน (FIFO) อินเทอร์เฟซนี้มีการใช้ งานมาตรฐานดังต่อไปนี้: LinkedList (ใช่แล้ว นอกจากนี้ยังใช้Queue ) และPriotityQueue


86. โครงสร้างภายในของ ArrayList คืออะไร?
ArrayList ก็เหมือนกับอาร์เรย์ แต่สามารถขยายได้แบบไดนามิก นั่นหมายความว่าอย่างไร? ภายใต้ประทุนArrayListใช้อาร์เรย์ธรรมดา กล่าวคือ เก็บองค์ประกอบไว้ในอาร์เรย์ภายในซึ่งมีขนาดเริ่มต้นคือ 10 เซลล์ เมื่ออาร์เรย์ภายในเต็มแล้ว อาร์เรย์ใหม่จะถูกสร้างขึ้น ขนาดของอาร์เรย์ใหม่ถูกกำหนดโดยสูตรนี้:<size of the current array> * 3 / 2 + 1
ดังนั้นหากขนาดของอาร์เรย์ของเราคือ 10 ขนาดของอาร์เรย์ใหม่จะเป็น: 10 * 3/2 + 1 = 16 จากนั้นค่าทั้งหมดจากอาร์เรย์ดั้งเดิม (เก่า) จะถูกคัดลอกไปไว้โดยใช้ในตัวSystem.arraycopy()วิธีการและอาร์เรย์เดิมจะถูกลบ โดยสรุป นั่นคือวิธีที่ArrayListใช้การปรับขนาดแบบไดนามิก ลองพิจารณา วิธีการ ArrayList ที่ได้รับความนิยมมากที่สุด : 1. add(<Element>) — เพิ่มองค์ประกอบที่ส่วนท้ายของอาร์เรย์ (ในเซลล์ว่างสุดท้าย) หลังจากตรวจสอบครั้งแรกว่ามีเซลล์ว่างในอาร์เรย์หรือไม่ ถ้าไม่เช่นนั้น จะมีการสร้างอาร์เรย์ใหม่และองค์ประกอบต่างๆ จะถูกคัดลอกลงไป ความซับซ้อนของเวลาของการดำเนินการนี้คือ O(1) มีเมธอดadd(<Index>, <Elelement>) ที่คล้ายกัน โดยจะเพิ่มองค์ประกอบไม่ต่อท้ายรายการ (อาร์เรย์) แต่เพิ่มไปยังเซลล์เฉพาะที่ระบุโดยดัชนีที่เข้ามาเป็นอาร์กิวเมนต์ ในกรณีนี้ ความซับซ้อนของเวลาจะแตกต่างกันไปขึ้นอยู่กับตำแหน่งที่คุณเพิ่ม:
- หากการเพิ่มอยู่ใกล้กับจุดเริ่มต้นของรายการ ความซับซ้อนของเวลาจะใกล้เคียงกับ O(N) เนื่องจากองค์ประกอบทั้งหมดที่อยู่ทางด้านขวาขององค์ประกอบใหม่จะต้องถูกย้ายหนึ่งเซลล์ไปทางขวา
- หากแทรกองค์ประกอบไว้ตรงกลาง องค์ประกอบนั้นจะเป็น O(N/2) เนื่องจากเราจำเป็นต้องเลื่อนเพียงครึ่งหนึ่งของรายการในรายการไปทางขวาหนึ่งเซลล์
87. โครงสร้างภายในของ LinkedList คืออะไร?
ArrayList มีองค์ประกอบในอาร์เรย์ภายใน แต่LinkedList จะจัดเก็บองค์ประกอบเหล่านั้นไว้ ในรายการที่เชื่อมโยงแบบทวีคูณ ซึ่งหมายความว่าแต่ละองค์ประกอบมีลิงก์ไปยัง องค์ประกอบ ก่อนหน้าและไปยังองค์ประกอบถัดไป องค์ประกอบแรกไม่ได้เชื่อมโยงกับองค์ประกอบก่อนหน้า (เนื่องจากเป็นองค์ประกอบแรก) จะถือเป็นส่วนหัวของรายการด้วย และ ออบเจ็กต์ LinkedListมีการอ้างอิงโดยตรง ในทำนองเดียวกัน องค์ประกอบสุดท้ายไม่มีองค์ประกอบถัดไป เนื่องจากเป็นส่วนท้ายของรายการ วัตถุLinkedListยังอ้างอิงโดยตรงอีกด้วย ซึ่งหมายความว่าความซับซ้อนของเวลาในการเข้าถึงส่วนหัวหรือส่วนท้ายของรายการคือ O(1) ในArrayListหากรายการขยาย อาร์เรย์ภายในก็จะขยายใหญ่ขึ้น ทุกอย่างง่ายขึ้นที่นี่: การเพิ่มข้อมูลอ้างอิงทำได้ง่ายเพียงแค่เปลี่ยนลิงก์สองสามรายการ มาดู วิธีการของ LinkedList ที่ใช้กันมากที่สุด : 1. add(<Element>) — เพิ่มองค์ประกอบที่ส่วนท้ายของรายการ เช่น หลังจากองค์ประกอบสุดท้าย (5) ลิงก์ไปยังองค์ประกอบใหม่จะถูกเพิ่มในลำดับถัดไป . การอ้างอิงก่อนหน้าในองค์ประกอบใหม่จะชี้ไปที่องค์ประกอบ (5) ซึ่งอยู่ก่อนหน้าองค์ประกอบนั้นในรายการ ความซับซ้อนของเวลาของการดำเนินการนี้คือ O(1) เนื่องจากเราต้องการเพียงลิงก์ไปยังองค์ประกอบสุดท้าย และอย่างที่คุณคงจำได้ ออบเจ็กต์ LinkedList มีการอ้างอิงโดยตรงกับส่วนท้าย และการเข้าถึงมันมีความซับซ้อนของเวลาคงที่น้อยที่สุด 2. add(<Index>, <Element>) — เพิ่มองค์ประกอบตามดัชนี เมื่อเพิ่มองค์ประกอบ สมมติว่าตรงกลางรายการ วิธีนี้จะวนซ้ำองค์ประกอบจากส่วนหัวและส่วนท้าย (ทั้งสองทิศทาง) ก่อนจนกว่าจะพบตำแหน่งที่ต้องการ หากเราเพิ่มองค์ประกอบระหว่างองค์ประกอบที่สามและสี่ (ในภาพด้านบน) ลิงก์ถัดไปขององค์ประกอบที่สามจะชี้ไปที่องค์ประกอบใหม่ และองค์ประกอบก่อนหน้าขององค์ประกอบที่เพิ่มใหม่จะชี้ไปที่องค์ประกอบที่สาม ในทางกลับกัน ลิงก์ ก่อนหน้า ขององค์ประกอบที่สี่เก่า จะชี้ไปที่องค์ประกอบใหม่ และ ลิงก์ ถัดไป ขององค์ประกอบใหม่ จะชี้ไปยังองค์ประกอบที่สี่ใหม่: ความซับซ้อนของเวลาของวิธีนี้ขึ้นอยู่กับดัชนีขององค์ประกอบใหม่:

- ถ้ามันอยู่ใกล้กับหัวหรือส่วนท้าย การดำเนินการจะเข้าใกล้ O(1) เนื่องจากไม่จำเป็นจะต้องวนซ้ำองค์ประกอบต่างๆ
- ถ้าอยู่ใกล้ตรงกลางก็จะได้ O(N/2) เนื่องจากวิธีการจะค้นหาจากหัวและหางพร้อมๆ กันจนได้องค์ประกอบที่ต้องการ

88. โครงสร้างภายในของ HashMap คืออะไร?
นี่อาจเป็นหนึ่งในคำถามสัมภาษณ์ยอดนิยมในการถามผู้สมัคร Java Developer HashMap ทำงานร่วมกับคู่คีย์-ค่า พวกมันถูกเก็บไว้ในHashMap อย่างไร ? HashMap มีอาร์เรย์ของโหนดภายใน:Node<K,V>[] table
ตามค่าเริ่มต้น ขนาดของอาร์เรย์คือ 16 และจะเพิ่มเป็นสองเท่าทุกครั้งที่เต็มไปด้วยองค์ประกอบ (นั่นคือ เมื่อถึง LOAD_FACTOR โดยจะระบุเกณฑ์สำหรับจำนวนอาร์เรย์ที่สามารถรับได้เต็ม - โดยค่าเริ่มต้นคือ0.75 ) . แต่ละโหนดจะเก็บแฮชของคีย์ คีย์ ค่า และการอ้างอิงไปยังองค์ประกอบถัดไป 
- เซลล์ว่างเปล่า ในกรณีนี้ ค่า โหนด ใหม่ จะถูกเก็บไว้ในนั้น
- เซลล์ไม่ว่างเปล่า ในกรณีนี้ จะมีการเปรียบเทียบค่าของคีย์ หากเท่ากัน ค่า โหนด ใหม่ จะเขียนทับค่าโหนดเก่า ถ้าไม่เท่ากัน จะ มีการเข้าถึงรายการ ถัดไปและคีย์ของรายการจะถูกเปรียบเทียบ... และต่อๆ ไป จนกว่าค่าใหม่จะเขียนทับค่าเก่าบางส่วน หรือเราไปถึงจุดสิ้นสุดของรายการที่เชื่อมโยงเดี่ยวๆ แล้วเก็บค่าใหม่ไว้ที่นั่นเป็น องค์ประกอบสุดท้าย

GO TO FULL VERSION