آموزش جاوا - قسمت هشتم

1395/1/12 محمد چنگانی 4600

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

اما بریم سراغ تعریف ساختمان داده،

سازمان‌دادنِ داده‌ها به یک طریق خاص و بر پایهٔ مدل منطقی یا ریاضی که به منظور استفادهٔ بهینه از داده‌ها صورت می‌گیرد را یک ساختارِ داده‌ها گویند. ساختارهای داده‌ها انواع گوناگونی دارند که هر کدام مناسب برنامه‌های مختلفی هستند.

شماری از ساختارهای داده‌های پرکاربرد:

آرایه (Array)

صف (Queue)

پشته (Stack)

لیست پیوندی (Linked list)

گراف (Graph)

درخت (Tree)

جدول درهم‌سازی (Hash table)

در جاوا علاوه بر ساختمان داده های بالا ساختمان داده های دیگری هم وجود دارد

همه این موارد به خاطر اینکه به نوع داده محدویدتی ندارند و یه نوع ساختمان داده هستند جز Collection ها قرار می‌گیرند.

خوب منظورمون از اینکه به نوع داده محدود نیستن یعنی چی؟ منظور اینکه شبیه به آرایه ها که شما میتونید آرایه‌ای از هر چیز بسازین، میتونیم از Collection از هر نوع داده‌ای بسازیم بدون توجه به نوع داده!

خوب بریم سراغ ساده ترین کالکشن یا همان List. یک لیست چیزی به جز یک آرایه نیست که دارای طول متغییر هست. در واقع یک آرایه پویا هست که طول آن در حال تغییر هست.

(وارد جزییات نحوه پیاده سازی آن نمیشم، با اینکه برای اینکه به درستی بتونیم برنامه‌هامون رو بهینه کنیم نیاز به این داریم که نحوه پیاده سازی همه این ساختمان داده ها را بدونیم تا بدونیم کدوم رو در کجا استفاده کنیم.)

در جاوا یک لیست به صورت List به این صورت نوشته می‌شود:

List listName = new ArrayList<>();

مثلا:

List list1 = new ArrayList<>();
List list2 = new ArrayList<>();
List list3 = new ArrayList<>();

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

در واقع مشخص می‌کنیم type هر کدوم از خونه‌های این لیست یا آرایه پویا از چه جنسی باشد:

list1.add(“hello”);
list2.add(1000);

متد add در واقع عنصر شما را در انتهای آرایه قرار می‌دهد.

همچنین شما میتونید یه عنصر را در یک خانه مشخص اضافه کنید:

list1.add(3, “hi”);

با متد size() شما میتونید هر لحظه اندازه لیست خودتون رو بدونید:

list1.size();

و سایر متدها که از گفتنشون صرفه نظر میکنیم. ولی استفاده از اون‌ها لازم میشه

حتما بررسی کنید...

خوب بریم سراغ مطلب اصلی بحث. ما میتونیم این لیست پویا را به صورت‌های مختلف پیاده سازی‌کنیم. توجه کنید نوع عملکرد یعنی ورودی و خروجی ها یکسان هستند ولی نحوه ذخیره سازی پیاده‌سازی‌های مختلف متفاوت هست:

List list1 = new ArrayList<>();
List list2 = new LinkedList<>();

شما در بالا با دو نوع پیاده سازی مختلف لیست ها آشنا شدین. باز تاکیید میکنم همه توابع شبیه add یا size یا get برای هر دو نوع پیاده سازی خروجی های یکسانی دارد ولی نحوه پیاده سازی و نحوه ذخیره سازی اون‌ها در داخل حافظه متفاوت هست.

بنابراین ما باید با توجه به ساختار کد و نیاز تشخیص بدیم که از کدوم یک از پیاده سازی ها استفاده کنیم. همچنین شاید لازم باشه خودمان یه نوع پیاده سازی خاصی از لیست داشته باشیم! (که بخاطر پیچیده شدن بحث صرفه نظر می‌کنیم ولی اگه سوالی بود انتهای جلسه بپرسین)

فقط این نکته رو یادآوری کنم پیاده سازی به روش ArrayList از یک آرایه معمولی استفاده شده است ولی برای پیاده سازی LinkedList از اشاره‌گرها استفاده شده است.

کالکشن بعدی که در مورد اون صحبت می‌کنیم Set هست. دقیقا این کالکشن تعریف ریاضی مجموعه ها را دارند. در واقع مجموعه‌ای از داده‌ها که نمی‌توانند عضو تکراری داشته باشند و همچنین موقعیت عناصر اهمیتی ندارد.

Set set = new HashSet<>();

نکته قابلی توجهی که هست اینه که برای پیاده سازی این کالکشن از جدول درهم‌ساز (Hash table) استفاده شده است. بنابراین برای درج یک عنصر یا گرفتن یک عنصر نیاز به جستجو نیست. در واقع شما می‌تونید بدون استفاده از حلقه با یک درخواست مقداری رو بخونید یا بنویسید. (مرتبه از درجه ( o(1 هست)

یعنی فرض کنید شما به دنبال مثلا عدد ۵ در یک مجموعه باشید. برای set با یک رجوع می‌تونید این مقدار رو پیدا کنید ولی فرض کنید برای یک آرایه نیاز هست که از خانه اول شروع کرده و تک تک خانه‌ها رو بررسی کنید تا به خونه‌ای برسید که مقدار ان ۵ هست. (مرتبه از درجه ( o(n هست)

دقت کنید در یک set معنی ندارد که مثلا بگیم عنصر خونه دوم رو به ما بده! برای همین متد get ندارد. چون همان طور که بالا گفتیم در مجموعه‌ها موقعیت عناصر اهمیتی ندارد.

و آخرین ساختمان داده‌ای که این جلسه در مورد ان صحبت می کنیم، ساختمان داده Map هست. در واقع این ساختمان داده شبیه set هست با این تفاوت که هر عنصر که خود تکراری نیست می‌تواند انواع داده را در خود ذخیره کند! در واقع میشه این ساختمان داده رو به صورت کلید و مقدار تعریف کرد.

یعنی هر کلیدی که منحصر به فرد هست (تکراری نیست) یک مقدار به ان نسبت داده شده است:

Map map = new HashMap<>();

در واقع ما الان یک ساختمان داده‌ای داریم که کلید‌ آن از جنس Integer هست و هر کلیدی به یک String نگاشت شده است. در واقع من با داشتن یک کلید می‌تونم مقدار String مربوط به اون رو بخونم.

شبیه Set چون از جدول درهم‌ساز استفاده شده است، درج و گرفتن و جستجو از مرتبه ( o(1 هست. در واقع در این نوع ساختمان داده مقهومی به نام جستجو وجو ندارد. کافیست شما کلید را داشته باشید. با کمترین هزینه به مقدار خود میرسین.

map.put(1, “a”);
map.put(5, “hello”);
map.put(1000, “hi”);
String result = map.get(1);

دانلوددانلود PDF قسمت هشتم آموزش جاوا