Java ArrayList ในรูปภาพ

สวัสดี! การบรรยายในวันนี้ArrayListจะง่ายกว่าและยากกว่าครั้งก่อนๆ มันยากกว่า เพราะวันนี้เราจะมาดู "เบื้องหลัง" ArrayListและศึกษาว่าจะเกิดอะไรขึ้นระหว่างการปฏิบัติงาน ในทางกลับกัน การบรรยายนี้แทบจะไม่มีโค้ดเลย ส่วนใหญ่เป็นรูปภาพและคำอธิบาย ไปกันเลย :) ดังที่คุณทราบแล้วว่า ภายในArrayList'a จะมีอาร์เรย์ธรรมดาซึ่งทำหน้าที่เป็นที่เก็บข้อมูล ในกรณีส่วนใหญ่ เราไม่ได้ระบุขนาดที่แน่นอนของรายการ แต่อาร์เรย์ภายในต้องมีขนาดพอสมควร! นี่เป็นเรื่องจริง ขนาดเริ่มต้นคือ [10 ]

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
}

ก่อนอื่น เรามาดูกันว่าการเพิ่มองค์ประกอบใหม่จะเป็นอย่างไร ประการแรก มีการตรวจสอบเพื่อดูว่ามีพื้นที่เพียงพอในอาร์เรย์ภายในหรือไม่ และจะมีอีกหนึ่งองค์ประกอบที่พอดีหรือไม่ หากมีช่องว่าง องค์ประกอบใหม่จะถูกเพิ่มที่ส่วนท้ายของรายการ เมื่อเราพูดว่า "ถึงจุดสิ้นสุด" เราไม่ได้หมายถึงเซลล์สุดท้ายของอาร์เรย์ (นั่นคงจะแปลก) นี่หมายถึงเซลล์ที่อยู่ถัดจากองค์ประกอบปัจจุบันสุดท้าย ดัชนีของมันจะcars.size()เท่ากับ ขณะนี้รายการของเราว่างเปล่า ( cars.size() = 0) ดังนั้นองค์ประกอบใหม่จะถูกเพิ่มลงในเซลล์ที่มี0ดัชนี

ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);

ทุกอย่างชัดเจนที่นี่ จะเกิดอะไรขึ้นหากทำการแทรกตรงกลางนั่นคือระหว่างองค์ประกอบหลาย ๆ อย่าง?

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");
   Car ford = new Car("Ford Modneo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);

   cars.add(1, ford);//добавляем ford в ячейку 1, которая уже занята
}

ก่อนอื่นจะตรวจสอบอีกครั้งเพื่อดูว่ามีพื้นที่เพียงพอในอาร์เรย์หรือไม่ หากมีพื้นที่เพียงพอองค์ประกอบจะเลื่อนไปทางขวาโดยเริ่มจากเซลล์ที่เราแทรกองค์ประกอบใหม่ เราวางลงในเซลล์ด้วยดัชนี 1 นั่นคือองค์ประกอบจากเซลล์ 3 จะถูกคัดลอกไปยังเซลล์ 4 องค์ประกอบ 2 ไปยังเซลล์ 3 องค์ประกอบ 1 ไปยังเซลล์ 2 หลังจากนั้นองค์ประกอบใหม่ของเราจะถูกวางเข้าที่ องค์ประกอบก่อนหน้า ( bugatti) ได้รับการคัดลอกจากที่นั่นไปยังตำแหน่งใหม่แล้ว ตอนนี้เรามาดูกันว่ากระบวนการนี้จะเกิดขึ้นได้อย่างไรหากไม่มีที่ว่างสำหรับการแทรกในอาร์เรย์ ก่อนอื่นต้องตรวจสอบก่อนว่ามีพื้นที่เพียงพอหรือไม่ หากปรากฎว่ามีพื้นที่ไม่เพียงพอArrayListอาร์เรย์ขนาดใหม่ (ขนาดของ OldArray * 1.5) + 1 จะถูกสร้างขึ้นภายใน 'a ในกรณีของเรา อาร์เรย์ใหม่จะมีขนาด 16 เซลล์ องค์ประกอบปัจจุบันทั้งหมดจะถูกคัดลอกไปที่นั่นทันที ตัวรวบรวมขยะจะลบอาร์เรย์เก่าออก และจะเหลือเพียงอาร์เรย์ใหม่ที่ขยายแล้วเท่านั้น ขณะนี้มีพื้นที่ว่างสำหรับองค์ประกอบใหม่ เราวางลงในเซลล์ 3 ซึ่งถูกครอบครอง ตอนนี้ขั้นตอนที่คุ้นเคยเริ่มต้นขึ้นแล้ว องค์ประกอบทั้งหมดที่เริ่มต้นที่ดัชนี 3 จะถูกเลื่อนไปทางขวาหนึ่งเซลล์ และองค์ประกอบใหม่จะถูกเพิ่มอย่างเงียบๆ และตอนนี้การแทรกสำเร็จแล้ว! เราแยกแยะการแทรกออก ตอนนี้เรามาพูดถึงการลบองค์ประกอบกัน อย่างที่คุณจำได้ว่าเมื่อทำงานกับอาร์เรย์ เราพบปัญหา: เมื่อเราลบมันออกไป "รู" ยังคงอยู่ในนั้น ทางออกเดียวคือเลื่อนองค์ประกอบไปทางซ้ายทุกครั้งที่ถูกลบ และคุณต้องเขียนโค้ดสำหรับการเปลี่ยนแปลงด้วยตัวเอง ArrayListทำงานบนหลักการเดียวกัน แต่กลไกนี้ถูกนำไปใช้โดยอัตโนมัติแล้ว นี่คือลักษณะที่ปรากฏ: และในที่สุดเราก็ได้ผลลัพธ์ที่ต้องการ: ลบ องค์ประกอบlamboสำเร็จแล้ว ที่นี่เราลบออกจากตรงกลาง เป็นที่ชัดเจนว่าการลบออกจากจุดสิ้นสุดของรายการจะเร็วขึ้นเนื่องจากองค์ประกอบที่ต้องการจะถูกลบออกโดยไม่ต้องเปลี่ยนองค์ประกอบอื่นทั้งหมด ลองมาดูขนาดของอาร์เรย์ภายในและพื้นที่เก็บข้อมูลในหน่วยความจำอีกครั้ง การขยายอาร์เรย์เป็นกระบวนการที่ใช้ทรัพยากรจำนวนหนึ่ง ดังนั้น คุณไม่ควรสร้างArrayListด้วยขนาดเริ่มต้นหากคุณทราบแน่ชัดว่าจะมีองค์ประกอบอย่างน้อย 100 รายการ เมื่อคุณแทรกองค์ประกอบที่ 100 อาร์เรย์ภายในจะขยาย6 ครั้งแต่ละครั้งจะถ่ายโอนองค์ประกอบทั้งหมด

• จาก 10 องค์ประกอบถึง 16
• จาก 16 องค์ประกอบเป็น 25
• จาก 25 ถึง 38
• จาก 38 เป็น 58
• จาก 58 เป็น 88
• จาก 88 เป็น 133 (ตามสูตร (ขนาดของ Old Array * 1.5) + 1)

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

ArrayList<Car> cars = new ArrayList<>(100);

ตอนนี้อาร์เรย์ที่มีองค์ประกอบ 100 รายการจะถูกจัดสรรในหน่วยความจำทันที ซึ่งจะมีประสิทธิภาพมากขึ้น เนื่องจากทรัพยากรจะไม่สูญเปล่าในการขยาย นอกจากนี้ยังมีอีกด้านหนึ่งของเหรียญ เมื่อวัตถุถูกลบออกจากArrayListอาร์เรย์ภายใน ขนาดจะไม่ลดลงโดยอัตโนมัติ ตัวอย่างเช่น เรามีArrayListอาร์เรย์ภายในที่มีองค์ประกอบ 88 รายการ ซึ่งเต็มไปหมด: ในระหว่างการทำงานของโปรแกรม เราจะลบองค์ประกอบ 77 รายการออกจากองค์ประกอบนั้น และมีเพียง 11 องค์ประกอบเท่านั้นที่ยังคงอยู่ในนั้น: คุณเดาแล้วหรือยังว่าปัญหาคืออะไร? แน่นอนว่าการใช้หน่วยความจำอย่างไม่มีประสิทธิภาพ! เราใช้เพียง 11 เซลล์ ในขณะที่เราจัดสรรหน่วยความจำให้กับองค์ประกอบ 88 รายการ ซึ่งมากกว่าที่เราต้องการถึง 8 เท่า! หากต้องการเพิ่มประสิทธิภาพในกรณีนี้ คุณสามารถใช้วิธีคลาสพิเศษArrayList- trimToSize(). มัน "ตัด" ความยาวของอาเรย์ภายในให้เหลือตามจำนวนองค์ประกอบที่เก็บไว้ในนั้น ตอนนี้จัดสรรหน่วยความจำได้มากเท่าที่ต้องการ! :)