เป็นเวลานานรายการข้อมูลที่ใช้บ่อยขึ้นในรหัสส่วนใหญ่เป็นรายการและพวกเขาทั้งหมด arraylist รู้สึกว่าสิ่งนี้เพียงพอแล้ว ArrayList เป็นคลาสเครื่องมือ wrapper ที่ใช้ในการใช้งานอาร์เรย์แบบไดนามิกดังนั้นเมื่อเขียนโค้ดคุณสามารถดึงเข้าและออกทำซ้ำและสำรวจซึ่งค่อนข้างสะดวก
ฉันไม่รู้ว่าเมื่อใดที่ฉันเริ่มเริ่มคลาสเครื่องมือเช่น HashMap และ Hashset มักจะปรากฏในรหัส ควรกล่าวว่า HashMap เป็นเรื่องธรรมดามากขึ้นและเป็นคำถามสัมภาษณ์แบบคลาสสิกดังนั้นฉันจะอ่านเพิ่มเติมในชีวิตประจำวัน เมื่อฉันเริ่มใช้มันครั้งแรกฉันก็เข้าใจว่ามันเป็นตารางคีย์ที่สอดคล้องกันและสะดวกกว่าในการใช้คีย์เพื่อค้นหาข้อมูล หลังจากการสอบสวนเพิ่มเติมฉันพบ
สิ่งนี้มีความลับบางอย่างโดยเฉพาะอย่างยิ่งหลังจากการเปลี่ยนแปลง JDK เวอร์ชันใหม่ HashMap เป็นต้นไม้รหัสนั้นค่อนข้างซับซ้อน
ฉันเริ่มใช้ชุดน้อยลง แต่ฉันพบชุดต้นไม้ในรหัสโดยไม่ตั้งใจ ฉันพบว่าชั้นเรียนนี้มีความราบรื่น มันรู้สึกน่าสนใจมาก ฉันค่อยๆค้นพบว่านี่เป็นเครื่องมือที่ดี
หากคุณเขียนโค้ดมากเกินไปคุณจะรู้สึกถึงความสำคัญของพื้นฐานดังนั้นที่นี่ฉันเขียนบทความสั้น ๆ เพื่อจัดระเบียบความรู้เกี่ยวกับคอลเลกชันสั้น ๆ
โอเคเรามาเรียงกันสั้น ๆ :
•รายการ: นั่นคือรายการที่รองรับฟังก์ชั่นของอาร์เรย์และรายการที่เชื่อมโยงและโดยทั่วไปจะเป็นเส้นตรง
•แผนที่: เป็นตารางการแมปซึ่งเก็บความสัมพันธ์ที่สอดคล้องกันระหว่างคีย์และค่า
•ชุด: หมายถึงตั้งค่าใช้งานส่วนใหญ่เพื่อจัดเรียงข้อมูลและเรียงลำดับ
มาดูรายการก่อน
รายการเป็นหน้าต่างสำหรับการจัดเก็บข้อมูลเชิงเส้นเช่น: ArrayList สำหรับอาร์เรย์และ LinkedList สำหรับรายการที่เชื่อมโยง
ผู้เข้าร่วมงาน
นี่คือรายการอาร์เรย์ แต่มีฟังก์ชั่นการขยายอัตโนมัติเพื่อรับรู้อินเทอร์เฟซรายการ การดำเนินการภายนอกสามารถเข้าถึงได้ด้วยวิธีการประกาศอินเทอร์เฟซซึ่งปลอดภัยและสะดวก
กุญแจสำคัญในการขยายความจุโดยอัตโนมัติ ความจุเริ่มต้นสามารถตั้งค่าได้เมื่อวัตถุเริ่มต้นหรือสามารถวัดความจุเริ่มต้นได้ หากขนาดอาร์เรย์ไม่ชัดเจนโดยเฉพาะขนาดเริ่มต้นไม่สามารถระบุได้ หากมีความชัดเจนขนาดสามารถระบุได้ซึ่งจะช่วยลดความล่าช้าที่เกิดจากการขยายตัวแบบไดนามิก เมื่อพูดถึงสิ่งนี้เราต้องพูดคุยเกี่ยวกับวิธีการขยายการขยายตัว ดูรหัสต่อไปนี้:
โมฆะส่วนตัว Grow (int mincapacity) {// รหัสผ่านไหลล้น int oldcapacity = elementData.length; int newCapacity = oldCapacity + (oldcapacity >> 1); if (newCapacity - mincapacity <0) newCapacity = mincapacity; if (newCapacity - max_array_size> 0) newcapacity = hugecapacity (mincapacity); // mincapacity มักจะใกล้เคียงกับขนาดดังนั้นนี่คือการชนะ: elementData = arrays.copyof (ElementData, newCapacity); -Grow เป็นวิธีที่กระตุ้นให้ ArrayList เมื่อเพิ่มองค์ประกอบหรือการตรวจสอบง่าย ๆ กระบวนการหลัก:
1. รับความยาวของอาร์เรย์และเคลื่อนย้ายไปทางขวาซึ่งเทียบเท่ากับ oldcapacity/2 และรับความยาวใหม่
2. หากความยาวนี้น้อยกว่าความจุขั้นต่ำมันจะใช้งานได้ง่ายโดยตรง
3. ถ้ามันมากกว่าค่าสูงสุดให้ใช้ค่าสูงสุด วิธีการ hugecapacity จะถูกเรียกที่นี่ส่วนใหญ่เพื่อเปรียบเทียบ mincapacity กับ max_array_size หาก MinCapacity มากกว่า MAX_ARRAY_SIZE ให้ใช้จำนวนเต็ม MAX_VALUE มิฉะนั้นจะใช้ MAX_ARRAY_SIZE ที่น่าสนใจ max_array_size ใช้จำนวนเต็ม max_value - 8; ฉันไม่รู้ว่าความหมายของการทำเช่นนี้คืออะไร
4. สุดท้ายโทรหาวิธีการคัดลอกเพื่อคัดลอกหมายเลขที่มีอยู่ลงในอาร์เรย์ใหม่
เนื่องจากกระบวนการคัดลอกนี้หากอาร์เรย์ค่อนข้างใหญ่การขยายตัวจะทำให้เกิดความล่าช้าอย่างแน่นอน ดังนั้นหากคุณรู้ว่าค่าสูงสุดจากจุดเริ่มต้นและเป็นเรื่องง่ายที่จะเติบโตเป็นค่านี้จากนั้นระบุขนาดเมื่อเริ่มต้นการเริ่มต้นจะมีผลบางอย่าง
LinkedList
นี่คือคลาสเครื่องมือสำหรับรายการที่เชื่อมโยง ข้อดีของรายการที่เชื่อมโยงคือพวกเขาเพิ่มและลบสิ่งต่าง ๆ เร็วขึ้น แต่พวกเขาจะพบว่าช้าลง
สำหรับรหัสดูเหมือนว่าไม่มีอะไรพิเศษคือมันเชื่อมโยงเข้าด้วยกันด้วยสตริงของพอยน์เตอร์ แน่นอน Java ใช้วัตถุแทนเพื่อสร้างวัตถุโหนด โหนดเองชี้ไปที่โหนดก่อนหน้าและโหนดถัดไป นี่คือโครงสร้างของรายการที่เชื่อมโยง:
โหนดคลาสคงที่ระดับส่วนตัว <E> {E รายการ; โหนด <E> ถัดไป; โหนด <E> ก่อนหน้า; Node (Node <E> ก่อนหน้า, E Element, Node <E> ถัดไป) {this.Item = Element; this.next = ถัดไป; this.prev = prev; -จากนั้นใช้สองโหนดเพื่อชี้ไปที่ศีรษะและหางและทำ รหัสต่อไปนี้:
/*** ตัวชี้ไปที่โหนดแรก * invariant: (first == null && last == null) || * (first.prev == null && first.item! = null) */ โหนดชั่วคราว <e> ก่อน; /*** ตัวชี้ไปยังโหนดสุดท้าย * invariant: (first == null && last == null) || * (last.next == null && last.item! = null) */ โหนดชั่วคราว <e> สุดท้าย;
ดูการดำเนินการเพิ่ม:
/*** ลิงก์ E เป็นองค์ประกอบสุดท้าย */ void linklast (e e) {โหนดสุดท้าย <e> l = สุดท้าย; โหนดสุดท้าย <e> newNode = โหนดใหม่ <> (l, e, null); last = newNode; ถ้า (l == null) first = newNode; else l.next = newNode; ขนาด ++; Modcount ++; -อดีตคือ:
1. รับโหนดสุดท้ายและวางไว้ใน L
2. สร้างโหนดใหม่และดึงข้อมูลลงในโหนดนี้ กระบวนการสร้างจะชี้ไปที่ PREV ของโหนดใหม่ไปที่ L เพื่อที่จะเชื่อมต่อกับห่วงโซ่
3. จากนั้นชี้ไปที่โหนดใหม่นี้
4. จากนั้นพิจารณาว่า l เป็นโมฆะหรือไม่ หาก NULL เป็นโมฆะก็หมายความว่ามันเป็นรายการที่เชื่อมโยงเปล่า โหนดใหม่เป็นองค์ประกอบแรก ด้วยวิธีนี้สิ่งแรกจะต้องชี้ไปที่ Newnode
5. ถ้ามันไม่ว่าง
6. เคาน์เตอร์สะสม
การดำเนินการลบเป็นโหนดด้านหน้าและด้านหลังที่ชี้ไปที่การทำงานของการเคลื่อนย้ายของโหนดนี้
มาดูแผนที่กันเถอะ
แผนที่เป็นแอปพลิเคชันของตารางการแมปสำหรับคีย์และค่า คลาสการใช้งานหลัก: hashmap, hashtable, treemap
HashMap และ Hashtable
HashMap เป็นสิ่งที่ใช้อัลกอริทึมแฮชสำหรับการทำแผนที่ค่าคีย์ Hashtable เป็นคลาส Thread-Safe ที่มีการซิงโครไนซ์ นี่คือความแตกต่างที่สำคัญระหว่างพวกเขา หลักการมีความคล้ายคลึงกันและพวกเขาทั้งหมดประสบความสำเร็จผ่านการรวมกันของถัง + โซ่ ถังถูกใช้เพื่อจัดเก็บคีย์และต้องเก็บค่าไว้ในรายการที่เชื่อมโยงเนื่องจากการชนกันของแฮช
•ความสำคัญของถังอยู่ในประสิทธิภาพและสามารถวางตำแหน่งในขั้นตอนเดียวผ่านการคำนวณแฮช
•ความหมายของรายการที่เชื่อมโยงคือการเข้าถึงข้อมูลของแฮชซ้ำ
หลักการเฉพาะที่ฉันเขียน "หมายเหตุการศึกษา: Hashtable และ HashMap" มาก่อน
แต่ฉันเพิ่งเห็นว่า HashMap ของ JDK1.8 ได้เปลี่ยนโครงสร้างการจัดเก็บและนำโครงสร้างต้นไม้สีแดงและสีดำมาใช้ สิ่งนี้อาจแก้ประสิทธิภาพการค้นหารายการที่เชื่อมโยงได้หรือไม่? ไม่มีการศึกษาอย่างละเอียด
treemap
หลังจากอ่านรหัสของ treemap ฉันพบว่าฉันยังคงใช้โครงสร้างต้นไม้ต้นไม้สีแดงและสีดำ เนื่องจากมีการสั่งต้นไม้สีแดงและสีดำพวกเขาจึงมีฟังก์ชั่นการเรียงลำดับโดยธรรมชาติ แน่นอนคุณสามารถระบุวิธีการเปรียบเทียบผ่านตัวเปรียบเทียบเพื่อให้ได้การเรียงลำดับที่เฉพาะเจาะจง
เนื่องจากโครงสร้างต้นไม้ใช้ในการจัดเก็บจึงเป็นเรื่องยากมากขึ้นในการเพิ่มและลบข้อมูล มาดูรหัสใส่กันเถอะ:
Public V Put (k key, v value) {entry <k, v> t = root; if (t == null) {เปรียบเทียบ (key, key); // type (และ null ที่เป็นไปได้) ตรวจสอบรูท = รายการใหม่ <> (คีย์, ค่า, null); ขนาด = 1; Modcount ++; คืนค่า null; } int cmp; รายการ <k, v> parent; // แยกเปรียบเทียบและเปรียบเทียบเส้นทางเปรียบเทียบ <? super k> cpr = comparator; if (cpr! = null) {do {parent = t; cmp = cpr.compare (คีย์, t.key); ถ้า (cmp <0) t = t.left; อื่นถ้า (cmp> 0) t = t.right; อื่น ๆ ส่งคืน t.setValue (ค่า); } ในขณะที่ (t! = null); } else {ถ้า (key == null) โยน nullpointerexception ใหม่ (); @suppresswarnings ("ไม่ได้ตรวจสอบ") เปรียบเทียบได้ <? คีย์ super k> k = (เปรียบเทียบ <? super k>); ทำ {parent = t; cmp = k.compareto (t.key); ถ้า (cmp <0) t = t.left; อื่นถ้า (cmp> 0) t = t.right; อื่น ๆ ส่งคืน t.setValue (ค่า); } ในขณะที่ (t! = null); } รายการ <k, v> e = รายการใหม่ <> (คีย์, ค่า, พาเรนต์); ถ้า (cmp <0) parent.left = e; อื่น ๆ parent.right = e; fixafterinsertion (e); ขนาด ++; Modcount ++; คืนค่า null; -1. ก่อนอื่นตรวจสอบว่าโหนดรูทมีอยู่หรือไม่ หากไม่มีอยู่ก็หมายความว่ามันเป็นข้อมูลชิ้นแรกและใช้โดยตรงเป็นรากของต้นไม้
2. ตรวจสอบว่ามีตัวเปรียบเทียบหรือไม่ หากมีให้ใช้ตัวเปรียบเทียบเพื่อค้นหาตำแหน่งที่เก็บข้อมูลของข้อมูล หากผลลัพธ์ของผลตอบแทนเปรียบเทียบน้อยกว่า 0 ให้ใช้ซ้ายและใช้ทางด้านขวามิฉะนั้นแทนที่ค่าของโหนดปัจจุบันโดยตรง
3. หากไม่มีตัวเปรียบเทียบคีย์จะถูกเปรียบเทียบโดยตรงกับคีย์ของโหนด การเปรียบเทียบเหมือนกับวิธีก่อนหน้า
4. ขั้นตอนต่อไปคือการสร้างโหนดลูกบนพาเรนต์ที่พบและวางไว้ในโหนดลูกซ้ายหรือขวา
5. fixafterinsertion คือการทำโหนดสี
6. การประมวลผลแบบสะสม
มันจะเป็นปัญหาเล็กน้อยเมื่อลบข้อมูล นอกเหนือจากการลบข้อมูลแล้วคุณยังต้องปรับสมดุลต้นไม้สีแดงและสีดำ
นอกจากนี้ TREEMAP ยังใช้อินเทอร์เฟซ NavigableMap <K, V> ดังนั้นจึงมีการดำเนินการส่งคืนข้อมูลในชุดข้อมูล
ในที่สุดลองดูชุด
ชุดส่วนใหญ่มีแอพพลิเคชั่นสองประเภท: Hashset และ Treeset
Hashset
ความหมายที่แท้จริงนั้นชัดเจนมากโดยใช้คอลเลกชันของแฮช ลักษณะของคอลเลกชันนี้คือการใช้อัลกอริทึมแฮชเพื่อจัดเก็บข้อมูลดังนั้นข้อมูลจึงไม่ซ้ำกันและการเข้าถึงค่อนข้างเร็ว มันทำอย่างไร?
บูลีนสาธารณะเพิ่ม (e e) {return map.put (e, ปัจจุบัน) == null; -ปรากฎว่ามีวัตถุแผนที่ มาดูกันว่าแผนที่คืออะไร
HashMap ชั่วคราว <e, Object> MAP;
มันเป็น Hashmap ผู้ที่รู้ว่า HashMap จะเข้าใจว่าข้อมูลดังกล่าวจะไม่ถูกทำซ้ำ เนื่องจากวัตถุนั้นถูกเก็บไว้เป็นคีย์เมื่อฝากจะมีเพียงหนึ่งสำเนาเท่านั้นที่จะมีอยู่ใน HashMap
หลังจากเข้าใจสิ่งนี้และสิ่งอื่น ๆ คุณจะเข้าใจได้ดีมาก
ชุดต้นไม้
ชุดนี้ใช้ในการเรียงลำดับชุดซึ่งหมายความว่านอกเหนือจากความสามารถในการเรียงลำดับหนักแล้วมันยังสามารถมีฟังก์ชั่นการเรียงลำดับของตัวเอง แต่หลังจากดูรหัสของ Treeset ฉันพบว่ามันถูกนำไปใช้ในพื้นฐานของ treemap แม่นยำยิ่งขึ้นมันควรจะเป็นคลาสของ NavigableMap Treeet ขึ้นอยู่กับ Treemap โดยไม่ระบุแผนที่ตามค่าเริ่มต้น
Public Treeset () {สิ่งนี้ (treemap ใหม่ <e, Object> ()); -ดังนั้นสิ่งที่เราอาจให้ความสนใจมากขึ้นที่นี่คือวิธีการทำงานหนักของ Treyet เป็นอย่างไร? มาดูวิธีการเพิ่ม:
บูลีนสาธารณะเพิ่ม (e e) {return m.put (e, ปัจจุบัน) == null; -มันค่อนข้างคล้ายกับ hashset ซึ่งทั้งสองอย่างนี้ขึ้นอยู่กับคุณสมบัติของแผนที่เพื่อให้ได้การโหลดหนัก มันง่ายและมีประสิทธิภาพจริงๆ
ด้านบนเป็นคำอธิบายโดยละเอียดของชุดรายการและแผนที่ใน Java ที่บรรณาธิการนำมาให้คุณ ฉันหวังว่าคุณจะสนับสนุน wulin.com เพิ่มเติม ~