ฉันมักจะพบคำถามดังกล่าวในระหว่างการสัมภาษณ์ในอดีต อนิจจาฉันละอายใจรากฐานที่ยากจนเกินไปไม่มีทางฉันรู้สึกผิด
ตอนนี้เราต้องพูดคุยเกี่ยวกับความแตกต่างและการเชื่อมต่อระหว่างทั้งสาม: ทั้งสามใช้อินเตอร์เฟสรายการทั้งหมดมีวิธีการที่กำหนดไว้ในอินเทอร์เฟซรายการและยังมีวิธีการของอินเทอร์เฟซคอลเลกชัน
ArrayList: ใช้วิธีการอาร์เรย์เพื่อจัดเก็บข้อมูลการสืบค้นและความเร็วในการปรับเปลี่ยนเป็นอย่างรวดเร็ว แต่ความเร็วในการเพิ่มและการลบนั้นช้า
LinkedList: ใช้วิธีการของรายการที่เชื่อมโยงเพื่อจัดเก็บข้อมูลการสืบค้นและความเร็วในการปรับเปลี่ยนช้า แต่ความเร็วในการเพิ่มและการลบนั้นรวดเร็ว
เวกเตอร์: มันใช้อาร์เรย์สำหรับการจัดเก็บ ตัววนซ้ำ, การแจกแจง, รับ (ดัชนี int) และดัชนีของ (ดัชนี int) แต่ arraylist ไม่มีการแจกแจง
ArrayList และ Vector ใช้อาร์เรย์เพื่อจัดเก็บข้อมูล การดำเนินการดังนั้นข้อมูลดัชนีจะถูกแทรกอย่างรวดเร็ว หรือย้อนหลังไปตามทาง แต่เฉพาะรายการนี้จะต้องใช้เมื่อแทรกข้อมูล
ตารางเชิงเส้น, รายการที่เชื่อมโยงและตารางแฮชเป็นโครงสร้างข้อมูลที่ใช้กันทั่วไป คลาสเหล่านี้ทั้งหมดอยู่ในแพ็คเกจ Java.util บทความนี้พยายามอธิบายบทบาทของแต่ละชั้นเรียนให้ผู้อ่านและวิธีการใช้อย่างถูกต้องผ่านคำอธิบายง่ายๆ
คอลเลกชัน├ลิสต์│├linkedlist│├arraylist│└└└│└││stack└setmap├hashtable├hashmap└weakhashmap
อินเทอร์เฟซคอลเลกชัน
คอลเลกชันเป็นอินเทอร์เฟซคอลเลกชันพื้นฐานที่สุด คอลเลกชันบางส่วนอนุญาตองค์ประกอบเดียวกันในขณะที่คนอื่นไม่ได้ บางคนสามารถเรียงลำดับได้ แต่คนอื่นไม่สามารถ Java SDK ไม่ได้ให้คลาสที่สืบทอดโดยตรงจากการรวบรวม
คลาสทั้งหมดที่ใช้งานอินเทอร์เฟซคอลเลกชันจะต้องจัดให้มีตัวสร้างมาตรฐานสองตัว: ตัวสร้างพารามิเตอร์ที่ใช้ในการสร้างคอลเลกชันที่ว่างเปล่าและมีตัวสร้างพารามิเตอร์คอลเลกชันที่ใช้ในการสร้างคอลเลกชันใหม่คอลเลกชันและผ่านใหม่นี้ องค์ประกอบเดียวกัน ตัวสร้างหลังอนุญาตให้ผู้ใช้คัดลอกคอลเลกชัน
จะวนซ้ำทุกองค์ประกอบในคอลเลกชันได้อย่างไร? โดยไม่คำนึงถึงประเภทที่แท้จริงของคอลเลกชันมันรองรับวิธีการวนซ้ำ () ซึ่งส่งคืนตัววนซ้ำและใช้ตัววนซ้ำนี้เพื่อเข้าถึงแต่ละองค์ประกอบในคอลเลกชันทีละตัว ประเพณีทั่วไปมีดังนี้:
ITERATOR IT = Collect.iterator ();
อินเทอร์เฟซทั้งสองที่ได้จากอินเทอร์เฟซคอลเลกชันคือรายการและตั้งค่า
รายการอินเทอร์เฟซ
รายการเป็นคอลเลกชันที่สั่งซื้อและการใช้อินเทอร์เฟซนี้ช่วยให้คุณสามารถควบคุมตำแหน่งของการแทรกองค์ประกอบแต่ละอย่างได้อย่างแม่นยำ ผู้ใช้สามารถใช้ดัชนี (ตำแหน่งขององค์ประกอบในรายการคล้ายกับตัวห้อยอาร์เรย์) เพื่อเข้าถึงองค์ประกอบในรายการซึ่งคล้ายกับอาร์เรย์ของ Java
ไม่เหมือนกับชุดที่กล่าวถึงด้านล่างรายการอนุญาตองค์ประกอบเดียวกัน
นอกเหนือจากเมธอด iterator () ที่มีอินเทอร์เฟซคอลเลกชันที่จำเป็นรายการยังมีเมธอด listiterator () ซึ่งส่งคืนอินเทอร์เฟซ listiterator ลบตั้งค่าองค์ประกอบและยังสามารถข้ามไปข้างหน้าหรือย้อนกลับ
คลาสทั่วไปที่ใช้อินเตอร์เฟสรายการรวมถึง LinkedList, ArrayList, Vector และ Stack
คลาส LinkedList
LinkedList ใช้อินเทอร์เฟซรายการช่วยให้องค์ประกอบ NULL นอกจากนี้ LinkedList ยังให้การรับเพิ่มเติม, ลบ, แทรกวิธีการที่ส่วนหัวหรือหางของ LinkedList การดำเนินการเหล่านี้ช่วยให้ LinkedList สามารถใช้เป็นสแต็กคิวหรือคิวสองทาง
โปรดทราบว่า LinkedList ไม่มีวิธีการแบบซิงโครนัส หากหลายเธรดเข้าถึงรายการในเวลาเดียวกันคุณต้องใช้การซิงโครไนซ์การเข้าถึงด้วยตัวเอง ทางออกหนึ่งคือการสร้างรายการแบบซิงโครนัสเมื่อสร้าง:
รายการ list = collections.synchronizedList (ใหม่ LinkedList (... ));
คลาส ArrayList
ArrayList ใช้อาร์เรย์ขนาดตัวแปร ช่วยให้องค์ประกอบทั้งหมดรวมถึง Null ArrayList ไม่ได้ซิงโครไนซ์
เวลาทำงานของขนาด, isempty, get, วิธีการคงที่ อย่างไรก็ตามค่าใช้จ่ายของวิธีการเพิ่มเป็นค่าคงที่ตัดจำหน่ายและต้องใช้เวลา o (n) ในการเพิ่มองค์ประกอบ n วิธีอื่นมีเวลาทำงานเชิงเส้น
แต่ละอินสแตนซ์ ArrayList มีความจุซึ่งเป็นขนาดของอาร์เรย์ที่ใช้ในการจัดเก็บองค์ประกอบ กำลังการผลิตนี้สามารถเพิ่มขึ้นโดยอัตโนมัติเมื่อมีการเพิ่มองค์ประกอบใหม่อย่างต่อเนื่อง แต่อัลกอริทึมการเติบโตไม่ได้กำหนดไว้ เมื่อจำเป็นต้องแทรกองค์ประกอบจำนวนมากวิธีการ ensurecapacity สามารถเรียกได้ก่อนที่จะแทรกเพื่อเพิ่มความสามารถของ arraylist เพื่อปรับปรุงประสิทธิภาพการแทรก
เช่นเดียวกับ LinkedList ArrayList ก็ไม่ได้ซิงโครไนซ์
คลาสเวกเตอร์
เวกเตอร์คล้ายกับ ArrayList มาก แต่เวกเตอร์นั้นเป็นแบบซิงโครนัส ตัววนซ้ำที่สร้างขึ้นโดยเวกเตอร์แม้ว่าตัววนซ้ำที่สร้างขึ้นโดย arrayList เป็นอินเทอร์เฟซเดียวกันกับตัววนซ้ำที่สร้างขึ้นโดย arrayList เนื่องจากเวกเตอร์ถูกซิงโครไนซ์เมื่อมีการสร้างตัววนซ้ำหนึ่งตัวและถูกใช้งานเธรดอื่นจะเปลี่ยนสถานะของเวกเตอร์ หรือลบออกบางส่วน) ในเวลานี้จะมีการถ่ายทำพร้อมกันเมื่อมีการเรียกใช้วิธีตัววนซ้ำดังนั้นจึงต้องจับข้อยกเว้น
ชั้นเรียนสแต็ก
สแต็คสืบทอดมาจากเวกเตอร์โดยใช้สแต็กครั้งแรกในครั้งสุดท้าย สแต็กมี 5 วิธีเพิ่มเติมเพื่อให้เวกเตอร์ใช้เป็นสแต็ก วิธีการกดและป๊อปขั้นพื้นฐานและวิธีการ PEEK จะได้องค์ประกอบที่ด้านบนของสแต็กวิธีการที่ว่างเปล่าจะทดสอบว่าสแต็กว่างเปล่าและวิธีการค้นหาตรวจจับตำแหน่งขององค์ประกอบในสแต็ก สแต็คเพิ่งสร้างขึ้นและเป็นสแต็คที่ว่างเปล่า
ตั้งค่าอินเตอร์เฟส
Set เป็นคอลเลกชันที่ไม่มีองค์ประกอบที่ซ้ำกันนั่นคือองค์ประกอบสององค์ประกอบ E1 และ E2 มี e1.equals (E2) = false และ Set มีองค์ประกอบ Null มากที่สุด
เห็นได้ชัดว่าตัวสร้างของ Set มีข้อ จำกัด และพารามิเตอร์การรวบรวมที่ผ่านไม่สามารถมีองค์ประกอบที่ซ้ำกันได้
โปรดทราบ: วัตถุที่เปลี่ยนแปลงได้จะต้องดำเนินการด้วยความระมัดระวัง หากองค์ประกอบที่ไม่แน่นอนในชุดเปลี่ยนสถานะของตัวเองทำให้ Object.equals (วัตถุ) = จริงเพื่อทำให้เกิดปัญหาบางอย่าง
อินเทอร์เฟซแผนที่
โปรดทราบว่าแผนที่ไม่ได้สืบทอดอินเทอร์เฟซคอลเลกชันและแผนที่ให้การแมปจากคีย์ไปยังค่า แผนที่ไม่สามารถมีคีย์เดียวกันได้และแต่ละคีย์สามารถแมปได้เพียงค่าเดียวเท่านั้น อินเทอร์เฟซแผนที่มีมุมมองสามประเภทของคอลเลกชัน
คลาสแฮช
Hashtable สืบทอดอินเทอร์เฟซแผนที่และใช้ตารางแฮชด้วยการทำแผนที่ค่าคีย์ วัตถุที่ไม่ใช่ NULL ใด ๆ สามารถใช้เป็นคีย์หรือค่า
ใช้ (คีย์, ค่า) เพื่อเพิ่มข้อมูลใช้ GET (คีย์) เพื่อดึงข้อมูล
Hashtable ปรับประสิทธิภาพผ่านพารามิเตอร์ความจุเริ่มต้นและพารามิเตอร์ปัจจัยโหลด โดยปกติแล้วปัจจัยโหลดเริ่มต้น 0.75 สามารถบรรลุความสมดุลเวลาและพื้นที่ได้ดีขึ้น การเพิ่มปัจจัยโหลดสามารถประหยัดพื้นที่ได้ แต่เวลาการค้นหาที่สอดคล้องกันจะเพิ่มขึ้นซึ่งจะส่งผลกระทบต่อการดำเนินงานเช่น Get and Put
ตัวอย่างง่ายๆของการใช้แฮชช์มีดังนี้: ใส่ 1, 2 และ 3 ลงในแฮชแต้มและกุญแจของพวกเขาคือ "หนึ่ง", "สอง", "สาม" ตามลำดับ:
หมายเลข Hashtable = new hashtable ();
number.put ("หนึ่ง", จำนวนเต็มใหม่ (1));
number.put ("สอง", จำนวนเต็มใหม่ (2));
number.put ("สาม", จำนวนเต็มใหม่ (3));
หากต้องการนำตัวเลขออกมาเช่น 2 ให้ใช้คีย์ที่เกี่ยวข้อง:
จำนวนเต็ม n = (จำนวนเต็ม) numbers.get ("สอง");
System.out.println ("สอง =" + n);
เนื่องจากวัตถุเป็นคีย์จะกำหนดตำแหน่งของค่าที่สอดคล้องกันโดยการคำนวณฟังก์ชั่นแฮชวัตถุใด ๆ ที่เป็นคีย์ต้องใช้วิธี HashCode และ Equals วิธีการ HashCode และ Equals ที่สืบทอดมาจากวัตถุระดับราก ) = จริงแล้ว hashcode ของพวกเขาจะต้องเหมือนกัน แต่ถ้าวัตถุทั้งสองแตกต่างกัน hashcodes ของพวกเขาอาจไม่แตกต่างกัน ของการใช้งานตารางแฮช
หากวัตถุเดียวกันมี hashcodes ที่แตกต่างกันการดำเนินการบนตารางแฮชจะมีผลลัพธ์ที่ไม่คาดคิด (วิธีการที่คาดหวังจะส่งคืนโมฆะ) ในเวลาเดียวกัน
Hashtable ถูกซิงโครไนซ์
คลาส hashmap
HashMap นั้นคล้ายคลึงกับ Hashtable ความแตกต่างคือ HashMap เป็นแบบอะซิงโครนัสและอนุญาตให้ NULL, ค่า NULL และ NULL คีย์ แต่เมื่อ HASHMAP ได้รับการพิจารณาว่าเป็นคอลเลกชัน (ค่า () สามารถคืนค่าคอลเลกชันได้) ค่าใช้จ่ายในการทำซ้ำของการวนซ้ำจะเป็นสัดส่วนกับความสามารถของ HASHMAP ดังนั้นหากประสิทธิภาพของการดำเนินการวนซ้ำมีความสำคัญมากอย่าตั้งค่าความสามารถในการเริ่มต้นของ HASHMAP ให้สูงเกินไปหรือปัจจัยโหลดต่ำเกินไป
ระดับความอ่อนแอ
WeakhashMap เป็น hashmap ที่ได้รับการปรับปรุงซึ่งใช้ "การอ้างอิงที่อ่อนแอ" กับคีย์
สรุป
หากสแต็ก, คิวและการดำเนินการอื่น ๆ มีส่วนร่วมคุณควรพิจารณาใช้รายการ
หากโปรแกรมอยู่ในสภาพแวดล้อมแบบเธรดเดี่ยวหรือการเข้าถึงเป็นเพียงหนึ่งเธรดที่พิจารณาคลาสแบบอะซิงโครนัสมันจะมีประสิทธิภาพมากขึ้น
ให้ความสนใจเป็นพิเศษกับการทำงานของตารางแฮช
พยายามส่งคืนอินเทอร์เฟซแทนประเภทจริงเช่นการส่งคืนรายการแทน ArrayList นี่คือการเขียนโปรแกรมนามธรรม
การซิงโครไนซ์
เวกเตอร์เป็นแบบซิงโครนัส บางวิธีในคลาสนี้ตรวจสอบให้แน่ใจว่าวัตถุในเวกเตอร์นั้นปลอดภัย ArrayList เป็นแบบอะซิงโครนัสดังนั้นวัตถุใน ArrayList จึงไม่ปลอดภัย เนื่องจากข้อกำหนดการซิงโครไนซ์จะส่งผลกระทบต่อประสิทธิภาพการดำเนินการการใช้ ArrayList เป็นตัวเลือกที่ดีหากคุณไม่ต้องการคอลเลกชันที่ปลอดภัยจากเธรดซึ่งสามารถหลีกเลี่ยงค่าใช้จ่ายที่ไม่จำเป็นเนื่องจากการซิงโครไนซ์
การเติบโตของข้อมูล
จากกลไกการใช้งานภายใน ArrayList และ Vector ทั้งคู่ใช้อาร์เรย์ (อาร์เรย์) เพื่อควบคุมวัตถุในการรวบรวม เมื่อคุณเพิ่มองค์ประกอบให้กับสองประเภทนี้หากจำนวนองค์ประกอบเกินความยาวปัจจุบันของอาร์เรย์ภายในพวกเขาจะต้องขยายความยาวของอาร์เรย์ภายใน ต้นฉบับ 50% ของสิ่งนั้นดังนั้นครั้งสุดท้ายที่คุณได้รับคอลเลกชันนี้จะใช้พื้นที่มากกว่าที่คุณต้องการ ดังนั้นหากคุณต้องการบันทึกข้อมูลจำนวนมากในคอลเลกชันมีข้อดีบางประการในการใช้เวกเตอร์เพราะคุณสามารถหลีกเลี่ยงค่าใช้จ่ายทรัพยากรที่ไม่จำเป็นได้โดยการตั้งค่าขนาดเริ่มต้นของคอลเลกชัน
โหมดการใช้งาน
ใน ArrayList และ Vector ใช้เวลาเดียวกันในการค้นหาข้อมูลจากตำแหน่งที่ระบุ (ผ่านดัชนี) หรือเพื่อเพิ่มและลบองค์ประกอบในตอนท้ายของชุด อย่างไรก็ตามหากมีการเพิ่มองค์ประกอบหรือลบที่อื่นในชุดเวลาที่ใช้จะเพิ่มขึ้นเป็นเส้นตรง: O (Ni) โดยที่ n แสดงถึงจำนวนองค์ประกอบในชุดและฉันแสดงถึงตำแหน่งดัชนีที่องค์ประกอบเพิ่มหรือลบองค์ประกอบ ทำไมสิ่งนี้ถึงเกิดขึ้น? เป็นที่คิดว่าเมื่อดำเนินการข้างต้นองค์ประกอบทั้งหมดหลังจากองค์ประกอบ I-Th และ i-th ในชุดจะต้องดำเนินการกระจัดกระจาย ทั้งหมดนี้หมายความว่าอย่างไร?
ซึ่งหมายความว่าคุณเพียงแค่มองหาองค์ประกอบในตำแหน่งที่เฉพาะเจาะจงหรือเพียงแค่เพิ่มและลบองค์ประกอบในตอนท้ายของคอลเลกชันจากนั้นใช้เวกเตอร์หรืออาร์เรย์ลิสต์ก็โอเค หากเป็นการดำเนินการอื่นคุณควรเลือกคลาส Operation Collection อื่น ตัวอย่างเช่นเวลาที่คลาสคอลเลกชัน LinkList เพิ่มหรือลบองค์ประกอบที่ตำแหน่งใด ๆ ในคอลเลกชันเหมือนกัน? เป็นที่ตั้งของดัชนี LinkList จะสร้างวัตถุสำหรับแต่ละองค์ประกอบที่แทรกและสิ่งที่คุณต้องเข้าใจจะนำค่าใช้จ่ายเพิ่มเติม
ในที่สุดในหนังสือ Java ภาคปฏิบัติ Peter Haggar แนะนำให้ใช้อาร์เรย์แบบง่าย ๆ (อาร์เรย์) แทนเวกเตอร์หรือ ArrayList นี่เป็นเรื่องจริงโดยเฉพาะอย่างยิ่งสำหรับโปรแกรมที่มีประสิทธิภาพการดำเนินการสูง เนื่องจากการใช้อาร์เรย์ (อาร์เรย์) หลีกเลี่ยงการซิงโครไนซ์การโทรวิธีเพิ่มเติมและการจัดสรรพื้นที่การดำเนินงานอวกาศโดยไม่จำเป็น