نقشه درختی در جاوا

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

مقایسه TreeMap، HashMap و LinkedHashMap

بیشترین استفاده از رابط Map HashMap است. استفاده از آن آسان است و دسترسی سریع به داده ها را تضمین می کند، بنابراین بهترین نامزد برای حل اکثر مشکلات است. بیشتر، اما نه همه. گاهی اوقات شما نیاز دارید که داده ها را به روشی ساختاریافته ذخیره کنید و بتوانید در میان آنها پیمایش کنید. در این صورت پیاده سازی دیگری از رابط نقشه (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 عنصر، این مسئله مهمی نیست، اما هنگام کار با یک میلیون، مشکلات بزرگی خواهیم داشت. برای حل این مشکلات، برنامه نویسان از ساختارهای داده کمی پیچیده تر استفاده می کنند. اینجاست که درخت سرخ سیاه وارد صحنه می شود! جستجو برای یک عنصر از ریشه درخت شروع می شود که در مورد ما 61 است. سپس مقادیر گره را با مقداری که به دنبال آن هستیم مقایسه می کنیم. اگر ارزش ما کمتر باشد، به سمت چپ می رویم. اگر بزرگتر است، به سمت راست می رویم. این روند تا زمانی تکرار می شود که مقدار مورد نظر را پیدا کنیم یا با عنصری که مقدار آن null است (برگی از درخت) مواجه شویم. رنگ های قرمز و سیاه برای ساده تر کردن مسیر و تعادل درخت استفاده می شود. قوانینی وجود دارد که همیشه باید هنگام ساختن یک درخت قرمز و سیاه رعایت شود:

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

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

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

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

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

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

• firstEntry() : اولین جفت کلید-مقدار را برمی گرداند
• lastEntry() : آخرین جفت کلید-مقدار را برمی گرداند
• pollFirstEntry() : اولین جفت را برمی گرداند و حذف می کند
• pollLastEntry() : آخرین جفت را برمی گرداند و حذف می کند
• roofKey(K obj) : کوچکترین کلید k که بزرگتر یا مساوی با کلید obj است را برمی گرداند. اگر چنین کلیدی وجود نداشته باشد، null را برمی گرداند
• floorKey(K obj) : بزرگترین کلید k که کمتر یا مساوی با کلید obj است را برمی گرداند. اگر چنین کلیدی وجود نداشته باشد، null را برمی گرداند
• lowKey(K obj) : بزرگترین کلید k که کمتر از کلید obj است را برمی گرداند. اگر چنین کلیدی وجود نداشته باشد، null را برمی گرداند
• HighKey(K obj) : کوچکترین کلید k که بزرگتر از کلید obj است را برمی گرداند. اگر چنین کلیدی وجود نداشته باشد، null را برمی گرداند
• roofEntry(K obj) : شبیه به روش roofKey(K obj)، فقط یک جفت کلید-مقدار (یا تهی) را برمی گرداند.
• floorEntry(K obj) : مشابه متد floorKey(K obj)، فقط یک جفت کلید-مقدار (یا تهی) را برمی گرداند.
• lowEntry(K obj) : شبیه به روش lowKey(K obj)، فقط یک جفت کلید-مقدار (یا تهی) را برمی گرداند.
• highEntry(K obj) : مشابه روش highKey(K obj)، فقط یک جفت کلید-مقدار (یا تهی) را برمی گرداند.
• () descendingKeySet : یک NavigableSet حاوی تمام کلیدهای مرتب شده به ترتیب معکوس را برمی گرداند.
• () descendingMap : یک NavigableMap را برمی گرداند که شامل تمام جفت ها به ترتیب معکوس مرتب شده است.
• navigableKeySet() : یک شی NavigableSet را برمی گرداند که شامل تمام کلیدها به ترتیب ذخیره شده است.
• headMap (K upperBound، boolean incl) : نقشه‌ای را برمی‌گرداند که شامل جفت‌هایی از ابتدا تا عنصر upperBound است. پارامتر incl نشان می دهد که آیا عنصر upperBound در نقشه برگشتی گنجانده شود یا خیر
• tailMap (K lowBound، boolean incl) : عملکردی مشابه روش قبلی، فقط جفت ها را از lowBound به انتها برمی گرداند.
• subMap(K lowBound، 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("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 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 ایجاد کنید، که در آن هر کلید نشان دهنده یک شخص خاص است و هر مقدار ، تعداد نمایش تبلیغات در این ماه است. ما از سازنده یک مقایسه کننده عبور می کنیم که افراد را بر اساس سن مرتب می کند. نقشه را با مقادیر دلخواه پر می کنیم. اکنون می‌خواهیم به اولین فرد بزرگسال در مخزن داده کوچک خود اشاره کنیم. ما این کار را با استفاده از Stream API انجام می دهیم. سپس دو نقشه جداگانه دریافت می کنیم که به روش هایی که تبلیغات را نشان می دهند منتقل می کنیم. راه های بسیار زیادی وجود دارد که ما می توانستیم این وظیفه را انجام دهیم. زرادخانه روش های کلاس TreeMap به ما امکان می دهد برای هر نیازی راه حل های سفارشی ایجاد کنیم. لازم نیست همه آنها را به خاطر بسپارید، زیرا همیشه می توانید از اسناد یا نکات IDE خود استفاده کنید. برای تقویت آموخته هایتان، پیشنهاد می کنیم یک درس ویدیویی از دوره جاوا ما تماشا کنید فعلاً همین است! امیدوارم کلاس TreeMap هم اکنون برای شما واضح باشد و آن را به درستی در حل تکالیف کدنویسی کاربردی به کار ببرید.