در این مقاله دو پیاده‌سازی مختلف از واسط Map یعنی HashMap و TreeMap را با یکدیگر مقایسه می‌کنیم. هر دو پیاده‌سازی، بخش جدایی‌ناپذیری از چارچوب Java Collections هستند و داده‌ها را به صورت زوج‌های کلید-مقدار ذخیره می‌کنند.
در ادامه به بررسی تفاوت‌ها و شباهت‌های این دو پیاده‌سازی می‌پردازیم. با مطالعه این مقاله، به درک بهتری از ساختار این دو پیاده‌سازی می‌رسیم و متوجه می‌شویم که در چه شرایط و با چه نیازمندی‌هایی بهتر است به سراغ کدام یک از این دو برویم.
تفاوت‌ها
در این بخش، تفاوت‌های HashMap و TreeMap را ابتدا از منظر نحوه‌ی پیاده‌سازی، سپس از جهت نگه‌داری ترتیب داده‌ها و در نهایت نحوه رفتار آن‌ها در مواجه با کلید یا مقدارهای Null را بررسی می‌کنیم.
1- پیاده‌سازی
ابتدا در مورد HashMap صحبت می‌کنیم که پیاده‌سازی مبتنی بر جدول‌های درهم‌سازی (hashtable) دارد. این کلاس، از کلاس AbstractMap ارث‌بری کرده و واسط Map را پیاده‌سازی می‌کند. HashMap بر اساس اصل درهم‌سازی کار می‌کند و معمولا به عنوان یک جدول درهم‌سازیِ سطلی (Bucketed Hash Table) عمل می‌کند. البته باید بدانیم زمانی که سطل‌ها خیلی بزرگ شوند، تبدیل به نودهای TreeNodes می‌شوند که ساختاری مشابه با TreeMap دارد.
از طرفی دیگر، کلاس TreeMap از کلاس AbstractMap ارث‌بری کرده و واسط NavigableMap را پیاده‌سازی می‌کند. TreeMap داده‌ها را در درخت قرمز-سیاه که یک درخت جست‌وجوی دودویی خودمتوازن است، ذخیره می‌کند.
2- ترتیب
HashMap هیچ ضمانتی برای ترتیب قرارگیری داده‌ها در Map ندارد و در واقع هنگام پیمایش بر روی کلید و مقدارهای یک HashMap هیچ ترتیبی برای آن‌ها نمی‌توان متصور شد.
@Test
public void whenInsertObjectsHashMap_thenRandomOrder() {
Map<Integer, String> hashmap = new HashMap<>();
hashmap.put(3, "TreeMap");
hashmap.put(2, "vs");
hashmap.put(1, "HashMap");
assertThat(hashmap.keySet(), containsInAnyOrder(1, 2, 3));
}
با این وجود، داده‌ها در TreeMap به صورت صعودی بر اساس ترتیب طبیعی‌شان مرتب شده‌اند. اگر داده‌ها نتوانند به صورت طبیعی مرتب شوند، با استفاده از یک Comprator یا Comparable می‌توانیم ترتیب مورد نظرمان را تعریف کنیم.
@Test
public void whenInsertObjectsTreeMap_thenNaturalOrder() {
Map<Integer, String> treemap = new TreeMap<>();
treemap.put(3, "TreeMap");
treemap.put(2, "vs");
treemap.put(1, "HashMap");
assertThat(treemap.keySet(), contains(1, 2, 3));
}
3- Null
در HashMap امکان ذخیره کردن حداکثر یک کلید null و چندین مقدار null وجود دارد. برای مثال:
@Test
public void whenInsertNullInHashMap_thenInsertsNull() {
Map<Integer, String> hashmap = new HashMap<>();
hashmap.put(null, null);
assertNull(hashmap.get(null));
}
در TreeMap هیچ کلید Nullای نمی‌تواند ذخیره شود. اما مانند HashMap چندین مقدار Null می‌توان داشت.
@Test(expected = NullPointerException.class)
public void whenInsertNullInTreeMap_thenException() {
Map<Integer, String> treemap = new TreeMap<>();
treemap.put(null, "NullPointerException");
}
اگر از TreeMap با یک Comprator تعریف‌شده توسط کاربر استفاده می‌کنیم، نحوه‌ی مدیریت کلید و مقدارهای null بستگی به پیاده‌سازی متد ()compare دارد.
تحلیل کارایی
کارایی (Performance) بحرانی‌ترین معیاری است که در درک مناسب‌بودن ساختار دادهی به کار گرفته‌شده در یک مورد کاربرد (use case)، به ما کمک می‌کند. در این بخش، تحلیل جامعی از کارایی HashMap و TreeMap ارایه می‌شود.
1- HashMap
HashMap که یک پیاده‌سازی مبتنی بر جدول درهم‌سازی است، برای سازمان‌دهی عناصر خود بر اساس تابع درهم‌ساز، از ساختار دادهی مبتنی بر آرایه استفاده می‌کند. HashMap بیشتر عملیات‌ها مانند ()add و ()remove و ()contains را در زمان ثابت (O(1 انجام می‌دهد. بنابراین به طور چشمگیری از TreeMap سریع‌تر است. زمان میانگین برای جست‌وجوی یک عنصر در شرایط عادی، در جدول درهم‌سازی برابر با (O(1 است. اما پیاده‌سازی نامناسبِ تابع درهم‌ساز ممکن است باعث توزیع ضعیف و نامناسب مقادیر در سطل‌ها شود که این عواقب را در پی دارد:
- Memory Overhead: تعداد زیادی سطل بدون استفاده باقی میمانند.
- کاهش کارایی: هرچه تعداد تلاقی‌ها بیشتر شود، کارایی کمتر می‌شود.
تا قبل از جاوا 8، تنها روش پیشنهادی برای هندل کردن تلاقی‌ها، جداسازی زنجیره‌ای بود که معمولا با استفاده از لیست‌های پیوندی پیاده‌سازی می‌شود. به عبارت دیگر، اگر تلاقی‌ای وجود داشته باشد یعنی دو آیتم مختلف، مقدار درهم‌سازی یکسانی داشته باشند، هر دو آیتم در یک لیست پیوندی یکسان ذخیره می‌شوند.
بنابراین، جست‌وجوی یک آیتم در یک HashMap، در بدترین حالت به اندازه جست‌وجوی یک آیتم در داخل یک لیست پیوندی طول می‌کشد که برابر با زمان (O(n است.
زمانی که سطل‌ها از یک حدی بزرگ‌تر می‌شوند و شامل تعداد مناسبی node باشند، به مد TreeNode تبدیل می‌شوند که هر کدام ساختارشان شبیه همان ساختاری است که در TreeMap داشتند.
به این ترتیب، در صورتی که تعداد تلاقی‌ها زیاد باشد، کارایی بدترین حالت از (O(n به (O(log n بهبود می‌یابد.
کدی که این تبدیل را انجام می‌دهد، به این صورت است:
if(binCount >= TREEIFY_THRESHOLD - 1) {
treeifyBin(tab, hash);
}
مقدار TREEIFY_THRESHOLD برابر با است که به طور موثر تعداد آستانه جهت استفاده از درخت به جای لیست پیوندی برای سطل نشان می‌دهد.
پس می‌بینیم که:
- HashMap به حافظه بسیار بیشتری از مقدار مورد نیاز برای ذخیره‌سازی داده‌هایش نیاز دارد.
- HashMap نباید بیش از 70 تا 75 درصد پر شود. زیرا اگر پرتر شود، تغییر سایز داده و داده‌ها مجددا درهم‌سازی می‌شوند.
- درهم‌سازی مجدد نیازمند انجام n عملیات است که پرهزینه است در عین حال زمان ثابت درج نیز به (O(n تبدیل می‌شود.
- هزینه درج آیتم‌ها در HashMap توسط الگوریتم درهم‌سازی تعیین می‌شود.
عملکرد HashMap را می توان با تنظیم ظرفیت اولیه (initialCapacity) و عامل بار (loadFactor) در زمان ایجاد خود شی HashMap تنظیم کرد.
با این حال، باید زمانی HashMap را انتخاب کنیم که:
- تعداد حدودی آیتم‌هایی که در مجموعه می‌خواهیم نگه داریم را می‌دانیم.
- نمی‌خواهیم آیتم‌ها را به ترتیب طبیعی استخراج کنیم.
در شرایط فوق، HashMap بهترین انتخاب است. زیرا درج، حذف و جست‌وجو در زمان ثابت انجام می‌شود.
2- TreeMap
TreeMap داده‌هایش را در یک درخت سلسه‌مراتبی ذخیره می‌کند و توانایی مرتب‌سازی داده‌ها با کمک یک Comparator سفارشی را دارد.
خلاصه‌ای از کارایی‌اش:
- برای بیشتر عملیات‌ها مانند ()add و ()remove و ()contains، زمان اجرا برابر با (O(log n است.
- TreeMap در مقایسه با HashMap از حافظه کمتری استفاده می‌کند زیرا تنها به میزان مورد نیاز برای ذخیره آیتم‌هایش حافظه مصرف می‌کند.
- درخت برای حفظ کارایی مورد نظرش، باید تعادل را حفظ کند و این امر مستلزم تلاش زیادی است و باعث پیچیده شدن پیاده‌سازی می‌شود.
زمانی باید TreeMap را انتخاب کنیم که:
- محدودیت حافظه وجود دارد.
- تعداد آیتم‌هایی که باید در حافظه ذخیره شوند را نمی‌دانیم.
- می‌خواهیم داده‌ها را بر اساس ترتیب طبیعی استخراج کنیم.
- زمانی که داده‌ها به صورت پیاپی حذف و اضافه می‌شوند.
- زمانی که می‌خواهیم زمان جست‌وجو از مرتبه (O(log n باشد.
شباهت‌ها
در این بخش، شباهت‌های HashMap و TreeMap را ابتدا از نظر نحوه‌ی برخورد با آیتم‌های یکتا و سپس از نظر دسترسی‌های هم‌زمان به آن‌ها مورد بحث و بررسی قرار می‌دهیم.
1- آیتم‌های یکتا
HashMap و TreeMap هیچ‌کدام نمی‌توانند کلید تکراری داشته باشند و بدون هیچ خطا یا پرتاب استثنایی، مقدار آیتم قبلی که دارای کلید یکسان با آیتم جدید است را بازنویسی می‌کنند:
@Test
public void givenHashMapAndTreeMap_whenputDuplicates_thenOnlyUnique() {
Map<Integer, String> treeMap = new HashMap<>();
treeMap.put(1, "Baeldung");
treeMap.put(1, "Baeldung");
assertTrue(treeMap.size() == 1);
Map<Integer, String> treeMap2 = new TreeMap<>();
treeMap2.put(1, "Baeldung");
treeMap2.put(1, "Baeldung");
assertTrue(treeMap2.size() == 1);
}
2- دسترسی هم‌زمان
HashMap و TreeMap هیچ‌کدام synchronizeشده نیستند و دسترسی هم‌زمان را باید خودمان مدیریت کنیم. هر وقت چندین نخ (thread) به صورت هم‌زمان به آن‌ها دسترسی داشته باشند و حداقل یکی از نخ‌ها آن‌ها را تغییر دهد (write انجام دهد)، لازم است که خودمان آن‌ها را synchronize کنیم.
می‌توانیم به صورت صریح از Collections.synchronizemap(mapName استفاده کنیم تا یک synchronized view از map مورد نظرمان به ما بدهد.
از کدام پیاده‌سازی استفاده کنیم؟
دیدیم هر دو پیاده‌سازی مزایا و معایب خاص خود را دارند و این ما هستیم که باید با درک کامل شرایط و نیازمندی‌هایمان، انتخاب کنیم از کدام پیاده‌سازی استفاده کنیم.
به طور خلاصه:
- اگر می‌خواهیم داده‌هایمان را به صورت مرتب‌شده نگه‌داری کنیم، باید از TreeMap استفاده کنیم.
- اگر کارایی در مقایسه با حافظه اهمیت بیشتری برای ما دارد، باید از HashMap استفاده کنیم.
- از آنجایی که TreeMap داده‌ها را به صورت مرتب‌شده در کنار هم در حافظه نگه‌داری می‌کند، اگر می‌خواهیم به اشیایی که در ترتیب طبیعی به هم نزدیک هستند، دسترسی پیدا کنیم، بهتر است از TreeMap استفاده کنیم.
- HashMap با استفاده از initialCapacity و loadFactor قابل تنظیم شدن است. اما TreeMap این امکان را ندارد.
با ما همراه باشید:
آدرس کانال تلگرام: JavaCupIR@
آدرس اکانت توییتر: JavaCupIR@
آدرس صفحه اینستاگرام: javacup.ir
آدرس گروه لینکدین: Iranian Java Developers
