ویژگی های TreeMap در جاوا

اگر در حال خواندن این مقاله هستید، به احتمال زیاد با رابط نقشه و کاربردهای آن آشنا هستید . اگر نه، پس شما بروید. امروز در مورد ویژگی های پیاده سازی TreeMap و به طور خاص تر، تفاوت آن با HashMap و نحوه استفاده صحیح از آن صحبت خواهیم کرد.

مقایسه TreeMap، HashMap و LinkedHashMap

رایج ترین پیاده سازی رابط Map HashMap است . استفاده از آن آسان است و دسترسی سریع به داده ها را تضمین می کند و آن را به بهترین نامزد برای اکثر وظایف تبدیل می کند. بیشتر، اما نه همه. گاهی اوقات لازم است داده ها به صورت ساختاریافته با قابلیت پیمایش در آن ذخیره شوند. در این مورد، پیاده سازی دیگری از رابط Map به کمک می آید - TreeMap . TreeMap رابط NavigableMap را پیاده سازی می کند که از SortedMap ارث می برد که به نوبه خود از رابط Map به ارث می رسد . با پیاده‌سازی رابط‌های NavigableMap و SortedMap ، TreeMap قابلیت‌های بیشتری را به دست می‌آورد که HashMap ندارد ، اما این کار از نظر کارایی بهایی دارد. همچنین یک کلاس LinkedHashMap وجود دارد که همچنین به شما امکان می دهد داده ها را به ترتیب خاصی ذخیره کنید - به ترتیبی که اضافه شده اند. برای کمک به درک تفاوت بین این سه کلاس، به این جدول نگاه کنید: همانطور که می بینید، این کلاس ها اشتراکات زیادی دارند، اما تفاوت های کمی نیز دارند. اگرچه کلاس TreeMapچند منظوره ترین است، اما همیشه نمی توان آن را nullبه عنوان یک کلید ذخیره کرد. علاوه بر این، زمان دسترسی به عناصر TreeMap طولانی ترین خواهد بود. بنابراین، اگر نیازی به ذخیره داده ها به صورت مرتب شده ندارید، بهتر است از HashMapیا LinkedHashMap.

درخت آبنوس سرخ

همانطور که احتمالا متوجه شدید، در زیر کاپوت TreeMapاز ساختار داده ای به نام درخت قرمز-مشکی استفاده می کند. این ذخیره سازی داده ها در این ساختار است که ترتیب ذخیره سازی داده ها را تضمین می کند. این درخت چیست؟ بیایید آن را بفهمیم! تصور کنید که باید جفت‌های Number-String را ذخیره کنید. اعداد 16، 20، 52، 55، 61، 65، 71، 76، 81، 85، 90، 93، 101 کلید خواهند بود. اگر داده‌ها را در یک لیست سنتی ذخیره می‌کنید و نیاز به یافتن عنصری با کلید 101 دارید، برای یافتن آن باید تمام 13 عنصر را تکرار کنید. برای 13 عنصر این مهم نیست؛ هنگام کار با یک میلیون، مشکلات بزرگی خواهیم داشت. برای حل چنین مشکلاتی، برنامه نویسان از ساختارهای داده کمی پیچیده تر استفاده می کنند. بنابراین، با درخت قرمز و سیاه آشنا شوید!

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

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

• ریشه باید سیاه رنگ باشد.
• برگ های درخت باید سیاه باشد.
• یک گره قرمز باید دارای دو گره فرزند سیاه باشد.
• یک گره سیاه می تواند هر گره فرزندی داشته باشد.
• مسیر از یک گره به برگ های آن باید دارای همان تعداد گره سیاه باشد.
• گره های جدید به جای برگ ها اضافه می شوند.

اگر به قوانین 3، 4 و 5 با هم نگاه کنید، می توانید متوجه شوید که چگونه گره های رنگ آمیزی پیمایش را از طریق درخت سرعت می بخشد: مسیر عبور از گره های سیاه همیشه کوتاه تر از گره های قرمز است. بنابراین اندازه کل درخت با تعداد گره های سیاه مشخص می شود و به این اندازه «ارتفاع سیاه» می گویند. درخت قرمز-مشکی در زبان های برنامه نویسی مختلف پیاده سازی شده است. پیاده سازی های زیادی برای جاوا در اینترنت وجود دارد، بنابراین ما مدت زیادی روی آن نمی مانیم، اما همچنان با عملکرد آن آشنا می شویم TreeMap.

روش هایی که از رابط های SortedMap و NavigableMap مشتق شده اند

مانند HashMap، TreeMapاین رابط را پیاده سازی می کند Map، به این معنی که TreeMapهمه روش هایی را دارد که HashMap. اما علاوه بر این، اینترفیس ها و با به دست آوردن قابلیت های اضافی از آنها TreeMapرا پیاده سازی می کند . - رابطی که روش های مربوط به مجموعه داده های مرتب شده را گسترش داده و اضافه می کند: SortedMapNavigableMapSortedMapMap

• firstKey(): کلید اولین عنصر نقشه را برمی گرداند.
• lastKey(): کلید آخرین عنصر را برمی گرداند.
• headMap(K end): نقشه ای را برمی گرداند که شامل تمام عناصر موجود از ابتدا تا عنصر با کلید است end.
• tailMap(K start): نقشه‌ای را برمی‌گرداند که شامل تمام عناصر فعلی است که با عنصر شروع می‌شود startو با پایان ختم می‌شود.
• subMap(K start, K end): نقشه‌ای را برمی‌گرداند که شامل تمام عناصر فعلی است که با عنصر شروع شده startو با عنصر با کلید ختم می‌شود end.

NavigableMap- رابطی که SortedMapروش هایی را برای پیمایش بین عناصر نقشه گسترش داده و اضافه می کند:

• firstEntry(): اولین جفت کلید-مقدار را برمی گرداند.
• lastEntry(): آخرین جفت کلید-مقدار را برمی گرداند.
• pollFirstEntry(): اولین جفت را برمی گرداند و حذف می کند.
• pollLastEntry(): آخرین جفت را برمی گرداند و حذف می کند.
• ceilingKey(K obj): کوچکترین کلید k را که بزرگتر یا مساوی کلید obj است برمی گرداند. اگر چنین کلیدی وجود نداشته باشد، null را برمی‌گرداند.
• floorKey(K obj): بزرگترین کلید k را که کوچکتر یا مساوی کلید obj است برمی گرداند. اگر چنین کلیدی وجود نداشته باشد، null را برمی گرداند.
• lowerKey(K obj): بزرگترین کلید k که کوچکتر از کلید obj است را برمی گرداند. اگر چنین کلیدی وجود نداشته باشد، null را برمی گرداند.
• higherKey(K obj): کوچکترین کلید k که بزرگتر از کلید obj است را برمی گرداند. اگر چنین کلیدی وجود نداشته باشد، null را برمی‌گرداند.
• ceilingEntry(K obj): شبیه به متد roofKey(K obj)، اما یک جفت کلید-مقدار (یا تهی) را برمی‌گرداند.
• floorEntry(K obj): شبیه به متد floorKey(K obj)، اما یک جفت کلید-مقدار (یا تهی) را برمی‌گرداند.
• lowerEntry(K obj): شبیه به متد lowKey(K obj)، اما یک جفت کلید-مقدار (یا تهی) را برمی گرداند.
• higherEntry(K obj): شبیه به روش highKey(K obj) است، اما یک جفت کلید-مقدار (یا تهی) را برمی‌گرداند.
• descendingKeySet(): یک NavigableSet را برمی گرداند که شامل همه کلیدها است که به ترتیب معکوس مرتب شده اند.
• descendingMap(): یک NavigableMap حاوی تمام جفت ها که به ترتیب معکوس مرتب شده اند را برمی گرداند.
• navigableKeySet(): یک شی NavigableSet را برمی گرداند که شامل تمام کلیدها به ترتیب ذخیره سازی است.
• headMap(K upperBound, boolean incl): نقشه ای را برمی گرداند که شامل جفت ها از ابتدا تا عنصر upperBound است. آرگومان incl مشخص می کند که آیا عنصر upperBound باید در نقشه برگشتی گنجانده شود یا خیر.
• tailMap(K lowerBound, boolean incl): عملکرد مشابه روش قبلی است، فقط جفت ها از lowBound تا انتها برگردانده می شوند.
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): مانند روش‌های قبلی، جفت‌هایی از lowBound به upperBound برگردانده می‌شوند، آرگومان‌های lowIncl و highIncl نشان می‌دهند که آیا عناصر مرزی در نقشه جدید گنجانده شوند یا خیر.

در خود پیاده سازی TreeMap، علاوه بر سازنده هایی که با آنها آشنا هستیم، یک مورد دیگر اضافه می شود که نمونه ای از مقایسه کننده را می پذیرد. این مقایسه کننده مسئول ترتیب ذخیره عناصر خواهد بود.

نمونه هایی از استفاده از TreeMap

چنین فراوانی از روش های اضافی ممکن است غیر ضروری به نظر برسد، اما اغلب آنها بسیار مفیدتر از آنچه در ابتدا به نظر می رسید به نظر می رسند. بیایید با شما به این مثال نگاه کنیم. تصور کنید که ما در بخش بازاریابی یک شرکت بزرگ کار می کنیم و بانک اطلاعاتی از افرادی داریم که می خواهیم تبلیغات را به آنها نشان دهیم. دو نکته در این مورد وجود دارد:

• ما باید تعداد برداشت های هر فرد را پیگیری کنیم.
• الگوریتم نمایش تبلیغات به خردسالان متفاوت است.

بیایید کلاسی ایجاد کنیم Personکه تمام اطلاعات موجود در مورد یک شخص را ذخیره کند:

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

ما منطق را در کلاس پیاده سازی می کنیم Main:

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map){}
   public static void showAdvertisementToAdult(Map map){}
}

در کلاسی Mainکه ایجاد می کنیم TreeMap، جایی که keyیک شخص خاص است، و valueتعداد نمایش تبلیغات در این ماه است. در سازنده یک مقایسه کننده را پاس می کنیم که افراد را بر اساس سن مرتب می کند. با mapمقادیر تصادفی پر کنید. اکنون باید به اولین فرد بزرگسال در فروشگاه داده کوچک خود اشاره کنیم. ما این کار را با استفاده از Stream API انجام می دهیم. پس از این، دو نقشه مستقل به دست می آوریم که آنها را به روش های نمایش تبلیغات می گذرانیم. راه های زیادی وجود دارد که از طریق آنها می توان این مشکل را حل کرد. زرادخانه روش های کلاس TreeMapبه شما امکان می دهد راه حل هایی را برای هر سلیقه ای ابداع کنید. لازم نیست همه آنها را به خاطر بسپارید، زیرا همیشه می توانید از اسناد یا نکات محیط توسعه استفاده کنید. همین! امیدوارم کلاس TreeMapبرای شما واضح باشد و در حل مسائل عملی کاربرد دقیقی برای آن پیدا کنید.