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

سلام! چند ساعت طول می کشد تا در چیزی استاد شوید؟ من اغلب چنین چیزی شنیده ام: "برای اینکه در هر کاری استاد شوید، باید 10000 ساعت وقت بگذارید." یک عدد ترسناک، اینطور نیست؟ با این حال، نمی دانم که آیا این حقیقت دارد؟ و من دائماً در تلاش هستم تا بفهمم چند ساعت برای تسلط بر هنر برنامه نویسی سرمایه گذاری کرده ام. و وقتی من از آن 10000 ساعت عزیز عبور کنم و استاد شوم، آیا این تفاوت را احساس خواهم کرد؟ یا من مدتها پیش بدون اینکه متوجه باشم از آنها عبور کرده ام؟ به هر طریقی، برای تبدیل شدن به یک برنامه نویس، نیازی به سرمایه گذاری زمان زیادی ندارید. نکته اصلی استفاده عاقلانه از آن است. هدف اصلی شما قبولی در مصاحبه است. و در مصاحبه برای تازه واردان، اولین چیزی که آنها می پرسند تئوری است، بنابراین شما باید در آن قوی باشید. در واقع، هنگام آماده شدن برای مصاحبه، وظیفه شما این است که تمام شکاف های خود را در نظریه پایه یک توسعه دهنده جاوا کشف کنید و آنها را با دانش پوشش دهید. و امروز در این مورد به شما کمک خواهم کرد، زیرا من اینجا هستم تا به تجزیه و تحلیل محبوب ترین سؤالات ادامه دهم. پس بیایید ادامه دهیم!

89. ArrayList چه تفاوتی با LinkedList دارد؟

این یکی از پرطرفدارترین سوالات به همراه سوال در مورد ساختار داخلی HashMap است . حتی یک مصاحبه بدون آن کامل نیست، و بنابراین پاسخ به آن باید «از دندان شما بیرون بزند». علاوه بر آشکار - نام های مختلف - آنها در ساختار داخلی متفاوت هستند. قبلا ساختار داخلی هر دو ArrayList و LinkedList را بررسی کردیم ، بنابراین به جزئیات پیاده سازی آنها نمی پردازم. فقط به شما یادآوری می کنم که ArrayList بر اساس یک آرایه داخلی پیاده سازی شده است که در صورت نیاز طبق فرمول افزایش می یابد:

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

در همان زمان، LinkedList بر اساس یک لیست داخلی با پیوند دوگانه پیاده سازی می شود، یعنی هر عنصر دارای پیوندی به قبلی و بعدی است، به استثنای مقادیری که ابتدا / انتهای لیست هستند. مردم دوست دارند این سوال را در قالب بپرسند: "کدامیک بهتر است - ArrayList یا LinkedList ؟"، به امید اینکه شما را جلب کنند. به هر حال، اگر به یکی از آنها به عنوان پاسخ اشاره کنید، پاسخ اشتباه خواهد بود. در عوض، باید مشخص کنید که در مورد چه وضعیت خاصی صحبت می کنید - دسترسی به فهرست یا درج در وسط یک لیست. بسته به پاسخ، می توانید انتخاب خود را توضیح دهید. من قبلا توضیح داده ام که ArrayList و LinkedList در یک موقعیت یا موقعیت دیگر چگونه کار می کنند. بیایید این را با قرار دادن آنها در همان صفحه برای مقایسه خلاصه کنیم: افزودن یک عنصر (افزودن)

1. Добавление нового element без указания индекса How местоположения будет происходить автоматически в конец обоих списков. В LinkedList новый элемент станет новым хвостом (происходит только перезаписывание пары ссылок — алгоритмическая сложность O(1)).

   В ArrayList будет добавлен новый элемент в последнюю пустую ячейку массива — O(1).

2. Добавление element по индексу How правило подразумевает вставку примерно в середину списка. В LinkedList сперва будет вестись поиск нужного места с помощью перебора элементов с “хвоста” и “головы” — O(n/2), а после — вставка значения путем переопределения ссылок элементов, между которыми вставляется новый — O(1). Суммарная алгоритмическая сложность данного действия будет O(n/2).

   ArrayList в данной ситуации по индексу находит элемент — O(1), и все элементы справа (включая элемент, который уже хранится по данному индексу) двигаются на одну единицу вправо (при этом возможно понадобится создание нового списка и копирование элементов в него) — O(n/2). Суммарная сложность — O(n/2).

3. Добавление element в начало списка в LinkedList будет ситуация схожая с добавлением в конец: новый элемент станет новой “головой” — O(1), в то же время когда ArrayList-у нужно будет двигать все элементы вправо — O(n).

خط پایین: در LinkedList، پیچیدگی الگوریتمی از O(1) تا O(n/2) متغیر است . یعنی هرچه درج به انتهای یا ابتدای لیست نزدیکتر باشد، سرعت آن بیشتر می شود. در همان زمان، برای ArrayList از O(1) تا O(n) متغیر است : هرچه درج به انتهای لیست نزدیک‌تر باشد، سریع‌تر است. تنظیم یک عنصر (مجموعه) این عملیات یک عنصر را در موقعیت مشخص شده در لیست می نویسد و در صورت وجود، عنصر قبلی را بازنویسی می کند. در LinkedList، این عملیات مشابه افزودن خواهد بود، زیرا بزرگترین مشکل در اینجا یافتن عنصر است. بازنویسی یک عنصر با بازنویسی یک جفت پیوند انجام می شود، بنابراین در اینجا نیز پیچیدگی الگوریتمی بسته به فاصله موقعیت از انتهای یا ابتدای لیست از O(1) تا O(n/2) متغیر است. در آن زمان، سلول مورد نیاز در ArrayList برای این عملیات شاخص پیدا می شود و یک عنصر جدید در آن نوشته می شود. جستجوی فهرست، مانند این عملیات، دارای پیچیدگی الگوریتمی O(1) است . یک عنصر را بر اساس شاخص بگیرید (دریافت کنید) در LinkedList، گرفتن یک عنصر مطابق با همان اصل جستجوی سایر عملیات انجام می شود - بسته به فاصله از انتها یا ابتدا، یعنی. از O(1) تا O(n/2) . در ArrayList ، همانطور که قبلاً گفتم، یافتن یک عنصر در یک آرایه توسط شاخص دارای پیچیدگی O(1) است . حذف یک عنصر با نمایه (حذف) برای LinkedList ، اصل عملکرد آن نیز در اینجا کار می کند: ابتدا عنصر پیدا می شود و سپس پیوندها بازنویسی می شوند - همسایگان عنصر شروع به ارجاع به یکدیگر می کنند و ارجاعات به این عنصر را از دست می دهند. که متعاقباً توسط زباله جمع کن حذف خواهد شد. یعنی پیچیدگی الگوریتمی همچنان یکسان است - از O(1) تا O(n/2) . برای ArrayList ، این عملیات بیشتر شبیه عملیات افزودن یک عنصر جدید (افزودن) است. ابتدا عنصر مورد نیاز پیدا می شود - O(1) ، سپس حذف می شود و تمام عناصری که در سمت راست آن قرار داشتند یک واحد به سمت چپ منتقل می شوند تا شکاف حاصل بسته شود. عملیات حذف همان پیچیدگی الگوریتمی عملیات افزودن را خواهد داشت - از O(1) تا O(n) . هرچه حذف به انتهای لیست نزدیکتر باشد، پیچیدگی الگوریتمی آن کمتر است. در واقع، اینها همه عملیات اصلی بودند. یادآوری می کنم: هنگام مقایسه این دو لیست، باید مشخص کنید که در مورد چه وضعیت خاصی صحبت می کنیم و سپس می توانید بدون ابهام به سؤال مطرح شده پاسخ دهید.

90. ArrayList چه تفاوتی با HashSet دارد؟

اگر بتوان ArrayList و LinkedList را از نظر عملیات مقایسه کرد - که بهتر است - مقایسه ArrayList با HashSet چندان آسان نیست ، زیرا اینها مجموعه های کاملاً متفاوتی هستند. می توانید یک غذای شیرین را با دیگری مقایسه کنید، اما با یک غذای گوشتی کار می کند - آنها بسیار متفاوت هستند. با این حال، سعی می کنم تفاوت هایی را بین آنها بیان کنم:

• ArrayList رابط List را پیاده سازی می کند ، در حالی که HashSet رابط Set را پیاده سازی می کند .

• در ArrayList، دسترسی با شاخص عنصر امکان پذیر است: عملیات get دارای پیچیدگی الگوریتمی O(1) است و در HashSet عنصر مورد نیاز را فقط می توان با نیروی brute به دست آورد و این از O(1) تا O(n) است. ;

• ArrayList اجازه می دهد تا عناصر تکراری. در HashSet، همه عناصر منحصر به فرد هستند: افزودن یک عنصر به HashSet که آنالوگ آن از قبل در مجموعه موجود است کار نخواهد کرد (تکراری ها با استفاده از کد هش بررسی می شوند، از این رو نام این مجموعه است).

• ArrayList با استفاده از یک آرایه داخلی و HashSet با استفاده از HashMap داخلی پیاده سازی می شود .

• یک ArrayList ترتیب درج عناصر را حفظ می کند، در حالی که HashSet یک مجموعه نامرتب است و ترتیب عناصر را حفظ نمی کند.

• ArrayList اجازه می دهد تا هر تعداد از مقادیر خالی (null) را فراهم کند، فقط یک مقدار null را می توان در HashSet درج کرد (در نهایت، منحصر به فرد بودن عناصر).

91. چرا چنین تنوعی در پیاده سازی آرایه های پویا در جاوا وجود دارد؟

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

92. چرا چنین تنوعی از پیاده سازی های ذخیره سازی کلید-مقدار در جاوا وجود دارد؟

در اینجا وضعیت مانند اجرای آرایه پویا است. بهترین کسی وجود ندارد: هر کدام نقاط قوت و ضعفی دارند. و البته ما باید از نقاط قوت خود نهایت استفاده را ببریم. مثال: بسته همزمان، که شامل بسیاری از فناوری های چند رشته ای است، مجموعه های همزمان خود را دارد . همان ConcurrentHashMap در ایمنی کار چند رشته ای با داده ها در مقایسه با HashMap معمولی مزیت دارد ، اما در یک محیط غیر چند رشته ای سرعت آن را از دست می دهد. خب، پیاده‌سازی‌هایی که در هیچ شرایطی قوی‌ترین نیستند، به تدریج استفاده از آنها متوقف می‌شود. مثال: Hashtable در ابتدا در نظر گرفته شده بود تا یک HashMap ایمن رشته ای باشد ، اما ConcurrentHashMap از آن در یک محیط چند رشته ای بهتر عمل کرد و Hashtable در نهایت فراموش شد و دیگر استفاده نشد.

93. چگونه مجموعه ای از عناصر را مرتب کنیم؟

اولین چیزی که باید گفت این است که کلاس عنصر مجموعه باید رابط Comparable و متد compareTo آن را پیاده سازی کند . یا به کلاسی نیاز دارید که Comaprator را با متد مقایسه کننده خود پیاده سازی کند . در این پست می توانید اطلاعات بیشتری در مورد آنها بخوانید . هر دو روش مشخص می کنند که چگونه اشیاء از یک نوع معین باید مقایسه شوند. هنگام مرتب‌سازی، این امر بسیار مهم است، زیرا باید این اصل را درک کنید که با آن عناصر می‌توانند مقایسه شوند. راه اصلی برای انجام این کار پیاده سازی Comparable است که مستقیماً در کلاسی که می خواهید مرتب کنید پیاده سازی شده است. در عین حال، استفاده از Comparator کمتر رایج است. فرض کنید از کلاسی از کتابخانه ای استفاده می کنید که پیاده سازی Comparable ندارد ، اما باید به نحوی آن را مرتب کنید. بدون اینکه بتوانید کد این کلاس را تغییر دهید (به جز با گسترش آن)، می توانید یک پیاده سازی از Comparator بنویسید که در آن مشخص کنید که بر اساس چه اصل می خواهید اشیاء این کلاس را با هم مقایسه کنید. و یک مثال دیگر. فرض کنید برای مرتب‌سازی اشیاء از یک نوع به اصول مختلفی نیاز دارید، بنابراین چندین مقایسه می‌نویسید که در موقعیت‌های مختلف استفاده می‌کنید. به عنوان یک قاعده، بسیاری از کلاس‌های خارج از جعبه قبلاً رابط Comparable را پیاده‌سازی می‌کنند - همان رشته . در واقع، هنگام استفاده از آنها، لازم نیست نگران نحوه مقایسه آنها باشید. شما فقط آنها را بگیرید و از آنها استفاده کنید. اولین و واضح ترین راه استفاده از مجموعه ای از نوع TreeSet یا TreeMap است که عناصر را به ترتیب مرتب شده با توجه به مقایسه کننده کلاس عنصر ذخیره می کند. به یاد داشته باشید که TreeMap کلیدها را مرتب می کند، اما مقادیر را نه. اگر از پیاده سازی Comparator به جای Comparable استفاده می کنید ، باید شی آن را به سازنده مجموعه ارسال کنید.

TreeSet treeSet = new TreeSet(customComparator);

اما اگر نوع متفاوتی از مجموعه داشته باشید چه؟ چگونه آن را مرتب کنیم؟ در این مورد، روش دوم کلاس ابزار Collections مناسب است - متد sort() . استاتیک است، بنابراین تنها چیزی که نیاز دارید نام کلاس و روشی است که لیست مورد نیاز به آن ارسال می شود. مثلا:

Collections.sort(someList);

اگر از Comparable استفاده نمی کنید ، بلکه از اجرای Comparator استفاده می کنید، باید آن را به عنوان پارامتر دوم ارسال کنید:

Collections.sort(someList, customComparator);

در نتیجه، ترتیب داخلی عناصر لیست ارسال شده تغییر می کند: طبق مقایسه کننده عنصر مرتب می شود. توجه می کنم که لیست عناصر منتقل شده باید قابل تغییر باشد، یعنی. قابل تغییر است، در غیر این صورت روش کار نخواهد کرد و UnsupportedOperationException پرتاب می شود . به عنوان راه سوم ، می‌توانید از عملیات مرتب‌سازی جریانی استفاده کنید که در صورت استفاده از اجرای Comparable، عناصر مجموعه را مرتب می‌کند :

someList = someList.stream().sorted().collect(Collectors.toList());

اگر مقایسه کننده :

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

در این مقاله می توانید اطلاعات بیشتری در مورد استریم بخوانید . روش چهارم اجرای دستی مرتب‌سازی است، مانند مرتب‌سازی حبابی یا مرتب‌سازی ادغام .

ClassObject. برابر و هش کد

94. توضیح مختصری از شی کلاس در جاوا ارائه دهید

در قسمت دوم تجزیه و تحلیل، قبلاً در مورد متدهای کلاس Object صحبت کردیم و یادآوری می کنم که کلاس Object مولد همه کلاس ها در جاوا است. دارای 11 متد است که بر این اساس به همه کلاس ها به ارث می رسد. اطلاعات مربوط به هر 11 روش را می توان در قسمت دوم بحث یافت .

95. Equals و HashCode در جاوا چه کاربردی دارند؟

hashCode() متدی از کلاس Object است که توسط همه کلاس ها به ارث می رسد. وظیفه آن تولید تعدادی است که نشان دهنده یک شی خاص است. نمونه ای از استفاده از این روش، استفاده از آن در HashMap بر روی یک شی کلیدی برای تعیین بیشتر هش کد محلی است که سلول آرایه داخلی (سطل) را مشخص می کند که جفت در آن ذخیره می شود. ما در بخش 9 تجزیه و تحلیل به طور مفصل در مورد کار HashMap صحبت کردیم ، بنابراین زیاد روی این موضوع تمرکز نمی کنیم. همچنین قاعدتاً از این روش در متد () quals به عنوان یکی از ابزارهای اصلی آن برای تعیین هویت اشیا استفاده می شود. ()quals متدی از کلاس Object است که وظیفه آن مقایسه اشیاء و تعیین مساوی بودن یا نبودن آنهاست. این روش در همه جا که نیاز به مقایسه اشیاء داریم استفاده می شود، زیرا مقایسه معمول با استفاده از == برای اشیا مناسب نیست، زیرا فقط پیوندها را با آنها مقایسه می کند.

96. در مورد قرارداد بین Equals و HashCode در جاوا بگویید؟

اولین چیزی که می گویم این است که برای اینکه متدهای ()quals() و hashCode() به درستی کار کنند ، باید به درستی override شوند. پس از این، آنها باید قوانین را دنبال کنند:

• اشیاء یکسانی که مقایسه آنها از طریق برابر با مقدار true، باید دارای کدهای هش یکسان باشند.
• اشیا با کدهای هش یکسان ممکن است همیشه برابر نباشند.

در این مرحله تا قسمت بعدی تحلیل مکث خواهیم کرد!