TreeMap

کلاس TreeMap زیر کلاس AbstractMap است و مفهوم Map را پیاده سازی می کند ، قبلاً با مفهوم Map آشنا شدیم ، کلاس TreeMap از درخت موازنه Red-Black برای نگه داری زوج کلید-مقدار استفاده می کند و درخت مربوطه از روی کلید ها ساخته می شود ، برای خلاف HashMap که نظم خاصی را برای کلید ها حفظ نمی کند در TreeMap کلید ها به صورت پیش فرض بر اساس ترتیب الفبایی نگه داری می شوند. عملیات درج ، حذف و جست و جو در TreeMap بسیار سریع است و این ویژگی آن باعث می شود به عنوان یک ابزار بهینه سازی از آن استفاده شود. کلاس TreeMap از طریق مسیر java.util.TreeMap قابل دستیابی است. برای ساخت یک شی جدید از TreeMapمی توانیم از یکی از سازنده های زیر استفاده کنیم :

TreeMap()

این سازنده یک TreeMap خالی ایجاد می کند.

TreeMap(Comparator cmp)

اگر بخواهیم کلید ها بر اساس یک ترتیب اختصاصی نگه داری شوند می توانیم برای اینکار یک Comparator ایجاد کنیم و آن را به سازنده TreeMap ارسال کنیم.

TreeMap(Collection c)

این سازنده یک TreeMap جدید ایجاد می کند و اعضای کالکشن c را به آن اضافه می کند.

TreeMap(SortedMap sm)

مشابه سازنده قبلی است با این تفاوت که در اینجا آیتم ها با همان ترتیب sm در TreeMap نگه داری می شوند. متد های مهم TreeMap در جدول زیر آمده اند :

متد کاربرد
ceilingEntry(Object key) یک زوج کلید-مقدار که کلید آن بزرگتر یا مساوی با key باشد بر می گرداند.
ceilingKey(Object key) یک کلید که بزرگتر یا مساوی با key باشد بر می گرداند.
clear() کل مجموعه را پاک می کند.
comparator() Comparator ای که برای مقایسه کلید ها به کار می رود را بر می گرداند اگر مجموعه از ترتیب طبیعی پیروی کند و Comparator نداشته باشد خروجی این متد null خواهد بود.
containsKey(Object key) بررسی می کند که کلید مورد نظر وجود دارد یا خیره؟
containsValue(Object value) بررسی می کند که مقدار مورد نظر وجود دارد یا خیر؟
descendingKeySet() یک لیست معکوس از کلید های مجموعه را بر می گرداند.
NavigableMap descendingMap() معکوس مپ فعلی را بر می گرداند.(ترتیب کلید ها معکوس خواهد بود)
entrySet() تمامی زوج های کلید-مقدار را به صورت یک Set بر می گرداند.
Map.Entry firstEntry() اولین زوج کلید-مقدار با کوچکترین کلید را بر می گرداند.
firstKey() کوچکترین کلید را بر می گرداند.
Map.Entry floorKey(Object key) یک زوج کلید-مقدار بر می گرداند که در آن کلید کوچکتر یا مساوی با key باشد.
floorKey(Object key) کلیدی که کوچکتر یا مساوی با key باشد بر می گرداند.
Object get(Object key) مقدار متناظر با یک کلید را بر می گرداند.
headMap(Object toKey) یک زیر مجموعه به صورت SortedMap بر می گرداند که در آن کلید ها از toKey کوچکتر هستند.
higherEntry(Object key) یک زوج کلید-مقدار بر می گرداند که در آن کلید از key بزرگتر باشد.
higherkey(Object key) کلیدی که از key بزرگتر باشد را بر می گرداند.
keySet() کل کلید ها را بر می گرداند.
Map.Entry lastEntry() آخرین زوج کلید-مقدار با بزرگترین کلید را بر می گرداند.
Object lastKey() بزرگترین کلید را بر می گرداند.
lowerEntry(Object key) یک زوج کلید-مقدار بر می گرداند که در آن کلید از key کوچکتر باشد.
pollFirstEntry() اولین زوج کلید-مقدار با کوچکترین کلید را حذف می کند.
pollLastEntry() آخرین زوج کلید-مقدار با بزرگترین کلید را حذف می کند.
put(Object key,Object value) مقدار value را به کلید key نسبت می دهد.
void putAll(Map mp) کل اعضای mp را به مجموعه اضافه می کند.
remove(Object key) زوج کلید-مقدار متناظر با کلید key را حذف می کند.
size() تعداد کلید ها را بر می گرداند.
subMap(Object fromKey,Object toKey) یک زیر مجموعه بر می گرداند.
SortedMap tailMap(Object fromKey) زیر مجموعه ای را بر می گرداند که در آن کلید ها بزرگتر یا مساوی fromkey هستند.
values() مجموعه ای از مقادیر را بر می گرداند.

به مثال زیر توجه کنید :

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

public class TreeMapDemo 
{
    public static void main(String[] args) 
    {
        TreeMap treemap = new TreeMap();

        treemap.put(2, "A");
        treemap.put(9, "B");
        treemap.put(3, "A");
        treemap.put(7, "D");
        treemap.put(7, "X");
        treemap.put(12, "C");

        System.out.println(treemap);

        Map.Entry first = treemap.pollFirstEntry();
        System.out.println(first.getKey() + " , " + first.getValue());

        System.out.println(treemap);

        System.out.println(treemap.get(3));

        System.out.println(treemap.keySet());

        System.out.println("<=7 :" + treemap.floorKey(7));
        System.out.println(">=7 :" + treemap.ceilingKey(7));
        System.out.println("<7  :" + treemap.lowerKey(7));
        System.out.println(">7  :" + treemap.higherKey(7));

        System.out.println("<=5 :" + treemap.floorKey(5));
        System.out.println(">=5 :" + treemap.ceilingKey(5));
        System.out.println("<5  :" + treemap.lowerKey(5));
        System.out.println(">5  :" + treemap.higherKey(5));
    }
}
{2=A, 3=A, 7=X, 9=B, 12=C}
2 , A
{3=A, 7=X, 9=B, 12=C}
A
[3, 7, 9, 12]
<=7 :7
>=7 :7
<7 :3
>7 :9
<=5 :3
>=5 :7
<5 :3
>5 :7

در مثال بالا ابتدا یک TreeMap ایجاد کرده و به صورت نامنظم داده هایی را به آن اضافه کرده و سپس آن را چاپ می کنیم ، مشاهده می کنیم که مجموعه به صورت مرتب (بر اساس کلید ها) چاپ می شود ، به علاوه چون کلید ها منحصر به فرد است برای کلید 7 فقط مقدار X (آخرین مقداری که برای این کلید درج شد) نگه داری می شود. همچنین می بینیم که مقادیر می توانند تکراری باشند.(مقادیر کلید های 2 و 3 برابر با A است). سپس اولین زوج کلید-مقدار را حذف و چاپ می کنیم و بعد از آن کل مجموعه را مجدداً چاپ می کنیم. مقدار متناظر با کلید 3 را چاپ می کنیم. مجموعه کل کلید ها را با متد keySet به دست آورده و چاپ می کنیم. در ادامه یک بار با کلید 7 که جز کلید های مجموعه است و یک بار با کلید 5 که جز کلید های مجموعه نیست متد های floorKey و ceilingKey و lowerKey و higherKey را مورد بررسی قرار می دهیم.