บทความนี้วิเคราะห์ซอร์สโค้ดของ ArrayList ให้ฉันพูดถึงอาร์เรย์ก่อนวิเคราะห์พวกเขา อาร์เรย์อาจเป็นหนึ่งในโครงสร้างข้อมูลแรกที่เราติดต่อด้วย พวกเขาแบ่งพื้นที่ที่อยู่อย่างต่อเนื่องในหน่วยความจำเพื่อจัดเก็บองค์ประกอบ เนื่องจากใช้งานหน่วยความจำโดยตรงประสิทธิภาพของอาร์เรย์จึงดีกว่าคลาสคอลเลกชันซึ่งเป็นข้อได้เปรียบที่สำคัญของการใช้อาร์เรย์ แต่เรารู้ว่าอาร์เรย์มีข้อบกพร่องร้ายแรงนั่นคือขนาดอาร์เรย์จะต้องระบุในระหว่างการเริ่มต้นและขนาดของอาร์เรย์ไม่สามารถเปลี่ยนแปลงได้ในการดำเนินการครั้งต่อไป ในสถานการณ์จริงเราพบสิ่งต่าง ๆ มากขึ้นที่เราไม่ทราบว่าจะเก็บองค์ประกอบจำนวนเท่าใดในตอนแรก แต่หวังว่าคอนเทนเนอร์จะสามารถขยายขีดความสามารถของตัวเองโดยอัตโนมัติเพื่อให้สามารถเก็บองค์ประกอบได้มากขึ้น ArrayList สามารถตอบสนองความต้องการดังกล่าวได้เป็นอย่างดีและสามารถขยายขนาดโดยอัตโนมัติเพื่อปรับให้เข้ากับองค์ประกอบการจัดเก็บที่เพิ่มขึ้นอย่างต่อเนื่อง เลเยอร์พื้นฐานของมันถูกนำไปใช้ตามอาร์เรย์ดังนั้นจึงมีคุณสมบัติบางอย่างของอาร์เรย์เช่นการค้นหาการแก้ไขนั้นรวดเร็วและการแทรกและการลบช้า ในบทความนี้เราจะลึกเข้าไปในซอร์สโค้ดเพื่อดูว่ามันห่อหุ้มอาร์เรย์อย่างไร ก่อนอื่นดูตัวแปรสมาชิกและตัวสร้างหลักสามตัว
// ค่าเริ่มต้นความจุเริ่มต้นส่วนตัวคงที่ int default_capacity = 10; // อาร์เรย์วัตถุเปล่าอาร์เรย์ส่วนตัวแบบคงที่ส่วนตัว [] emport_elementData = {}; // อาร์เรย์วัตถุอาร์เรย์วัตถุส่วนตัว [] elementData; // จำนวนองค์ประกอบการรวบรวมส่วนตัว if (initialCapacity <0) {โยน unlegalargumentException ใหม่ ("ความสามารถที่ผิดกฎหมาย:"+ การเริ่มต้นความจุ); } // สร้างอาร์เรย์ประเภทวัตถุใหม่ของความจุที่ระบุ this.elementData = วัตถุใหม่ [initialCapacity];} // ตัวสร้างโดยไม่มีพารามิเตอร์ public ArrayList () {super (); // ส่งอินสแตนซ์อาร์เรย์ที่ว่างเปล่าไปยัง ElementData this.elementData = emport_elementData;} // วิธีการสร้างเพื่อส่งผ่านเข้าไปในคอลเลกชันภายนอก ArrayList สาธารณะ (คอลเลกชัน <? ขยาย e> c) {// ถือองค์ประกอบอ้างอิงของอาร์เรย์ภายในที่ส่งผ่านไป // อัปเดตจำนวนองค์ประกอบของขนาดการรวบรวม = elementData.length; // ตัดสินประเภทอาร์เรย์ของการอ้างอิงและแปลงการอ้างอิงเป็นการอ้างอิงอาร์เรย์วัตถุถ้า (elementData.getClass ()! = object []. class) {elementData = array.copyof (elementData, ขนาด, วัตถุ []. คลาส); -คุณจะเห็นว่าโครงสร้างการจัดเก็บข้อมูลภายในของ ArrayList เป็นอาร์เรย์ของประเภทวัตถุดังนั้นจึงสามารถจัดเก็บองค์ประกอบทุกประเภท เมื่อสร้าง arrayList หากขนาดเริ่มต้นถูกส่งผ่านมันจะสร้างอาร์เรย์วัตถุใหม่ของความสามารถที่ระบุ หากขนาดเริ่มต้นไม่ได้ตั้งค่ามันจะไม่จัดสรรพื้นที่หน่วยความจำ แต่ใช้อาร์เรย์วัตถุว่างเปล่าจากนั้นจัดสรรหน่วยความจำเมื่อองค์ประกอบจะถูกวางไว้จริง ลองมาดูวิธีการเพิ่มลบแก้ไขและค้นหา
// เพิ่ม (เพิ่ม) บูลีนสาธารณะเพิ่ม (e e) {// ตรวจสอบว่าต้องขยายอาร์เรย์ก่อนที่จะเพิ่มความยาวอาร์เรย์ขั้นต่ำคือขนาด + 1 ensureCapacityInternal (ขนาด + 1); // เพิ่มองค์ประกอบที่ส่วนท้ายของอาร์เรย์ elementData [ขนาด ++] = e; ส่งคืนจริง;} // เพิ่ม (แทรก) โมฆะสาธารณะเพิ่ม (ดัชนี int, องค์ประกอบ e) {// แทรกช่วงตำแหน่งตรวจสอบ rangecheckforadd (ดัชนี); // ตรวจสอบว่าจะต้องมีการขยายความสามารถในการขยาย ensureCapacityInternal (ขนาด + 1); // ย้ายองค์ประกอบที่อยู่ด้านหลังตำแหน่งการแทรก System.arrayCopy (ElementData, INDEX, ElementData, ดัชนี + 1, ขนาด - ดัชนี); // กำหนดค่าใหม่ ElementData [ดัชนี] = องค์ประกอบ; ขนาด ++;} // ลบสาธารณะ e ลบ (ดัชนี int) {// ดัชนีไม่สามารถมากกว่าขนาด rangecheck (ดัชนี); Modcount ++; E oldValue = ElementData (ดัชนี); int nummoved = size - ดัชนี - 1; if (nummoved> 0) {// ย้ายองค์ประกอบไปข้างหลังดัชนีไปข้างหน้าโดยหนึ่ง system.arraycopy (elementData, ดัชนี+1, elementData, index, nummoved); } // elementDaterferes elementData [-size] = null; return oldValue;} // เปลี่ยน public e set (int index, e Element) {// index ไม่สามารถมากกว่าขนาด rangecheck (ดัชนี); E oldValue = ElementData (ดัชนี); // แทนที่ด้วย Element ElementData [ดัชนี] = องค์ประกอบ; return oldValue;} // ตรวจสอบสาธารณะ e get (int index) {// ดัชนีไม่สามารถมากกว่าขนาด rangecheck (ดัชนี); // ส่งคืนองค์ประกอบตำแหน่งที่ระบุ return elementData (ดัชนี);} ทุกครั้งที่มีการเพิ่มองค์ประกอบลงในคอลเลกชันก่อนอื่นจะตรวจสอบว่าความจุนั้นเพียงพอหรือไม่มิฉะนั้นจะมีการขยายกำลังการผลิต รายละเอียดของการขยายกำลังการผลิตจะกล่าวถึงด้านล่าง ก่อนอื่นให้ดูที่จุดเฉพาะเพื่อให้ความสนใจเมื่อเพิ่มการลบการแก้ไขและการตรวจสอบ
เพิ่ม (เพิ่ม): เพียงเพิ่มองค์ประกอบนี้ในตอนท้าย การดำเนินการอย่างรวดเร็ว
เพิ่ม (แทรก): การดำเนินการช้าลงเนื่องจากองค์ประกอบที่อยู่เบื้องหลังตำแหน่งการแทรกจะต้องย้ายและการคัดลอกอาเรย์นั้นเกี่ยวข้อง
ลบ: เนื่องจากองค์ประกอบที่อยู่เบื้องหลังตำแหน่งการลบจะต้องถูกเลื่อนไปข้างหน้าสำเนาอาร์เรย์จะได้รับการออกแบบดังนั้นการดำเนินการจึงช้า
การเปลี่ยนแปลง: แก้ไของค์ประกอบโดยตรงที่ตำแหน่งที่ระบุโดยไม่เกี่ยวข้องกับการเคลื่อนไหวขององค์ประกอบหรือการคัดลอกอาร์เรย์และการดำเนินการอย่างรวดเร็ว
ตรวจสอบ: ส่งคืนองค์ประกอบอาร์เรย์ของตัวห้อยที่ระบุโดยตรงและการดำเนินการนั้นรวดเร็ว
จากซอร์สโค้ดจะเห็นได้ว่าเนื่องจากการค้นหาและการแก้ไขอยู่ในตำแหน่งโดยตรงไปยังตัวห้อยอาร์เรย์มันไม่เกี่ยวข้องกับการเคลื่อนไหวขององค์ประกอบและการคัดลอกอาร์เรย์ดังนั้นจึงเร็วขึ้น อย่างไรก็ตามเนื่องจากองค์ประกอบจำเป็นต้องย้ายจึงเกี่ยวข้องกับการคัดลอกอาเรย์ดังนั้นการดำเนินการจึงช้าลง นอกจากนี้การดำเนินการเพิ่มเติมแต่ละครั้งอาจดำเนินการขยายอาร์เรย์ซึ่งจะส่งผลกระทบต่อประสิทธิภาพ ลองมาดูกันว่า ArrayList ขยายกำลังการผลิตแบบไดนามิกอย่างไร
โมฆะส่วนตัว ensureCapacityInternal (int mincapacity) {// ถ้าอาร์เรย์ยังคงว่างเปล่าในเวลานี้ถ้า (elementData == empty_elementData) {// เปรียบเทียบกับความจุเริ่มต้น } // หากอาร์เรย์ได้รับการเริ่มต้นให้ดำเนินการขั้นตอนนี้ ensureexplicitCapacity (mincapacity);} โมฆะส่วนตัว ensureexplicitCapacity (int mincapacity) {modcount ++; // หากความจุขั้นต่ำมากกว่าความยาวอาร์เรย์ให้ขยายอาร์เรย์ถ้า (mincapacity - elementData.length> 0) {grow (mincapacity); }} // ความจุสูงสุดของคอลเลกชันส่วนตัวคงที่สุดท้าย int max_array_size = integer.max_value - 8; // เพิ่มความยาวอาร์เรย์โมฆะส่วนตัวเติบโต (int mincapacity) {// ได้รับความจุดั้งเดิม // กำลังการผลิตของอาร์เรย์ใหม่เพิ่มครึ่งหนึ่งบนพื้นฐานดั้งเดิม int newCapacity = oldCapacity + (OldCapacity >> 1); // ตรวจสอบว่ากำลังการผลิตใหม่น้อยกว่าความจุขั้นต่ำหรือไม่ถ้า (newCapacity - mincapacity <0) {newCapacity = mincapacity; } // ตรวจสอบว่ากำลังการผลิตใหม่เกินความจุสูงสุดหรือไม่ถ้า (newCapacity - max_array_size> 0) {newCapacity = hugecapacity (mincapacity); } // คัดลอกอาร์เรย์ดั้งเดิมไปยังอาร์เรย์ใหม่ ElementData = array.copyof (ElementData, newCapacity);} ก่อนที่จะเพิ่มองค์ประกอบ ensurecapacityinternal จะถูกเรียกให้ตรวจสอบความสามารถในการรวบรวม ภายในวิธีนี้จะตรวจสอบว่าอาร์เรย์ภายในของคอลเลกชันปัจจุบันยังคงเป็นอาร์เรย์ที่ว่างเปล่าหรือไม่ ถ้าเป็นเช่นนั้นให้สร้างอาร์เรย์วัตถุใหม่ที่มีขนาดเริ่มต้น 10 ถ้าไม่พิสูจน์ว่าคอลเลกชันปัจจุบันได้รับการเริ่มต้น จากนั้นเรียกใช้วิธีการ ensureexplicitcapacity เพื่อตรวจสอบความจุของอาร์เรย์ปัจจุบันเป็นไปตามความจุขั้นต่ำที่ต้องการหรือไม่ หากไม่พอใจให้โทรหาวิธีการเติบโตเพื่อขยาย ในวิธีการเติบโตคุณจะเห็นว่าการขยายตัวแต่ละครั้งคือการเพิ่มความยาวอาร์เรย์ดั้งเดิมครึ่งหนึ่ง การขยายตัวเป็นจริงเพื่อสร้างอาร์เรย์ใหม่ที่มีความจุมากขึ้นคัดลอกองค์ประกอบทั้งหมดของอาร์เรย์ดั้งเดิมไปยังอาร์เรย์ใหม่จากนั้นทิ้งอาร์เรย์ดั้งเดิมและใช้อาร์เรย์ใหม่ จนถึงตอนนี้เราได้วิเคราะห์วิธีการที่ใช้กันทั่วไปใน ArrayList และประเด็นสำคัญบางประการที่น่าสังเกต:
1. การใช้งาน arrayList นั้นขึ้นอยู่กับอาร์เรย์ดังนั้นการค้นหาและการปรับเปลี่ยนของตัวห้อยที่ระบุจะเร็วขึ้น แต่การลบและการแทรกจะช้าลง
2. เมื่อสร้าง ArrayList ให้พยายามระบุความสามารถให้มากที่สุดเท่าที่จะทำได้เพื่อลดการดำเนินการคัดลอกอาร์เรย์ที่เกิดจากการขยายตัว หากคุณไม่ทราบขนาดคุณสามารถกำหนดความจุเริ่มต้นให้กับ 10
3. ก่อนที่จะเพิ่มองค์ประกอบให้ตรวจสอบว่าจำเป็นต้องมีการขยายกำลังการผลิตหรือไม่ การขยายกำลังการผลิตแต่ละครั้งเป็นครึ่งหนึ่งของกำลังการผลิตดั้งเดิม
4. ทุกครั้งที่ดำเนินการห้อยการตรวจสอบความปลอดภัยจะดำเนินการ หากอาร์เรย์อยู่นอกขอบเขตข้อยกเว้นจะถูกโยนทันที
5. วิธีการทั้งหมดของ ArrayList ไม่ได้ซิงโครไนซ์ดังนั้นจึงไม่ปลอดภัยด้าย
6. การวิเคราะห์ข้างต้นขึ้นอยู่กับ JDK1.7 และรุ่นอื่น ๆ จะมีความแตกต่างบางอย่างดังนั้นจึงไม่สามารถสรุปได้
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น