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

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

6. درباره لیست به ما بگویید

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

• get - عنصر را در موقعیت مشخص شده برمی گرداند (بر اساس مقدار شاخص)،
• حذف - عنصر را در موقعیت مشخص شده حذف می کند،
• set - عنصر را در موقعیت مشخص شده با عنصر مشخص شده در روش جایگزین می کند.

پیاده سازی های اصلی ArrayList و LinkedList هستند . کمی بعد در مورد آنها بیشتر صحبت خواهیم کرد. Vector لیستی است که از نظر thread ایمن است، بنابراین هر روش در این کلاس همگام می شود. اما به خاطر داشته باشید که اگر می خواهید برخی از اقدامات لیست را ایمن کنید، یک توالی کامل از عملیات را همگام خواهید کرد. و همگام سازی عملیات فردی هم امنیت کمتری دارد و هم بسیار کندتر. البته Vector سربار قفل نیز دارد، حتی اگر به قفل نیاز نداشته باشید. بنابراین، این کلاس در حال حاضر منسوخ در نظر گرفته شده و مورد استفاده قرار نمی گیرد. به هر حال: ArrayList شبیه Vector است ، اما از قفل استفاده نمی کند، بنابراین در همه جا استفاده می شود. Stack یک زیر کلاس از کلاس Vector با یک سازنده پیش‌فرض و تمام متدهای کلاس Vector ، به علاوه چند مورد از خود است (در ادامه در مورد آنها صحبت خواهیم کرد). به عنوان مثال، می توانید فرآیند را به عنوان پشته ای از پوشه ها با اسناد تصور کنید. شما یک پوشه را در بالای پشته قرار می دهید و فقط می توانید این پوشه ها را به ترتیب معکوس و از بالا شروع کنید. در واقع، این یک مکانیسم نوع LIFO است ، یعنی Last In First Out ، آخرین کسی که می آید اولین کسی است که می رود. پشته روش های خود را پیاده سازی می کند:

• فشار - عنصر ارسال شده را به بالای پشته اضافه می کند.
• peek - عنصری را که در بالای پشته قرار دارد برمی گرداند.
• pop - همچنین عنصری را که در بالای پشته است برمی گرداند، اما آن را حذف می کند.
• vala - خالی بودن پشته را بررسی می کند - درست است یا نه - نادرست است .
• جستجو - پشته را برای یک عنصر مشخص جستجو می کند. اگر عنصری پیدا شود، شماره دنباله آن نسبت به بالای پشته برگردانده می شود. اگر عنصر پیدا نشد، مقدار -1 برگردانده می شود.

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

7. درباره نقشه به ما بگویید

همانطور که در بالا گفته شد، نقشه مجموعه ای است که دارای ساختار مجزایی از رابط ها و پیاده سازی آنها است. جدا است زیرا در اینجا مقادیر یک به یک ذخیره نمی شوند، بلکه در یک جفت "کلید-مقدار" ذخیره می شوند. روش های اصلی نقشه :

• put (کلید K، مقدار V) - اضافه کردن یک عنصر به نقشه.
• get (کلید شی) - یک مقدار را با کلید جستجو کنید.
• containKey (کلید Object) - نقشه را برای وجود این کلید بررسی می کند.
• containValue(ارزش شی) - نقشه را برای وجود این مقدار بررسی می کند.
• حذف (کلید شی) - حذف یک مقدار توسط کلید آن.

همانطور که می بینید، اکثر عملیات ها با استفاده از یک کلید کار می کنند. به عنوان یک قاعده، اشیاء تغییرناپذیر به عنوان کلید انتخاب می شوند . یک مثال معمولی از این شی String است . پیاده سازی های اساسی نقشه :

1. HashMap - برای ذخیره مقادیر به ترتیب تصادفی طراحی شده است، اما به شما امکان می دهد عناصر نقشه را به سرعت جستجو کنید. به شما امکان می دهد با استفاده از کلمه کلیدی null یک کلید را مشخص کنید ، اما نه بیش از یک بار، زیرا جفت هایی با کلیدهای یکسان روی هم نوشته می شوند. شرط اصلی منحصر به فرد بودن کلیدها است: مقادیر را می توان تکرار کرد (ممکن است چندین مقدار تهی وجود داشته باشد).
2. LinkedHashMap یک آنالوگ از HashMap است که مقادیر را به ترتیبی که اضافه شده اند ذخیره می کند. بر این اساس، مانند LinkedList ، دارای یک سرصفحه است - سر یک لیست با پیوند دوگانه. وقتی مقداردهی اولیه می شود، به خودش اشاره می کند.

   LinkedHashMap همچنین دارای یک accessOrder است که نحوه دسترسی به عناصر را هنگام استفاده از تکرارکننده مشخص می کند. اگر accessOrder نادرست باشد، دسترسی به ترتیبی که عناصر درج شده اند انجام می شود. اگر درست باشد، عناصر به ترتیب آخرین دسترسی خواهند بود (آخرین عنصر دسترسی در انتها قرار می گیرد).

3. TreeMap نقشه ای است که عناصر را بر اساس مقادیر کلیدی مرتب می کند. مشابه TreeSet ، اما برای جفت ها بر اساس مقادیر کلیدی. برای تنظیم قوانین مرتب‌سازی TreeMap ، کلیدها باید رابط Comparable را پیاده‌سازی کنند . در غیر این صورت، باید یک مقایسه کننده Key-oriented (که در سازنده TreeMap مشخص شده است) وجود داشته باشد ، یک TreeSet - که با یک شی TreeMap در داخل آن پیاده سازی شده است، که در واقع، همه جادوها در آن اتفاق می افتد.

   می‌توانید در مقاله ویژگی‌های TreeMap درباره مرتب‌سازی در TreeMap با استفاده از درخت‌های قرمز-مشکی بیشتر بخوانید .

4. Hashtable شبیه HashMap است ، اما اجازه نمی دهد null ها را به عنوان کلید یا مقادیر ذخیره کنید. از نقطه نظر چند رشته ای با دقت همگام می شود، که به نوبه خود به این معنی است که از نظر چند رشته ای ایمن است. اما این پیاده سازی قدیمی و کند است، بنابراین اکنون Hashtable را در پروژه های کم و بیش جدید نخواهید دید .

8. ArrayList در مقابل LinkedList. استفاده از کدام یک ارجح است؟

این سوال شاید محبوب ترین سوال در ساختار داده باشد و مشکلاتی را به همراه دارد. قبل از پاسخ دادن به آن، بیایید در مورد این ساختارهای داده بیشتر بیاموزیم. ArrayList رابط List را پیاده سازی می کند و بر روی یک آرایه داخلی که در صورت نیاز گسترش می یابد عمل می کند. هنگامی که آرایه داخلی به طور کامل پر شد، و یک عنصر جدید باید درج شود، یک آرایه جدید با اندازه (oldSize * 1.5) +1 ایجاد می شود. پس از این، تمام داده‌های آرایه قدیمی در عنصر جدید + جدید کپی می‌شود و قدیمی توسط جمع‌آورنده زباله حذف می‌شود . متد add یک عنصر را به آخرین سلول خالی آرایه اضافه می کند. یعنی اگر از قبل 3 عنصر در آنجا داشته باشیم، عنصر بعدی را به سلول 4 اضافه می کند. بیایید عملکرد روش های اصلی را مرور کنیم:

• get(int index) - گرفتن یک عنصر در یک آرایه توسط شاخص سریعترین در O(1) است .
• add(Object obj) - اگر فضای کافی در آرایه داخلی برای یک عنصر جدید وجود داشته باشد، با درج معمولی O(1) زمان صرف می شود ، زیرا جمع به آخرین سلول هدف قرار می گیرد.

  اگر نیاز به ایجاد یک آرایه جدید و کپی کردن مطالب در آن داشته باشیم، زمان ما مستقیماً با تعداد عناصر آرایه O(n) متناسب خواهد بود .

• remove(int index) - هنگام حذف یک عنصر، به عنوان مثال، از وسط، زمان O(n/2) را دریافت می کنیم، زیرا باید عناصر را به سمت راست آن یک سلول به عقب ببریم. بر این اساس، اگر از ابتدای لیست حذف شود، O(n)، از انتها - O(1)؛
• add(int index, Object obj) - وضعیتی شبیه به حذف: هنگام اضافه کردن به وسط، باید عناصر را در یک سلول سمت راست به جلو حرکت دهیم، بنابراین زمان O(n/2) است. البته از ابتدا - O(n)، از پایان - O(1);
• set(int index, Object obj) - در اینجا وضعیت متفاوت است، زیرا شما فقط باید عنصر مورد نظر را پیدا کنید و بدون جابجایی بقیه روی آن بنویسید، بنابراین O(1).

در این مقاله درباره ArrayList بیشتر بخوانید . LinkedList دو واسط را به طور همزمان پیاده سازی می کند - List و Queue ، و بنابراین دارای ویژگی ها و روش های ذاتی در هر دو ساختار داده است. از لیست، او به یک عنصر با شاخص دسترسی پیدا کرد، از صف - وجود "سر" و "دم". در داخل، آن را به عنوان یک ساختار داده که نشان دهنده یک لیست دوگانه به هم پیوند خورده است، پیاده سازی می شود. یعنی هر عنصر به جز «دم» و «سر» پیوندی به عنصر بعدی و قبلی دارد.

• get(int index) - هنگام جستجوی عنصری که در وسط لیست قرار دارد، شروع به جستجو در تمام عناصر به ترتیب می کند تا زمانی که عنصر مورد نظر پیدا شود. به طور منطقی، جستجو باید O(n/2) باشد ، اما LinkedList نیز دارای یک دنباله است، بنابراین جستجو به طور همزمان از هر دو طرف انجام می شود. بر این اساس، زمان به O(n/4) کاهش می یابد .

  اگر عنصر به ابتدای لیست یا انتهای آن نزدیک باشد، زمان O(1) خواهد بود .

• add(Object Obj) - هنگام اضافه کردن یک عنصر جدید، عنصر "دم" پیوندی به عنصر بعدی اضافه می کند و عنصر جدید پیوندی به این عنصر قبلی دریافت می کند و به "دم" جدید تبدیل می شود. بر این اساس، زمان O(1) خواهد بود .
• remove(int index) - منطقی شبیه به روش get(int index) . برای حذف یک عنصر از وسط لیست، ابتدا باید آن را پیدا کنید. این دوباره O(n/4) است ، در حالی که خود حذف در واقع چیزی نمی گیرد، زیرا فقط نشانگر اشیاء همسایه را تغییر می دهد (آنها شروع به ارجاع به یکدیگر می کنند). اگر عنصر در ابتدا یا در پایان باشد، دوباره - O(1) ;
• add(int index, Object obj) و set(int index, Object obj) - این روش ها پیچیدگی زمانی مشابه با get(int index) خواهند داشت ، زیرا بیشتر زمان صرف جستجوی عنصر می شود. بنابراین، برای وسط لیست - O(n/4) ، برای شروع - O(1).

اطلاعات بیشتر در مورد کار با LinkedList در این مقاله توضیح داده شده است . بیایید همه اینها را در یک جدول بررسی کنیم: همانطور که احتمالاً قبلاً فهمیده اید، پاسخ دادن به این سؤال غیرممکن است. پس از همه، در شرایط مختلف آنها با سرعت های مختلف کار می کنند. بنابراین، هنگامی که از شما سؤالی مانند این پرسیده می شود، باید فوراً بپرسید که این لیست روی چه چیزی متمرکز خواهد شد و اغلب چه عملیاتی انجام می شود. با شروع از این، پاسخ دهید، اما با توضیح اینکه چرا اینطور است. بیایید مقایسه خود را خلاصه کنیم: ArrayList:

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

لینکد لیست:

• بهترین انتخاب اگر عملیات مکرر ما درج و حذف در ابتدا و میانه باشد.
• بدترین انتخاب اگر رایج ترین عملیات جستجو باشد.

9. عناصر در HashMap چگونه ذخیره می شوند؟

مجموعه HashMap شامل یک جدول آرایه داخلی Node[] است که سلول های آن را سطل نیز می نامند . گره حاوی:

• کلید - پیوند به کلید،
• ارزش - ارجاع به مقدار،
• هش - ارزش هش،
• بعدی - پیوند به گره بعدی .

یک سلول از آرایه جدول[] ممکن است حاوی ارجاع به یک شی Node با پیوند به عنصر Node بعدی باشد ، و ممکن است پیوندی به دیگری داشته باشد، و غیره... در نتیجه، این عناصر Node می توانند یک لیست پیوندی منفرد ، با عناصر با پیوند به بعدی. در این حالت، مقدار هش عناصر یک زنجیره یکسان است. پس از یک انحراف کوتاه، بیایید به نحوه ذخیره عناصر در HashMap نگاه کنیم :

1. کلید برای null بررسی می شود . اگر تهی باشد ، کلید در سلول جدول[0] ذخیره می شود زیرا کد هش برای null همیشه 0 است.
2. اگر کلید تهی نباشد، متد ()hashcode شی کلید فراخوانی می شود که کد هش آن را برمی گرداند. این کد هش برای تعیین سلول آرایه ای که شی Node در آن ذخیره می شود استفاده می شود.
3. در مرحله بعد، این هش کد در متد hash() داخلی قرار می گیرد که هش کد را محاسبه می کند، اما در اندازه آرایه جدول[] .
4. سپس، بسته به مقدار هش، Node در یک سلول خاص در آرایه جدول[] قرار می گیرد .
5. اگر سلول جدول[] مورد استفاده برای ذخیره عنصر Node فعلی خالی نباشد، اما از قبل دارای یک عنصر باشد، عناصر Node روی مقدار بعدی تکرار می شوند تا به آخرین عنصر برسند. یعنی اونی که فیلد بعدیش تهی باشه .

   در طول این جستجو، کلید شی Node محافظت شده با کلیدهای مورد جستجو مقایسه می شود:

   • اگر مطابقت پیدا شود، جستجو به پایان می رسد و گره جدید گره ای را که مطابقت در آن پیدا شده است بازنویسی می کند (فقط فیلد مقدار آن بازنویسی می شود ).
   • اگر هیچ منطبق کلیدی یافت نشد، گره جدید آخرین مورد در این لیست خواهد بود و گره قبلی پیوند بعدی به آن خواهد داشت.

این سوال اغلب در طول مصاحبه مطرح می شود: تعارض چیست ؟ وضعیتی که یک سلول از آرایه جدول[] نه یک عنصر، بلکه زنجیره ای از دو یا چند عنصر را ذخیره می کند، برخورد نامیده می شود . در موارد عادی که فقط یک عنصر در یک سلول جدول[] ذخیره می‌شود ، دسترسی به عناصر HashMap دارای پیچیدگی زمانی O(1) ثابت است . اما هنگامی که یک سلول با عنصر مورد نظر شامل زنجیره ای از عناصر ( برخورد )، O(n) است ، زیرا در این مورد زمان با تعداد عناصر مرتب شده متناسب است.

10. تکرار کننده را توضیح دهید

در نمودار نگاشت سلسله مراتب مجموعه در بالا، رابط Collection جایی بود که کل سلسله مراتب شروع شد، اما در عمل کاملاً اینطور نیست. مجموعه از یک اینترفیس با متد iterator() به ارث می برد ، که یک شی را برمی گرداند که رابط Iterator<E> را پیاده سازی می کند . رابط Iterator به شکل زیر است:

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() - با فراخوانی این متد، می توانید عنصر بعدی را دریافت کنید. hasNext() - به شما امکان می دهد بفهمید که آیا عنصر بعدی وجود دارد یا خیر و آیا به پایان مجموعه رسیده است یا خیر. و هنگامی که هنوز عناصر وجود دارد، hasNext() true را برمی گرداند . معمولاً hasNext() قبل از متد ()next فراخوانی می شود ، زیرا next() یک NoSuchElementException را زمانی که به انتهای مجموعه می رسد پرتاب می کند . remove() - عنصری را که با آخرین فراخوانی به next() بازیابی شده بود حذف می کند . هدف Iterator تکرار روی عناصر است. مثلا:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

در واقع، حلقه for-هر در زیر هود با استفاده از یک تکرار کننده پیاده سازی می شود. شما می توانید بیشتر در مورد این در اینجا بخوانید . List نسخه مخصوص به خود را از یک تکرار کننده ارائه می دهد، اما یک نسخه سردتر و پیچیده تر - ListIterator . این رابط Iterator را گسترش می دهد و روش های اضافی دارد:

• اگر عنصر قبلی در مجموعه وجود داشته باشد، hasPrevious درست است، در غیر این صورت false.
• previous عنصر فعلی را برمی گرداند و به عنصر قبلی منتقل می شود. اگر هیچ کدام وجود نداشته باشد، یک NoSuchElementException پرتاب می شود.
• add شیء ارسال شده را قبل از عنصر وارد می کند تا با فراخوانی بعدی به next() برگردانده شود .
• set به عنصر فعلی یک مرجع به شیء ارسال شده اختصاص می دهد.
• nextIndex شاخص عنصر بعدی را برمی گرداند. اگر چنین چیزی وجود نداشته باشد، اندازه لیست برگردانده می شود.
• previousIndex شاخص عنصر قبلی را برمی گرداند. اگر وجود نداشته باشد، عدد -1 برگردانده می شود.

خوب، این همه برای من امروز است. امیدوارم پس از خواندن این مقاله حتی به رویای گرامی خود نزدیک شوید - توسعه دهنده شوید.