به طور خلاصه در مورد چیز اصلی - Java Collections Framework

آغاز راه

امروز می خواهم در مورد موضوع جالبی مانند " چارچوب مجموعه های جاوا " یا به زبان ساده درباره مجموعه ها صحبت کنم. بیشتر کار کد پردازش داده ها به یک شکل یا شکل دیگر است. دریافت لیستی از کاربران، دریافت لیستی از آدرس ها و غیره. به نوعی آنها را مرتب کنید، جستجو کنید، مقایسه کنید. به همین دلیل است که دانش مجموعه ها به عنوان یک مهارت اصلی در نظر گرفته می شود. به همین دلیل می خواهم در مورد آن صحبت کنم. علاوه بر این، یکی از رایج ترین سوالات در مصاحبه های توسعه دهندگان جاوا مجموعه ها هستند. به عنوان مثال، "یک سلسله مراتب از مجموعه ها را ترسیم کنید." کامپایلر آنلاین به ما در این راه کمک می کند. به عنوان مثال، می توانید از " Tutorialspoint Online Java Compiler " یا Repl.it استفاده کنید. مسیر آشنایی با هر ساختار داده با متغیرهای معمولی (Variables) آغاز می شود. در وب‌سایت اوراکل، موضوعات مختلف به‌عنوان «مسیرها» یا Trails نمایش داده می‌شوند. بنابراین، مسیر آشنایی با جاوا به نام « مسیر: یادگیری زبان جاوا: فهرست مطالب ». و مبانی زبان (یعنی مبانی زبان) با متغیرها شروع می شود. بنابراین، بیایید یک کد ساده بنویسیم:

public static void main(String[] args) {
	String user = "Max";
	System.out.println("Hello, " + user);
}

در همه چیز خوب است، با این تفاوت که می فهمیم این کد فقط برای یک متغیر خوب و زیبا است. اگر چندین مورد وجود داشته باشد چه باید کرد؟ آرایه ها برای ذخیره داده های یک نوع اختراع شدند. در همان Trail از Oracle یک بخش جداگانه به آرایه ها اختصاص داده شده است. این بخش " آرایه ها " نام دارد . کار با آرایه ها نیز بسیار ساده است:

import java.util.Arrays;
class Main {
  public static void main(String[] args) {
    String[] users = new String[2];
    users[0] = "Max";
    users[1] = "John";
    System.out.println("Hello, " + Arrays.toString(users));
  }
}

آرایه ها مشکل ذخیره چندین مقدار را در یک مکان حل می کنند. اما محدودیتی را تحمیل می کند: اندازه آرایه ثابت است. اگر مانند مثال گفتیم که اندازه = 2 است، آنگاه برابر با دو است. همین. اگر یک آرایه بزرگتر می خواهیم، ​​باید یک نمونه جدید ایجاد کنیم. همچنین، یافتن یک عنصر نیز برای یک آرایه کار دشواری است. یک روش وجود دارد Arrays.binarySearch، اما این جستجو فقط روی یک آرایه مرتب شده کار می کند (برای یک آرایه مرتب نشده، نتیجه تعریف نشده یا به سادگی غیرقابل پیش بینی است). یعنی جستجو ما را موظف می کند که هر بار مرتب سازی کنیم. حذف نیز فقط مقدار را پاک می کند. بنابراین، ما هنوز نمی دانیم واقعاً چه مقدار داده در آرایه است، فقط می دانیم که چند سلول در آرایه وجود دارد. برای تازه کردن دانش خود در مورد آرایه ها:

• " JavaRush: آرایه ها در جاوا "
• " آموزش جاوا: آرایه ها "

و در نتیجه توسعه زبان جاوا، چارچوب مجموعه های جاوا در JDK 1.2 ظاهر شد که امروز در مورد آن صحبت خواهیم کرد.

مجموعه

هزینه یابی را از همان ابتدا شروع کنید. چرا مجموعه ها؟ این اصطلاح خود از چیزهایی مانند "تئوری نوع" و "انواع داده های انتزاعی" می آید. اما اگر به هیچ موضوع مهمی نگاه نکنید، وقتی چندین چیز داریم، می‌توانیم آنها را «مجموعه چیزها» بنامیم. کسانی که اقلام را جمع آوری می کنند. به طور کلی کلمه collect خود از لات می آید. مجموعه "جمع آوری، جمع آوری." یعنی مجموعه مجموعه ای از چیزی است، ظرفی برای برخی عناصر. بنابراین ما مجموعه ای از عناصر را داریم. کاری که ممکن است بخواهیم با آن انجام دهیم: همانطور که می بینید، ما ممکن است چیزهای کاملا منطقی بخواهیم. همچنین می‌دانیم که ممکن است بخواهیم کاری را با چندین مجموعه انجام دهیم: بر این اساس، توسعه دهندگان جاوا رابط java.util.Collection را برای توصیف این رفتار کلی برای همه مجموعه ها نوشتند . رابط Collection جایی است که همه مجموعه ها از آن منشا می گیرند. مجموعه یک ایده است، این ایده ای است از اینکه همه مجموعه ها چگونه باید رفتار کنند. بنابراین، اصطلاح "مجموعه" به عنوان یک رابط بیان می شود. به طور طبیعی، یک رابط نیاز به پیاده سازی دارد. این رابط java.util.Collectionدارای یک کلاس انتزاعی است AbstractCollection، یعنی مقداری «مجموعه انتزاعی» که نمایانگر اسکلت پیاده‌سازی‌های دیگر است (همانطور که در JavaDoc بالای کلاس نوشته شده است java.util.AbstractCollection). در مورد مجموعه ها صحبت می کنیم، بیایید به عقب برگردیم و به یاد داشته باشیم که می خواهیم روی آنها تکرار کنیم. این بدان معنی است که ما می خواهیم عناصر را یک به یک تکرار کنیم. این یک مفهوم بسیار مهم است. بنابراین، رابط Collectionاز ارث برده شده است Iterable. این بسیار مهم است زیرا ... اولاً، هر چیز Iterable باید بتواند یک Iterator را بر اساس محتویاتش برگرداند. و در مرحله دوم، هر چیزی که Iterable را می توان در حلقه ها استفاده کرد for-each-loop. و با کمک یک تکرار کننده است AbstractCollectionکه روش هایی مانند contains, toArray, پیاده سازی می شود remove. و مسیر درک مجموعه ها با یکی از رایج ترین ساختارهای داده آغاز می شود - یک لیست، به عنوان مثال. List.

لیست ها

بنابراین، لیست ها جایگاه مهمی در سلسله مراتب مجموعه ها دارند: همانطور که می بینیم، لیست ها رابط java.util.List را پیاده سازی می کنند . لیست ها بیان می کنند که ما مجموعه ای از عناصر داریم که به ترتیب یکی پس از دیگری مرتب شده اند. هر عنصر یک شاخص دارد (مانند یک آرایه). به طور معمول، یک لیست به شما امکان می دهد عناصری با همان مقدار داشته باشید. همانطور که در بالا گفتیم، Listدر مورد شاخص عنصر می داند. این به شما این امکان را می دهد که ( get) یک عنصر را به فهرست دریافت کنید یا یک مقدار برای یک شاخص خاص ( set) تعیین کنید. متدهای جمع آوری add، به شما امکان می دهد شاخصی را مشخص کنید که از آن آنها را اجرا کنید addAll. removeعلاوه بر این، y Listنسخه مخصوص به خود را از یک تکرار کننده به نام دارد ListIterator. این تکرار کننده از شاخص عنصر اطلاع دارد، بنابراین می تواند نه تنها به جلو، بلکه به عقب نیز تکرار کند. حتی می توان آن را از یک مکان خاص در مجموعه ایجاد کرد. در بین تمام پیاده سازی ها، دو مورد از رایج ترین موارد استفاده می شود: ArrayListو LinkedList. ابتدا یک لیست ( ) بر اساس یک آرایه ( ) ArrayListاست . این به شما امکان می دهد به "دسترسی تصادفی" به عناصر برسید. دسترسی تصادفی توانایی بازیابی فوری یک عنصر با شاخص است، به جای تکرار در تمام عناصر تا زمانی که عنصری را با شاخص مورد نظر پیدا کنیم. این آرایه به عنوان مبنایی است که امکان دستیابی به این امر را فراهم می کند. برعکس، این یک لیست پیوندی است. هر ورودی در یک لیست پیوندی به شکل نمایش داده می شود که خود داده ها و همچنین پیوندی به بعدی (بعدی) و قبلی (قبلی) را ذخیره می کند . بنابراین "دسترسی متوالی " را پیاده سازی می کند . واضح است که برای یافتن عنصر پنجم باید از عنصر اول به آخرین عنصر برویم، زیرا ما دسترسی مستقیم به عنصر پنجم نداریم. ما فقط می توانیم از عنصر 4 به آن دسترسی داشته باشیم. تفاوت در مفهوم آنها در زیر آورده شده است: ListArrayLinkedListEntryEntryLinkedList در کار، همانطور که متوجه شدید، تفاوت نیز وجود دارد. به عنوان مثال، اضافه کردن عناصر. عناصر LinkedListبه سادگی مانند حلقه هایی در یک زنجیره به هم متصل می شوند. اما ArrayListعناصر را در یک آرایه ذخیره می کند. و یک آرایه، همانطور که می دانیم، نمی تواند اندازه خود را تغییر دهد. اونوقت چطوری کار میکنه ArrayList؟ و خیلی ساده کار می کند. وقتی فضای موجود در آرایه تمام شود، 1.5 برابر افزایش می یابد. در اینجا کد بزرگنمایی وجود دارد: int newCapacity = oldCapacity + (oldCapacity >> 1); تفاوت دیگر در عملکرد هر افست عناصر است. به عنوان مثال، هنگام افزودن یا حذف عناصر به وسط. برای حذف از LinkedListیک عنصر، به سادگی ارجاعات به این عنصر را حذف کنید. در مورد , ArrayListما مجبوریم هر بار با استفاده از System.arraycopy. بنابراین، هر چه عناصر بیشتر باشد، اقدامات بیشتری باید انجام شود. توضیحات بیشتر را می توان در این مقالات یافت:

• " ساختارهای داده در تصاویر. ArrayList "
• " ساختارهای داده در تصاویر. LinkedList "
• " زیر سرپوش LinkedList چیست؟ "

با بررسی ArrayList، نمی‌توان «سلف» آن، کلاس java.util.Vector را به خاطر آورد . این تفاوت Vectorدر ArrayListاین است که روش های کار با مجموعه (افزودن، حذف و غیره) همگام هستند. یعنی اگر یک رشته ( Thread) عناصری را اضافه کند، رشته های دیگر منتظر می مانند تا اولین رشته کار خود را تمام کند. از آنجایی که ایمنی رشته اغلب مورد نیاز نیست، توصیه می شود در چنین مواردی از کلاس استفاده کنید ArrayList، همانطور که به صراحت در JavaDoc برای کلاس ذکر شده است Vector. علاوه بر این، Vectorاندازه آن را نه 1.5 برابر، ArrayListبلکه 2 برابر افزایش می دهد. در غیر این صورت، رفتار یکسان است - Vectorذخیره عناصر در قالب یک آرایه پنهان است و افزودن/حذف عناصر همان عواقبی را دارد که در ArrayList. در واقع Vectorما این را به دلیلی به یاد آوردیم. اگر به Javadoc نگاه کنیم، در "زیرکلاس های شناخته شده مستقیم" ساختاری مانند java.util.Stack را خواهیم دید . پشته یک ساختار جالب است که یک last-in-first-outساختار LIFO (آخرین ورود، اولین خروج) است. پشته ترجمه شده از انگلیسی یک پشته است (مثلاً یک پشته کتاب). پشته روش های اضافی را پیاده سازی می کند: peek(نگاه، نگاه)، pop(فشار)، push(فشار). این روش peekبه صورت نگاه ترجمه می‌شود (برای مثال، نگاه کردن به داخل کیف به صورت « نگاه به داخل کیف » و « نگاه کردن از سوراخ کلید» به « نگاه کردن از سوراخ کلید » ترجمه می‌شود). این روش به شما امکان می دهد به "بالای" پشته نگاه کنید، یعنی. آخرین عنصر را بدون حذف (یعنی بدون حذف) از پشته دریافت کنید. متد pushیک عنصر جدید را به پشته فشار می دهد (افزوده) و آن را برمی گرداند و متد عنصر popحذف شده را فشار می دهد (حذف می کند) و برمی گرداند. در هر سه حالت (یعنی پیک، پاپ و فشار)، ما فقط با آخرین عنصر (یعنی "بالای پشته") کار می کنیم. این ویژگی اصلی ساختار پشته است. به هر حال، یک کار جالب برای درک پشته ها وجود دارد، که در کتاب "مصاحبه برنامه نویسی حرفه ای" توضیح داده شده است. یک کار جالب وجود دارد که در آن با استفاده از ساختار "پشته" (LIFO) باید "صف" را پیاده سازی کنید. ساختار (FIFO). می بایست شبیه به این باشه: تجزیه و تحلیل این کار را می توان در اینجا یافت: " اجرای یک صف با استفاده از پشته ها - صف ADT ("پیاده سازی صف با استفاده از پشته ها" در LeetCode) ". بنابراین ما به آرامی به یک ساختار داده جدید - یک صف می رویم.

صف

صف ساختاری است که از زندگی برای ما آشناست. صف مغازه ها، پزشکان. هر کسی که اولین بار آمد (اولین ورود) اولین نفری است که صف را ترک می کند (اولین خروج). در جاوا، یک صف با رابط java.util.Queue نشان داده می شود . با توجه به Javadoc صف، صف متدهای زیر را اضافه می کند: همانطور که می بینید، روش های سفارشی وجود دارد (عدم اجرای آنها مملو از استثنا است) و روش های درخواستی (عدم امکان اجرای آنها منجر به خطا نمی شود) وجود دارد. همچنین امکان دریافت عنصر بدون حذف آن وجود دارد (نگاه کردن یا عنصر). رابط صف همچنین یک جانشین مفید دارد - Deque . این به اصطلاح "صف دو طرفه" است. یعنی چنین صفی به شما این امکان را می دهد که هم از ابتدا و هم از انتها از این ساختار استفاده کنید. مستندات می گوید که "Deques را می توان به عنوان پشته های LIFO (Last-In-First-Out) نیز استفاده کرد. این رابط باید در ترجیح کلاس Stack قدیمی استفاده شود."، یعنی توصیه می شود از پیاده سازی های Deque به جای استفاده از پشته. Javadoc نشان می دهد که رابط Deque چه روش هایی را توصیف می کند: بیایید ببینیم چه پیاده سازی هایی وجود دارد. و ما یک واقعیت جالب را خواهیم دید - LinkedList وارد کمپ صف شده است) یعنی LinkedList هر دو Listو را پیاده سازی می کند Deque. اما برای مثال "فقط صف" نیز وجود دارد PriorityQueue. او اغلب به یاد نمی آید، اما بیهوده. اولا، شما نمی توانید از "اشیاء غیر قابل مقایسه" در این صف استفاده کنید. یا Comparator باید مشخص شود یا همه اشیا باید قابل مقایسه باشند. ثانیا، "این پیاده سازی زمان O(log(n)) را برای روش های صف دهی و صف بندی فراهم می کند". پیچیدگی لگاریتمی به دلایلی وجود دارد. PriorityQueue بر اساس پشته اجرا شد. Javadoc می گوید: "صف اولویت به عنوان یک پشته باینری متعادل نشان داده می شود". خود ذخیره سازی برای این یک آرایه معمولی است. که در صورت لزوم رشد می کند. هنگامی که پشته کوچک است، 2 برابر افزایش می یابد. و سپس 50 درصد. نظر از کد: "دو اندازه اگر کوچک است، در غیر این صورت 50٪ رشد کنید". صف اولویت و باینری هیپ یک موضوع جداگانه است. بنابراین برای اطلاعات بیشتر:

• مقاله فوق العاده در Habré: " ساختارهای داده. راهنمای غیر رسمی "
• توضیح واضح در مورد "هپ": " فاکسفورد: علوم کامپیوتر. ساختارهای داده: هیپ "
• مقاله ای از هابر درباره هیپ باینری: " ساختارهای داده: پشته باینری "
• " مقدمه ای بر هیپ های باینری (MaxHeaps) "

به عنوان پیاده سازی، java.util.Dequeمی توانید از کلاس java.util.ArrayDeque استفاده کنید . یعنی لیست ها را می توان با استفاده از یک لیست پیوندی و یک آرایه پیاده سازی کرد و همچنین صف ها را می توان با استفاده از یک آرایه یا با استفاده از یک لیست پیوندی پیاده سازی کرد. رابط‌های Queueو Dequeدارای فرزندانی هستند که «صف مسدود کردن» را نشان می‌دهند: BlockingQueueو BlockingDeque. در اینجا تغییر رابط در مقایسه با صف های معمولی است: بیایید به چند نمونه از مسدود کردن صف ها نگاه کنیم. اما آنها جالب هستند. به عنوان مثال، BlockingQueue توسط: PriorityBlockingQueue ، SynchronousQueue ، ArrayBlockingQueue، DelayQueue ، LinkedBlockingQueue اجرا می‌شود . اما BlockingDequeآنها همه چیز را از مجموعه چارچوب های استاندارد پیاده سازی می کنند LinkedBlockingDeque. هر صف موضوع یک بررسی جداگانه است. و در چارچوب این بررسی، سلسله مراتب کلاس را نه تنها با List، بلکه با Queue: همانطور که از نمودار می بینیم، رابط ها و کلاس های Java Collections Framework به شدت در هم تنیده شده اند. بیایید یک شاخه دیگر از سلسله مراتب را اضافه کنیم - Set.

تنظیم

Set- به عنوان "مجموعه" ترجمه شده است. تفاوت آن با یک صف و یک لیست Setدر انتزاع بیشتر در ذخیره سازی عناصر است. Set- مانند کیسه ای از اشیاء، جایی که معلوم نیست اشیا چگونه قرار دارند و به چه ترتیبی قرار گرفته اند. در جاوا، چنین مجموعه ای با رابط java.util.Set نشان داده می شود . همانطور که مستندات می گوید، Setاین یک "مجموعه ای است که حاوی عناصر تکراری نیست". جالب اینجاست که خود اینترفیس Setروش‌های جدیدی را به اینترفیس اضافه نمی‌کند Collection، بلکه فقط الزامات را روشن می‌کند (درباره مواردی که نباید حاوی موارد تکراری باشد). علاوه بر این، از توضیحات قبلی چنین استنباط می شود که نمی توانید به سادگی Setیک عنصر از آن دریافت کنید. Iterator برای به دست آوردن عناصر استفاده می شود. Setچندین رابط دیگر مرتبط با آن دارد. اولی است SortedSet. همانطور که از نام پیداست، SortedSetنشان می دهد که چنین مجموعه ای مرتب شده است و بنابراین عناصر رابط را پیاده سازی می کنند Comparableیا مشخص می شوند Comparator. علاوه بر این، SortedSetچندین روش جالب ارائه می دهد: firstعلاوه بر این، روش هایی (کوچکترین عنصر بر اساس مقدار) و last(بزرگترین عنصر بر اساس مقدار) وجود دارد . SortedSetیک وارث وجود دارد - NavigableSet. هدف از این رابط، توصیف روش‌های ناوبری مورد نیاز برای شناسایی دقیق‌تر عناصر مناسب است. یک چیز جالب این است NavigableSetکه به تکرار کننده معمولی (که از کوچکترین به بزرگترین می رود) یک تکرار کننده برای ترتیب معکوس اضافه می کند - descendingIterator. علاوه بر این، NavigableSetبه شما این امکان را می دهد که از روشی descendingSetبرای به دست آوردن نمایی از خود (View) استفاده کنید که در آن عناصر به ترتیب معکوس هستند. این Viewبه این دلیل نامیده می شود که از طریق عنصر حاصل می توانید عناصر عنصر اصلی را تغییر دهید Set. یعنی در اصل، نمایش داده های اصلی به شیوه ای متفاوت است و نه یک کپی از آن. جالب توجه است NavigableSet، مانند ، می تواند عناصر (حداقل) و (حداکثر) را Queueکنترل کند . یعنی این عنصر را می گیرد و از مجموعه حذف می کند. چه نوع پیاده سازی هایی وجود دارد؟ در مرحله اول، معروف ترین پیاده سازی مبتنی بر یک کد هش است - HashSet . یکی دیگر از پیاده سازی های به همان اندازه شناخته شده بر اساس درخت قرمز-سیاه است - TreeSet . بیایید نمودار خود را کامل کنیم: pollFirstpollLast در مجموعه ها، باید سلسله مراتب را مرتب کرد - زاهدان. که در نگاه اول کنار می ایستد - java.util.Map.

نقشه ها

نقشه ها ساختار داده ای هستند که داده ها توسط کلید در آن ذخیره می شوند. به عنوان مثال، کلید می تواند شناسه یا کد شهر باشد. و با این کلید است که داده ها جستجو خواهند شد. جالب است که کارت ها به صورت جداگانه نمایش داده می شوند. به گفته توسعه‌دهندگان (به « پرسش‌های متداول طراحی API مجموعه‌های جاوا » مراجعه کنید)، نگاشت کلید-مقدار یک مجموعه نیست. و نقشه ها را می توان سریعتر به عنوان مجموعه ای از کلیدها، مجموعه ای از مقادیر، مجموعه ای از جفت های کلید-مقدار در نظر گرفت. این حیوان بسیار جالبی است. کارت ها چه روش هایی را ارائه می دهند؟ بیایید به رابط Java API java.util.Map نگاه کنیم . زیرا از آنجایی که نقشه‌ها مجموعه نیستند (از مجموعه‌ها به ارث نمی‌برند)، حاوی یک علامت نیستند contains. و این منطقی است. یک نقشه از کلیدها و مقادیر تشکیل شده است. کدام یک از اینها را روش باید بررسی کند containsو چگونه گیج نشویم؟ بنابراین، رابط Mapدارای دو نسخه متفاوت است: containsKey(شامل یک کلید) و containsValue(شامل یک مقدار). استفاده از آن keySetبه شما امکان می دهد مجموعه ای از کلیدها را دریافت کنید (همان Set). و با استفاده از روش valuesمی توانیم مجموعه ای از مقادیر را در نقشه بدست آوریم. کلیدهای موجود در نقشه منحصربه‌فرد هستند که ساختار داده بر آن تأکید می‌کند Set. مقادیر را می توان تکرار کرد، که توسط ساختار داده مجموعه تاکید شده است. علاوه بر این، با استفاده از روش entrySetمی توانیم مجموعه ای از جفت های کلید-مقدار را به دست آوریم. شما می توانید در مورد پیاده سازی کارت ها در تجزیه و تحلیل های دقیق بیشتر بخوانید:

• " ساختارهای داده در تصاویر. HashMap "
• " ساختارهای داده در تصاویر. LinkedHashMap "
• " کارهای داخلی HashMap در جاوا (به روز رسانی برای جاوا 8) "

من همچنین می خواهم ببینم چه چیزی HashMapبسیار شبیه به HashSetو TreeMapبه TreeSet. آنها حتی رابط های مشابهی دارند: NavigableSetو NavigableMap، SortedSetو SortedMap. بنابراین نقشه نهایی ما به این صورت خواهد بود: ما می‌توانیم با این واقعیت جالب پایان دهیم که مجموعه Setبه صورت داخلی استفاده می‌کند Map، جایی که مقادیر اضافه شده کلید هستند و ارزش در همه جا یکسان است. این جالب است زیرا Mapمجموعه ای نیست و برمی گردد Setکه یک مجموعه است اما در واقع به عنوان پیاده سازی می شود Map. کمی سورئال، اما اینطور شد)

نتیجه

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

• " Oracle Trail: Collections "
• " آموزش IBM: مجموعه های جاوا "
• " Yuri Tkach: Advanced Java - Collections "
• مجموعه‌های جاوا : نیرو بیدار می‌شود اثر رائول گابریل اورما و ریچارد واربرتون
• " تیمور باتیرشینوف: 22 - مبانی جاوا. مجموعه ها (و ویدیوهای زیر از لیست پخش) "
• " پنج نکته ای که درباره... Java Collections API " نمی دانستید

#ویاچسلاو