تجزیه و تحلیل پرسش و پاسخ از مصاحبه برای توسعه دهنده جاوا. قسمت 9

آتش بازی! برنامه نویس بودن کار آسانی نیست. شما باید دائماً یاد بگیرید، همیشه چیز جدیدی یاد بگیرید. اما، مانند هر کسب و کار دیگری، سخت ترین کار شروع کردن، برداشتن اولین قدم به سمت هدف است. و از آنجایی که در این سایت نشسته اید و این مقاله را می خوانید، مرحله اول را به پایان رسانده اید. این بدان معنی است که اکنون باید هدفمند به سمت هدف خود حرکت کنید، بدون اینکه در طول مسیر خود را کاهش دهید یا خاموش کنید. اگر من درست متوجه شده باشم، هدف شما این است که یک توسعه دهنده جاوا شوید یا اگر یکی از آنها هستید، دانش خود را افزایش دهید. اگر چنین است، پس شما در جای درستی هستید، زیرا ما به تجزیه و تحلیل لیست گسترده ای از 250+ سوال مصاحبه توسعه دهندگان جاوا ادامه خواهیم داد. بیا ادامه بدهیم!

مجموعه ها

84. در مورد تکرار کننده ها و کاربرد آنها بگویید

مجموعه‌ها یکی از موضوعات مورد علاقه در هر مصاحبه توسعه‌دهنده جاوا هستند، و هنگام صحبت در مورد سلسله مراتب مجموعه، نامزدها اغلب می‌گویند که با رابط مجموعه شروع می‌شود . اما این درست نیست، زیرا در بالای این رابط رابط دیگری وجود دارد - Iterable . این رابط متد iterator() را نشان می دهد که به شما امکان می دهد یک شی Iterator را برای مجموعه فعلی فراخوانی کنید. و این شی Iterator دقیقا چیست ؟ Iterator یک شی است که توانایی حرکت در یک مجموعه و تکرار روی عناصر را بدون نیاز کاربر به دانستن اجرای یک مجموعه خاص فراهم می کند. یعنی این نوعی اشاره به عناصر مجموعه است که همانطور که بود به مکان خاصی در آن نگاه می کند. تکرار کننده روش های زیر را دارد:

• hasNext() - اگر عنصری بعد از اشاره گر وجود داشته باشد true را برمی گرداند (این روش به شما امکان می دهد بفهمید که آیا به پایان مجموعه رسیده است یا خیر).
• next() - عنصر بعدی را بعد از اشاره گر برمی گرداند. اگر وجود نداشته باشد، NoSuchElementException پرتاب می شود . یعنی قبل از استفاده از این روش، بهتر است از وجود عنصر مطمئن شوید - با استفاده از hasNext() ;
• remove() - آخرین عنصر دریافتی از مجموعه را با استفاده از متد next() حذف می کند . اگر ()next قبل از فراخوانی remove() هرگز فراخوانی نشده باشد ، یک استثنا ایجاد می شود - IllegalStateException ;
• forEachRemaining(<Consumer>) - عمل تصویب شده را با هر عنصر مجموعه انجام می دهد (روش در جاوا 8 ظاهر شد).

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

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

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

iterator.forEachRemaining(x -> System.out.print(x));

اما پس از این، تکرار کننده برای استفاده بیشتر نامناسب می شود، زیرا کل لیست را طی می کند، و یک تکرار کننده معمولی روش هایی برای عقب نشینی ندارد. در اینجا ما به تدریج به LinkedList ، یعنی متد listIterator() آن نزدیک می‌شویم ، که نوع مدرنی از iterator - ListIterator را برمی‌گرداند . علاوه بر روش‌های تکرارکننده معمولی (استاندارد)، این روش روش‌های دیگری نیز دارد:

• add(<Element>) - یک عنصر جدید را در لیست قرار می دهد.
• hasPrevious() - اگر عنصری قبل از اشاره گر وجود داشته باشد (خواه عنصر قبلی وجود داشته باشد) true را برمی گرداند.
• nextIndex() - ایندکس را در لیست عنصر بعدی بعد از اشاره گر برمی گرداند.
• previous() - عنصر قبلی (تا نشانگر) را برمی گرداند.
• previousIndex() - شاخص عنصر قبلی را برمی گرداند.
• set(<Element>) - جایگزین آخرین عنصر بازگردانده شده توسط متدهای next() یا previous() می شود .

همانطور که می بینید، عملکرد این تکرار کننده بسیار جالب تر است: به شما امکان می دهد در هر دو جهت حرکت کنید و هنگام کار با عناصر، دستان خود را آزاد می کند. همچنین، هنگامی که مردم در مورد تکرار کننده ها صحبت می کنند، گاهی اوقات منظور خود الگو هستند. برای اینکه دچار مشکل نشوید و قانع کننده در مورد آن صحبت کنید، این مقاله را در مورد الگوی Iterator بخوانید .

85. سلسله مراتب مجموعه در Java Collection Framework چگونه است؟

دو سلسله مراتب مجموعه در جاوا وجود دارد. اولین سلسله مراتب خود سلسله مراتب مجموعه با ساختار زیر است : به نوبه خود به زیر مجموعه های زیر تقسیم می شود:

• Set رابطی است که چنین ساختار داده ای را به عنوان مجموعه ای حاوی عناصر منحصر به فرد (غیر تکرار شونده) نامرتب توصیف می کند. این رابط دارای پیاده سازی های استاندارد است - TreeSet ، HashSet و LinkedHashSet .
• لیست یک رابط است که ساختار داده ای را توصیف می کند که دنباله ای مرتب از اشیاء را ذخیره می کند. نمونه هایی که در یک لیست موجود هستند را می توان با فهرست آنها در این مجموعه درج و حذف کرد (مشابه با یک آرایه، اما با تغییر اندازه پویا). این رابط پیاده سازی های استانداردی دارد - ArrayList ، Vector ( منسوخ شده و در واقع استفاده نشده است ) و LinkedList .
• Queue رابطی است که ساختار داده ای را توصیف می کند که عناصر را به شکل یک صف ذخیره می کند که از قانون FIFO - First In First Out پیروی می کند . این رابط پیاده‌سازی‌های استاندارد زیر را دارد: LinkedList (بله، Queue را نیز پیاده‌سازی می‌کند ) و PriotityQueue .

سلسله مراتب دوم مجموعه ها Map است که ساختار زیر را دارد: در این مجموعه هیچ تقسیم بندی به زیر مجموعه ها وجود ندارد (زیرا سلسله مراتب نقشه خود چیزی شبیه به یک زیر مجموعه است، اما به طور جداگانه قرار دارد). پیاده سازی های استاندارد نقشه عبارتند از : Hashtable (منسوخ تلقی می شود)، LinkedHashMap و TreeMap . در واقع، وقتی در مورد مجموعه سؤال می شود ، معمولاً هر دو سلسله مراتب در نظر گرفته می شوند.

86. ساختار داخلی ArrayList چیست؟

ArrayList شبیه به یک آرایه است، اما با قابلیت گسترش پویا. چه مفهومی داره؟ واقعیت این است که ArrayList بر اساس یک آرایه معمولی کار می کند، یعنی عناصر را در یک آرایه داخلی ذخیره می کند (اندازه پیش فرض آن 10 سلول است). هنگامی که آرایه داخلی پر است، یک آرایه جدید ایجاد می شود که اندازه آن با فرمول تعیین می شود:

<размерТекущегоМассива> * 3 / 2  + 1

یعنی اگر اندازه آرایه ما 10 باشد، اندازه آرایه جدید خواهد بود: 10 * 3 / 2 + 1 = 16. سپس، تمام مقادیر آرایه اول (قدیمی) با استفاده از آرایه در آن کپی می شوند. روش System.arraycopy () native ، و اولین آرایه حذف می شود. در واقع، اینگونه است که توسعه پذیری پویا ArrayList پیاده سازی می شود . بیایید به پرکاربردترین روش‌های ArrayList نگاه کنیم : 1. add(<Elelement>) - یک عنصر را به انتهای آرایه (به آخرین سلول خالی) اضافه می‌کند و ابتدا بررسی می‌کند که آیا فضایی در این آرایه وجود دارد یا خیر. اگر وجود نداشته باشد، یک آرایه جدید ایجاد می شود که عناصر در آن کپی می شوند. پیچیدگی لگاریتمی این عملیات O(1) است. یک روش مشابه وجود دارد - add(<Index>,<Elelement>) . یک عنصر را نه به انتهای لیست (آرایه)، بلکه به یک سلول خاص با شاخصی که به عنوان آرگومان آمده است اضافه می کند. در این مورد، پیچیدگی لگاریتمی بسته به محل اضافه شدن آن متفاوت خواهد بود:

• اگر این تقریباً ابتدای لیست بود، پیچیدگی لگاریتمی نزدیک به O(N) خواهد بود، زیرا تمام عناصر واقع در سمت راست مورد جدید باید یک سلول به سمت راست منتقل شوند.
• اگر عنصر در وسط درج شود - O(N/2) زیرا فقط باید نیمی از عناصر لیست را یک سلول به سمت راست منتقل کنیم.

یعنی پیچیدگی لگاریتمی این روش بسته به محل درج عنصر از O(N) تا O(1) متغیر است. 2. set(<Index>,<Elelement>) - یک عنصر را در موقعیت مشخص شده در لیست می نویسد. اگر قبلاً عنصری در آن موقعیت وجود دارد، آن را بازنویسی کنید. پیچیدگی لگاریتمی این عملیات O(1) است، زیرا هیچ جابجایی وجود ندارد: فقط جستجو بر اساس شاخص در آرایه که همانطور که به یاد داریم پیچیدگی O(1) دارد و نوشتن عنصر. 3. remove(<index>) - حذف یک عنصر توسط شاخص آن در آرایه داخلی. هنگام حذف آیتمی که در انتهای لیست نیست، باید تمام موارد را به سمت راست آن یک سلول به چپ منتقل کنید تا شکاف باقی مانده پس از حذف آیتم بسته شود. بنابراین، پیچیدگی لگاریتمی مانند add(<Index>,<Elelement>) خواهد بود اگر عنصر در وسط باشد - O(N/2) - زیرا باید نیمی از عناصر را یک به چپ منتقل کنید. بر این اساس، اگر در ابتدا بود - O(N). خوب، اگر در پایان O(1) باشد، نیازی به جابجایی چیزی نیست. برای کسانی که می‌خواهند عمیق‌تر به این موضوع بپردازند، این پیوند را به مقاله‌ای با تحلیل کلاس ArrayList می‌گذارم .

87. ساختار داخلی LinkedList چیست؟

اگر ArrayList حاوی عناصری در یک آرایه داخلی باشد، LinkedList به شکل یک لیست دارای پیوند دوگانه است. این بدان معنی است که هر عنصر حاوی یک پیوند به عنصر قبلی ( قبلی ) و عنصر بعدی ( بعدی ) است. عنصر اول پیوندی به عنصر قبلی ندارد (اولین عنصر است) اما سرفصل لیست محسوب می شود و LinkedList مستقیماً به آن پیوند دارد. عنصر آخر، در واقع، عنصر بعدی ندارد، آن دم لیست است، و بنابراین یک پیوند مستقیم به آن در خود LinkedList وجود دارد . بنابراین، پیچیدگی لگاریتمی دسترسی به سر یا دم یک لیست O(1) است. در ArrayList، زمانی که لیست بزرگ شد، آرایه داخلی افزایش یافت، اما در اینجا همه چیز ساده تر اتفاق می افتد - هنگام اضافه کردن یک عنصر، چند پیوند به سادگی تغییر می کنند. بیایید به برخی از پرکاربردترین متدهای LinkedlList نگاهی بیندازیم : 1. add(<Elelement>) - افزودن در انتهای لیست، یعنی. بعد از آخرین عنصر (5) پیوندی به عنصر جدید به عنوان بعدی اضافه می شود . عنصر جدید مانند عنصر قبلی پیوندی به آخرین (5) خواهد داشت . پیچیدگی لگاریتمی چنین عملیاتی O(1) خواهد بود، زیرا فقط یک پیوند به آخرین عنصر مورد نیاز است، و همانطور که به یاد دارید، دم یک پیوند مستقیم از LinkedList دارد و پیچیدگی لگاریتمی دسترسی به آن حداقل است. 2. add(<Index>,<Elelement>) - اضافه کردن یک عنصر توسط نمایه. هنگام اضافه کردن یک عنصر، به عنوان مثال، به وسط یک لیست، عناصر از سر و دم (در هر دو طرف) ابتدا تکرار می شوند تا مکان مورد نظر پیدا شود. اگر بخواهیم عنصری را بین سوم و چهارم وارد کنیم (در شکل بالا)، در هنگام جستجوی مکان مناسب، پیوند بعدی عنصر سوم قبلاً به عنصر جدید اشاره می کند. برای لینک جدید، لینک قبلی به لینک سوم اشاره می کند. بر این اساس، پیوند عنصر چهارم - قبلی - قبلاً به عنصر جدید و پیوند بعدی عنصر جدید به عنصر چهارم اشاره خواهد کرد: پیچیدگی لگاریتمی این روش به شاخص داده شده به عنصر جدید بستگی دارد:

• اگر به سر یا دم نزدیک باشد، به O(1) نزدیک می شود، زیرا عملاً نیازی به تکرار بر روی عناصر نخواهد بود.
• اگر نزدیک به وسط باشد، O(N/2) - عناصر سر و دم به طور همزمان مرتب می شوند تا عنصر مورد نیاز پیدا شود.

3. set(<Index>,<Elelement>) - یک عنصر را در موقعیت مشخص شده در لیست می نویسد. پیچیدگی لگاریتمی این عملیات از O(1) تا O(N/2) متغیر است، باز هم بسته به نزدیک بودن عنصر به سر، دم یا وسط. 4. remove(<index>) - یک عنصر را از لیست حذف می کند، در اصل عنصری را که قبل از حذف ( قبلی ) قرار می گیرد به عنصری که بعد از حذف شده ( بعدی ) می آید ارجاع می دهد. و بالعکس: به طوری که عنصری که بعد از حذف شده می آید به عنصری که قبل از حذف می آید اشاره دارد: نتیجه فرآیندی معکوس با جمع کردن با شاخص است ( add(<Index>,<Elelement>) ). برای کسانی که مایل به کسب اطلاعات بیشتر در مورد ساختار داخلی LinkedList هستند، خواندن این مقاله را توصیه می کنم .

88. ساختار داخلی HashMap چیست؟

شاید یکی از رایج ترین سوالات هنگام مصاحبه با یک توسعه دهنده جاوا باشد. HashMap v با جفت های کلید-مقدار کار می کند . چگونه آنها در داخل خود HashMapv ذخیره می شوند ؟ در داخل HashMap آرایه ای از گره ها وجود دارد:

Node<K,V>[] table

به طور پیش فرض، اندازه آرایه 16 است، و هر بار که با عناصر پر می شود، دو برابر می شود (وقتی به LOAD_FACTOR رسید - درصد مشخصی از پر بودن، به طور پیش فرض 0.75 است ). هر گره یک هش از کلید، یک کلید، یک مقدار و یک پیوند به عنصر بعدی را ذخیره می کند: در واقع، "پیوند به عنصر بعدی" به این معنی است که ما با یک لیست پیوندی منفرد روبرو هستیم، جایی که هر عنصر حاوی یک پیوند به عنصر بعدی است. بعدی. یعنی HashMap داده‌ها را در آرایه‌ای از لیست‌های پیوندی منفرد ذخیره می‌کند. اما من فوراً متذکر می شوم: وقتی یک سلول از آرایه جدول پیوندی به یک لیست پیوندی مشابه متشکل از بیش از یک عنصر دارد، این خوب نیست. به این پدیده برخورد می گویند . اما اول از همه. بیایید ببینیم چگونه یک جفت جدید با استفاده از روش put ذخیره می شود . ابتدا hachCode() کلید گرفته می شود. بنابراین، برای اینکه هشمپ به درستی کار کند ، باید کلاس هایی را انتخاب کنید که در آنها این روش به عنوان کلید لغو شده است. این کد هش سپس در روش داخلی - hash() - برای تعیین تعداد در اندازه آرایه جدول استفاده می شود . سپس با استفاده از عدد دریافتی، به سلول خاصی از آرایه جدول دسترسی پیدا می کند . در اینجا دو مورد داریم:

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

هنگام جستجوی یک عنصر با کلید ( روش get(<key>) )، hashCode کلید محاسبه می شود، سپس مقدار آن در آرایه با استفاده از hash() و با استفاده از عدد حاصل، سلول آرایه جدول پیدا می شود. ، که در آن جستجو از قبل با شمارش گره ها و مقایسه کلید گره مورد نظر با کلید فعلی انجام شده است. عملیات نقشه در یک موقعیت ایده آل دارای پیچیدگی الگوریتمی O(1) است، زیرا آنها به یک آرایه دسترسی دارند، و همانطور که به یاد دارید، صرف نظر از تعداد عناصر، عملیات روی یک آرایه دارای پیچیدگی O(1) است. اما این ایده آل است. هنگامی که سلول آرایه مورد استفاده خالی نباشد (2) و از قبل تعدادی گره در آنجا وجود داشته باشد، پیچیدگی الگوریتمی به O(N) خطی تبدیل می شود، زیرا اکنون لازم است قبل از یافتن مکان مناسب، روی عناصر تکرار شود. من نمی‌توانم این را ذکر نکنم: از جاوا 8 شروع می‌شود، اگر یک گره لیست پیوندی منفرد بیش از 8 عنصر داشته باشد (برخورد)، به یک درخت باینری تبدیل می‌شود. در این مورد، پیچیدگی الگوریتمی دیگر O(N) نخواهد بود، بلکه O(log(N)) خواهد بود - این موضوع دیگری است، اینطور نیست؟ HashMap یک موضوع بزرگ است و مردم دوست دارند در مصاحبه ها درباره آن سوال بپرسند. بنابراین، من به شما توصیه می کنم که آن را با جزئیات درک کنید (به طوری که از دندان های شما جهش کند). من شخصا مصاحبه ای بدون سوالات HashMap نداشته ام . در این مقاله می‌توانید به بررسی عمیق HashMap بیابید . همین امروز ادامه دارد...