آنچه ممکن است در مصاحبه بپرسند: ساختارهای داده در جاوا. قسمت 1

سلام! مهم نیست که چگونه به آن نگاه کنید، بدون گذراندن موفقیت آمیز مصاحبه ورودی فنی نمی توانید یک توسعه دهنده شوید. فناوری های زیادی در رابطه با جاوا وجود دارد و یادگیری همه چیز غیرممکن است. به عنوان یک قاعده، فقط در صورتی که به دنبال توسعه‌دهنده‌ای با تجربه خوب در چارچوبی مهم برای پروژه هستند، در طول مصاحبه‌ها چیزی خاص پرسیده می‌شود. اگر اینطور باشد، شما با سرعت تمام از طریق این چارچوب هدایت خواهید شد، شکی ندارید. اما اکنون در مورد پایه ای صحبت می کنیم که هر توسعه دهنده جاوا باید بداند. درباره آن دانش کلاسیک که همه چیز از آن شروع می شود. امروز می خواهم به یکی از موضوعات اساسی هر مصاحبه بپردازم - ساختارهای داده در جاوا . بنابراین، به جای کوبیدن در اطراف بوش، بیایید شروع کنیم. فهرستی از سوالاتی را که ممکن است در طول مصاحبه درباره این موضوع از شما پرسیده شود، بیابید.

1. کمی در مورد ساختار داده برای ما توضیح دهید

ساختار داده یک انبار داده است که حاوی اطلاعاتی است که به روشی خاص ساختار یافته است. این سازه ها برای اجرای کارآمد عملیات خاص طراحی شده اند. نمونه های معمولی از ساختارهای داده عبارتند از:

• آرایه ها،
• پشته ها،
• صف ها،
• لیست های مرتبط
• نمودارها،
• درختان،
• درختان پیشوند،
• جدول هش

می توانید در اینجا و اینجا اطلاعات بیشتری در مورد آنها بیابید . داده ها یک جزء کلیدی در یک برنامه هستند و ساختارها به این داده ها اجازه می دهند در یک فرم خاص و به وضوح ساختار یافته ذخیره شوند. هر کاری که برنامه شما انجام دهد، این جنبه همیشه در آن وجود دارد: اگر یک فروشگاه اینترنتی باشد، اطلاعات مربوط به محصولات ذخیره می شود، اگر یک شبکه اجتماعی باشد، داده های مربوط به کاربران و فایل ها و غیره.

2. درباره آرایه ها چه می دانید؟

آرایه محفظه ای برای ذخیره مقادیر از همان نوع است که تعداد آنها از قبل مشخص شده است. نمونه ای از ایجاد یک آرایه با مقادیر رشته:

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

هنگام ایجاد یک آرایه، حافظه برای همه عناصر آن تخصیص داده می شود: هرچه سلول های بیشتری برای عناصر در ابتدا مشخص شود، حافظه بیشتری تخصیص داده می شود. اگر یک آرایه خالی با تعداد مشخصی سلول ایجاد شود، به تمام عناصر آرایه مقادیر پیش فرض اختصاص داده می شود. مثلا:

int[] arr = new int[10];

بنابراین، برای یک آرایه با عناصر نوع بولی ، مقادیر اولیه ( پیش‌فرض ) نادرست خواهد بود ، برای آرایه‌هایی با مقادیر عددی - 0، با عناصری از نوع char - \u0000 . برای آرایه ای از نوع کلاس (اشیاء) - null (نه رشته های خالی - "" بلکه به طور خاص null ). یعنی در مثال بالا، تمام مقادیر آرایه arr تا زمانی که مستقیماً مشخص نشده باشند 0 خواهند بود. برخلاف مجموعه ها، آرایه ها پویا نیستند. هنگامی که یک آرایه با اندازه مشخصی اعلام شد، خود اندازه را نمی توان تغییر داد. برای افزودن یک عنصر جدید به یک آرایه، باید یک آرایه بزرگتر جدید ایجاد کنید و همه عناصر را از قبلی در آن کپی کنید (ArrayList به این ترتیب کار می کند). یک نکته وجود دارد که همه نمی دانند و می توان به خوبی از آن گرفتار شد. دو نوع متغیر در جاوا وجود دارد - انواع ساده و ارجاع به اشیاء کامل. کدام یک از اینها آرایه هستند؟ به عنوان مثال، در اینجا:

int[] arr = new int[10];

به نظر می رسد که همه چیز ساده است - اینها 10 عنصر int هستند . بنابراین، می توان گفت که این یک نوع ساده است؟ مهم نیست چگونه باشد. در جاوا، آرایه ها اشیا هستند، به صورت پویا ایجاد می شوند و می توان آنها را به متغیرهایی از نوع Object نسبت داد. تمام متدهای کلاس Object را می توان روی یک آرایه فراخوانی کرد. بنابراین حتی می توانیم بنویسیم:

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

هنگام خروجی به کنسول ممکن است چیزی شبیه به: در این مقاله در مورد Java Array در مورد ویژگی های آرایه ها در جاوا بیشتر بخوانید . برای تثبیت دانش خود می توانید چندین مشکل را از این مجموعه حل کنید .

3. سلسله مراتب مجموعه ها را توضیح دهید

مجموعه ها در موقعیت هایی استفاده می شوند که در هنگام کار با داده ها به انعطاف پذیری نیاز دارید. مجموعه ها می توانند یک عنصر اضافه کنند، یک عنصر را حذف کنند و بسیاری از عملیات های دیگر را انجام دهند. پیاده سازی های مختلفی در جاوا وجود دارد و ما فقط باید مجموعه مناسبی را برای شرایط فعلی انتخاب کنیم. معمولاً، وقتی رابط مجموعه را ذکر می‌کنید ، از شما خواسته می‌شود که برخی از پیاده‌سازی‌های آن و ارتباط آن با Map را فهرست کنید . خب بیایید بفهمیم بنابراین، مجموعه و نقشه دو سلسله مراتب متفاوت برای ساختارهای داده هستند. سلسله مراتب مجموعه چگونه به نظر می رسد : رابط مجموعه ، لینک بالای کلیدی با لیستی از روش های اساسی است که از آن سه نوع اصلی ساختار داده منشأ می گیرند - Set ، List ، Queue . Set<T> یک رابط است که مجموعه ای از اشیاء را نشان می دهد که در آن هر شی منحصر به فرد است. List<T> یک رابط است که نشان دهنده یک دنباله مرتب از اشیاء به نام لیست است. Queue<T> رابطی است که مسئول ساختارهایی است که به صورت صف (ذخیره متوالی عناصر) سازماندهی شده اند. همانطور که قبلاً ذکر شد، Map یک سلسله مراتب جداگانه است: Map<K, V> یک رابط است که یک فرهنگ لغت را نشان می دهد که در آن عناصر به صورت جفت کلید-مقدار قرار می گیرند. علاوه بر این، تمام کلیدها (K) در شی Map منحصر به فرد هستند . اگر کلید را بدانیم - شناسه منحصر به فرد شیء، این نوع مجموعه، یافتن یک عنصر را آسان تر می کند.

4. درباره ست چه می دانید؟

همانطور که قبلا گفته شد، این مجموعه دارای عناصر منحصر به فرد بسیاری است. به عبارت دیگر، یک شیء مشابه نمی تواند بیش از یک بار در یک مجموعه جاوا ظاهر شود. همچنین می‌خواهم به این نکته اشاره کنم که ما نمی‌توانیم یک عنصر را از یک مجموعه با عدد (شاخص) استخراج کنیم - فقط با نیروی brute force. نکته مهم این است که پیاده سازی های مختلف Set راه های متفاوتی برای ساختاردهی داده ها دارند. ما پیاده سازی های خاص را بیشتر در نظر خواهیم گرفت. بنابراین، پیاده سازی های اصلی Set : HashSet مجموعه ای است که بر اساس جدول هش است که به نوبه خود به جستجو کمک می کند. از یک تابع هش استفاده می کند که عملکرد را در هنگام جستجو و درج بهبود می بخشد. صرف نظر از تعداد عناصر، به طور کلی، درج و جستجو (گاهی اوقات حذف) در زمان نزدیک به ثابت - O(1) انجام می شود. کمی بعد به تابع هش با جزئیات بیشتری نگاه خواهیم کرد. همچنین می‌خواهم توجه داشته باشم که HashSet حاوی HashMap است ، جایی که همه جادوها در آن اتفاق می‌افتد. در اینجا یک مقاله مفصل در مورد HashSet در جاوا آمده است . LinkedHashSet - این کلاس بدون افزودن هیچ روش جدیدی HashSet را گسترش می دهد. مانند LinkedList ، این کلاس یک لیست پیوندی از عناصر یک مجموعه را به ترتیبی که در آن درج شده اند حفظ می کند. این به شما امکان می دهد تا ترتیب لازم را در اجرای مجموعه داده شده سازماندهی کنید . کلاس TreeSet مجموعه ای را ایجاد می کند که بر اساس یک درخت قرمز-مشکی برای سازماندهی ساختار عناصر ذخیره سازی است. به عبارت دیگر، در یک مجموعه داده شده می توانیم عناصر را به ترتیب صعودی مرتب کنیم. اگر از برخی از اشیاء استاندارد از "جعبه" استفاده کنیم، به عنوان مثال، عدد صحیح ، پس برای مرتب کردن مجموعه اعداد صحیح به ترتیب صعودی نیازی به انجام کاری نداریم:

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 نمی داند چگونه اشیاء از این نوع را مرتب کند. در این مورد، ما به شی سفارشی خود برای پیاده سازی رابط Comparable و متد compareTo آن نیاز داریم :

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 + '\'' +
               '}';
   }
}

همانطور که متوجه شدید، متد compareTo یک 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 تنظیم کنیم :

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

پس از این، تمام اشیاء کلاس Cat که در TreeSet گنجانده شده اند با استفاده از کلاس Cat Comparator مرتب می شوند . از این مقاله می‌توانید درباره Comparator و Comparable در جاوا اطلاعات بیشتری کسب کنید .

5. در مورد Queue به ما بگویید

صف یک رابط است که مسئول ساختارهایی است که به صورت صف سازماندهی شده اند - ساختار داده ای که عناصر را به صورت متوالی ذخیره می کند. به عنوان مثال، از یک صف افراد، اولین نفری که وارد می شود، کسی است که زودتر از دیگران رسیده است و آخرین نفر، کسی است که دیرتر از دیگران رسیده است. این روش FIFO نامیده می شود ، یعنی First in First Out . متدهای صف منحصر به فرد بر کار با اولین یا آخرین عنصر تمرکز می کنند، به عنوان مثال:

• افزودن و پیشنهاد - یک عنصر را در انتهای صف درج می کند،
• remove - هدر این صف را بازیابی و حذف می کند،
• peek - هدر صف را بازیابی می کند اما حذف نمی کند.

قسمت 2