สิ่งที่พวกเขาอาจถามในการสัมภาษณ์: โครงสร้างข้อมูลใน Java ส่วนที่ 1

สวัสดี! ไม่ว่าคุณจะมองอย่างไร คุณไม่สามารถเป็นนักพัฒนาได้โดยไม่ผ่านการสัมภาษณ์ทางเทคนิค มีเทคโนโลยีมากมายที่เกี่ยวข้องกับ Java และเป็นไปไม่ได้ที่จะเรียนรู้ทุกสิ่ง ตามกฎแล้ว เราจะถามสิ่งที่เฉพาะเจาะจงในระหว่างการสัมภาษณ์เฉพาะในกรณีที่พวกเขากำลังมองหานักพัฒนาที่มีประสบการณ์ที่ดีในกรอบงานที่สำคัญสำหรับโครงการ หากเป็นเช่นนั้น คุณจะถูกไล่ล่าไปรอบๆ เฟรมเวิร์กนี้ด้วยความเร็วเต็มที่ ไม่ต้องสงสัยเลย แต่ตอนนี้เรากำลังพูดถึงพื้นฐานที่ Java Developer ทุกคนควรรู้ เกี่ยวกับความรู้คลาสสิกที่เป็นจุดเริ่มต้นของทุกสิ่ง วันนี้ฉันอยากจะพูดถึงหนึ่งในหัวข้อพื้นฐานของการสัมภาษณ์ - โครงสร้างข้อมูลใน Java ดังนั้น แทนที่จะไปยุ่งวุ่นวาย เรามาเริ่มกันเลยดีกว่า ค้นหารายการคำถามที่คุณอาจถูกถามเกี่ยวกับหัวข้อนี้ในระหว่างการสัมภาษณ์

1. บอกเราเล็กน้อยเกี่ยวกับโครงสร้างข้อมูล

โครงสร้างข้อมูลเป็นที่เก็บข้อมูลที่มีข้อมูลที่มีโครงสร้างในลักษณะใดลักษณะหนึ่ง โครงสร้างเหล่านี้ได้รับการออกแบบมาเพื่อประสิทธิภาพการทำงานบางอย่างที่มีประสิทธิภาพ ตัวอย่างทั่วไปของโครงสร้างข้อมูลคือ:

• อาร์เรย์
• กอง,
• คิว
• รายการที่เกี่ยวข้อง
• กราฟ,
• ต้นไม้,
• ต้นไม้คำนำหน้า,
• ตารางแฮช

คุณสามารถหาข้อมูลเพิ่มเติมเกี่ยวกับพวกเขาได้ที่นี่และที่นี่ ข้อมูลเป็นองค์ประกอบสำคัญในโปรแกรม และโครงสร้างช่วยให้สามารถจัดเก็บข้อมูลนี้ในรูปแบบเฉพาะที่มีโครงสร้างชัดเจน ไม่ว่าแอปพลิเคชันของคุณจะทำอะไรก็ตาม ลักษณะนี้จะปรากฏในนั้นเสมอ: หากเป็นร้านค้าบนเว็บ ข้อมูลเกี่ยวกับผลิตภัณฑ์จะถูกจัดเก็บ หากเป็นเครือข่ายโซเชียล ข้อมูลเกี่ยวกับผู้ใช้และไฟล์ และอื่นๆ

2. คุณรู้อะไรเกี่ยวกับอาร์เรย์บ้าง

อาร์เรย์เป็นคอนเทนเนอร์สำหรับจัดเก็บค่าประเภทเดียวกันซึ่งมีการระบุจำนวนไว้ล่วงหน้า ตัวอย่างการสร้างอาร์เรย์ที่มีค่าสตริง:

String[] strArray = {"Java","is","the","best","language"};

เมื่อสร้างอาร์เรย์ หน่วยความจำจะถูกจัดสรรให้กับองค์ประกอบทั้งหมด: ยิ่งมีการระบุเซลล์สำหรับองค์ประกอบมากขึ้นในขั้นต้น หน่วยความจำก็จะยิ่งได้รับการจัดสรรมากขึ้นเท่านั้น หากมีการสร้างอาร์เรย์ว่างที่มีจำนวนเซลล์จำนวนหนึ่ง องค์ประกอบทั้งหมดของอาร์เรย์จะได้รับการกำหนดค่าเริ่มต้น ตัวอย่างเช่น:

int[] arr = new int[10];

ดังนั้นสำหรับอาร์เรย์ที่มีองค์ประกอบของ ประเภท บูลีน ค่า เริ่มต้น ( ค่า เริ่มต้น ) จะเป็นเท็จสำหรับอาร์เรย์ที่มีค่าตัวเลข - 0 โดยมีองค์ประกอบของ ประเภท ถ่าน - \u0000 . สำหรับอาร์เรย์ประเภทคลาส (วัตถุ) - null (ไม่ใช่สตริงว่าง - “” แต่โดยเฉพาะnull ) นั่นคือในตัวอย่างข้างต้น ค่าทั้งหมดของ อาร์เรย์ arrจะเป็น 0 จนกว่าจะระบุโดยตรง อาร์เรย์ไม่ใช่ไดนามิกต่างจากคอลเลกชัน เมื่อประกาศอาร์เรย์ที่มีขนาดที่กำหนดแล้ว ขนาดนั้นจะไม่สามารถเปลี่ยนแปลงได้ ในการเพิ่มองค์ประกอบใหม่ให้กับอาร์เรย์ คุณต้องสร้างอาร์เรย์ใหม่ที่ใหญ่ขึ้นและคัดลอกองค์ประกอบทั้งหมดจากอันเก่าลงไป (นี่คือวิธีการทำงานของ ArrayList) มีจุดหนึ่งที่ทุกคนไม่รู้และสามารถจับได้ค่อนข้างดี มีตัวแปรสองประเภทใน Java - ประเภทธรรมดาและการอ้างอิงไปยังอ็อบเจ็กต์แบบเต็ม ข้อใดคืออาร์เรย์? ตัวอย่างเช่น ที่นี่:

int[] arr = new int[10];

ดูเหมือนว่าทุกอย่างจะง่าย - เหล่านี้คือ 10 int element แล้วเราจะพูดได้ว่านี่เป็นประเภทธรรมดาเหรอ? ไม่ว่ามันจะเป็นอย่างไร ใน Java อาร์เรย์คือวัตถุที่ถูกสร้างขึ้นแบบไดนามิกและสามารถกำหนดให้กับตัวแปรประเภทวัตถุได้ วิธีการทั้งหมดของคลาส Object สามารถเรียกใช้บนอาร์เรย์ได้ ดังนั้นเราจึงสามารถเขียนได้:

Object arr = new int[]{7,5,4,3};
System.out.println(arr.toString());

เมื่อส่งออกไปยังคอนโซลคุณอาจได้รับสิ่งที่ต้องการ: อ่านเพิ่มเติมเกี่ยวกับคุณสมบัติของอาร์เรย์ใน Java ในบทความเกี่ยวกับ Java Array เพื่อรวบรวมความรู้ คุณสามารถแก้ไขปัญหาต่างๆ จากคอลเล็กชันนี้ได้

3. อธิบายลำดับชั้นของคอลเลกชัน

คอลเลกชันจะใช้ในสถานการณ์ที่คุณต้องการความยืดหยุ่นเมื่อทำงานกับข้อมูล คอลเลกชันสามารถเพิ่มองค์ประกอบ ลบองค์ประกอบ และดำเนินการอื่นๆ อีกมากมาย มีการใช้งานที่แตกต่างกันมากมายใน Java และเราเพียงแค่ต้องเลือกคอลเลกชันที่เหมาะสมสำหรับสถานการณ์ปัจจุบัน โดยทั่วไป เมื่อคุณพูดถึง อินเทอร์เฟ ซของคอลเลกชัน คุณจะถูกขอให้แสดงรายการการใช้งานบางส่วนและความสัมพันธ์กับMap เรามาดูกันดีกว่า ดังนั้นคอลเลกชันและแผนที่จึงเป็นสองลำดับชั้นที่แตกต่างกันสำหรับโครงสร้างข้อมูล ลำดับชั้น ของคอลเลกชัน มีลักษณะดังนี้ : อินเทอร์เฟซของคอลเลกชันคือลิงก์หลักด้านบนที่มีรายการวิธีการพื้นฐาน ซึ่งเป็นที่มาของโครงสร้างข้อมูลพื้นฐานสามประเภท- Set , List , Queue Set<T>เป็นอินเทอร์เฟซที่แสดงถึงคอลเลกชันของวัตถุที่แต่ละวัตถุไม่ซ้ำกัน List<T>เป็นอินเทอร์เฟซที่แสดงลำดับของวัตถุที่เรียกว่ารายการ Queue<T>เป็นอินเทอร์เฟซที่รับผิดชอบโครงสร้างที่จัดเป็นคิว (การจัดเก็บองค์ประกอบตามลำดับ) ตามที่กล่าวไว้ก่อนหน้านี้Mapเป็นลำดับชั้นที่แยกจากกัน: Map<K, V>เป็นอินเทอร์เฟซที่แสดงพจนานุกรมซึ่งมีองค์ประกอบต่างๆ อยู่เป็นคู่คีย์-ค่า นอกจากนี้ คีย์ทั้งหมด (K) จะไม่ซ้ำกันภายใน ออบเจ็ก ต์Map คอลเลกชันประเภทนี้ช่วยให้ค้นหาองค์ประกอบได้ง่ายขึ้นหากเราทราบคีย์ - ตัวระบุเฉพาะของออบเจ็กต์

4. คุณรู้อะไรเกี่ยวกับเซ็ทบ้าง?

ตามที่ระบุไว้ก่อนหน้านี้ คอลเลกชันนี้มีองค์ประกอบที่เป็นเอกลักษณ์มากมาย กล่าวอีกนัยหนึ่ง อ็อบเจ็กต์เดียวกันไม่สามารถปรากฏมากกว่าหนึ่งครั้ง ใน ชุด Java ฉันอยากจะชี้ให้เห็นว่าเราไม่สามารถแยกองค์ประกอบออก จาก Set by Number (ดัชนี) ได้ - โดยใช้กำลังเดรัจฉานเท่านั้น สิ่งสำคัญคือ การใช้งาน Set ที่แตกต่างกัน มีวิธีการจัดโครงสร้างข้อมูลที่แตกต่างกัน เราจะพิจารณาการใช้งานเฉพาะเพิ่มเติม ดังนั้นการใช้งานหลักของSet : HashSetจึงเป็นชุดที่ยึดตามตารางแฮช ซึ่งจะช่วยในการค้นหา ใช้ฟังก์ชันแฮชซึ่งปรับปรุงประสิทธิภาพระหว่างการค้นหาและการแทรก ไม่ว่าจำนวนองค์ประกอบจะเป็นอย่างไร โดยทั่วไป การแทรกและการค้นหา (บางครั้งก็เป็นการลบ) จะดำเนินการในเวลาที่ใกล้เคียงกับค่าคงที่ - O(1) เราจะมาดูรายละเอียดเกี่ยวกับฟังก์ชันแฮชกันในภายหลัง ฉันอยากจะทราบด้วยว่าHashSetมีHashMapซึ่งเป็นที่ที่ความมหัศจรรย์ทั้งหมดเกิดขึ้น นี่คือบทความโดยละเอียดเกี่ยวกับ HashSet ใน Java LinkedHashSet - คลาสนี้ขยายHashSetโดยไม่ต้องเพิ่มวิธีการใหม่ใด ๆ เช่นเดียวกับLinkedListคลาสนี้จะรักษารายการเชื่อมโยงขององค์ประกอบของชุดตามลำดับที่แทรกไว้ ซึ่งจะทำให้คุณสามารถจัดระเบียบลำดับที่จำเป็นใน การใช้งาน Set ที่กำหนด ได้ คลาสTreeSetสร้างชุดที่ยึดตามต้นไม้สีแดงดำเพื่อจัดระเบียบโครงสร้างของการจัดเก็บองค์ประกอบ กล่าวอีกนัยหนึ่ง ในชุดที่กำหนด เราสามารถจัดเรียงองค์ประกอบจากน้อยไปหามากได้ หากเราใช้วัตถุมาตรฐานจาก "กล่อง" เช่นIntegerเราก็ไม่จำเป็นต้องดำเนินการใดๆ เพื่อจัดเรียงชุดของ Integers ตามลำดับจากน้อยไปหามาก:

TreeSet set = new TreeSet<>();
set.add(4);
set.add(2);
set.add(3);
set.add(1);

System.out.println(set);

และในคอนโซลเราจะได้ผลลัพธ์: นั่นคือในชุด นี้ ตัวเลขจะถูกจัดเก็บในรูปแบบการเรียงลำดับ หากเราใช้ องค์ประกอบ StringในTreeSetองค์ประกอบเหล่านั้นจะถูกจัดเรียง แต่จะเรียงตามตัวอักษร แล้วถ้าเรามีคลาสมาตรฐาน (กำหนดเอง) ล่ะ? ออบเจ็กต์ของคลาสนี้จะจัดโครงสร้างTreeSetอย่างไร หากเราพยายามกำหนดวัตถุใด ๆ ให้กับชุด นี้ :

TreeSet set = new TreeSet<>();
set.add(new Cat(4, "Murzik"));
set.add(new Cat(2, "Barsik"));
set.add(new Cat(3, "Гарфилд"));

System.out.println(set);

เราจะได้รับClassCastExceptionเนื่องจากTreeSetไม่ทราบวิธีจัดเรียงวัตถุประเภทนี้ ในกรณีนี้ เราจำเป็นต้องมีออบเจ็กต์ที่กำหนดเองเพื่อใช้ อินเทอร์เฟซ ที่เปรียบเทียบได้และ วิธีการ เปรียบเทียบTo :

public class Cat implements Comparable {
    int age;
    String name;

   public Cat(int age, String name) {
       this.age = age;
       this.name = name;
   }

   @Override
   public int compareTo(Cat cat) {
       return age > cat.age ? 1 : -1;
   }

   @Override
   public String toString() {
       return "Cat{" +
               "age=" + age +
               ", name='" + name + '\'' +
               '}';
   }
}

ดังที่คุณสังเกตเห็นว่า เมธอด comparisonToส่งคืนint :

• 1 ถ้าวัตถุปัจจุบัน (นี้) ถือว่าใหญ่
• -1 หากวัตถุปัจจุบันถือว่าเล็กกว่าวัตถุที่มาเป็นอาร์กิวเมนต์
• 0 ถ้าวัตถุเท่ากัน (ในกรณีนี้เราจะไม่ใช้)

ในกรณีนี้TreeSet ของเรา จะทำงานอย่างถูกต้องและแสดงผลลัพธ์: อีกวิธีหนึ่งคือการสร้างคลาสการเรียงลำดับแยกต่างหากที่ใช้ อินเทอร์เฟซ ตัวเปรียบเทียบ และ วิธีการเปรียบเทียบ :

public class CatComparator implements Comparator {

   @Override
   public int compare(Cat o1, Cat o2) {
       return o1.age > o2.age ? 1 : -1;
   }
}

ในกรณีนี้ เพื่อใช้งาน เราต้องตั้งค่าอ็อบเจ็กต์ของคลาสนี้ให้กับTreeSet Constructor :

TreeSet set = new TreeSet<>(new CatComparator());

หลังจากนี้ ออบเจ็กต์ทั้งหมดของคลาสCatที่รวมอยู่ในTreeSetจะถูกจัดเรียงโดยใช้ คลาส Cat Comparator คุณสามารถเรียนรู้ เพิ่มเติมเกี่ยวกับComparatorและComparableใน Java ได้จากบทความนี้

5. บอกเราเกี่ยวกับคิว

Queueเป็นอินเทอร์เฟซที่รับผิดชอบโครงสร้างที่จัดเป็นคิวซึ่งเป็นโครงสร้างข้อมูลที่จัดเก็บองค์ประกอบตามลำดับ เช่น จากคิวของคน คนแรกที่เข้าจะเป็นคนที่มาถึงเร็วกว่าคนอื่น และคนสุดท้ายจะเป็นคนที่มาช้ากว่าคนอื่นๆ วิธีการนี้เรียกว่าFIFOซึ่งก็คือเข้าก่อนออกก่อน วิธีการ คิวที่ไม่ซ้ำมุ่งเน้นไปที่การทำงานกับองค์ประกอบแรกหรือองค์ประกอบสุดท้าย ตัวอย่างเช่น:

• เพิ่มและเสนอ - แทรกองค์ประกอบที่ส่วนท้ายของคิว
• ลบ - ดึงและลบส่วนหัวของคิวนี้
• peek - ดึงข้อมูลแต่ไม่ได้ลบส่วนหัวของคิว

ส่วนที่ 2