إطار المجموعات

TreeMap و LinkedHashMap

15 دقيقة الدرس 7 من 14

TreeMap و LinkedHashMap

تعرفت سابقًا على HashMap: سريعة ولا ترتيب لها. لكن أحيانًا تحتاج أكثر من مجرد بحث سريع — تريد أن تخرج المفاتيح بترتيب يمكن التنبّؤ به. يوفّر Java تطبيقَين لواجهة Map يحلّان هذه المشكلة بطريقتين مختلفتين: TreeMap يحتفظ بالمفاتيح مرتّبة وفق ترتيبها الطبيعي أو مُقارِن مخصّص، بينما LinkedHashMap يحافظ على ترتيب إدراج المفاتيح.

لماذا يهمّنا الترتيب؟

تخيّل أنك تبني لوحة نتائج، أو قاموسًا مرتّبًا، أو ذاكرة تخزين مؤقت تُزيل الإدخال الأقدم أولًا. لا يضمن HashMap العادي أي ترتيب — قد تخرج العناصر بأي تسلسل. اختيار الخريطة المرتّبة المناسبة يجعل نيّتك صريحة ويُلغي خطوات الفرز المرهقة لاحقًا.

TreeMap — مرتّب حسب المفتاح

يعتمد TreeMap<K, V> داخليًا على شجرة Red-Black. كل عملية put وget تستغرق O(log n) بدلًا من O(1) المُخفَّف في خريطة التجزئة، لكن في المقابل تبقى الخريطة مرتّبة في كل الأوقات.

import java.util.TreeMap;

TreeMap<String, Integer> scores = new TreeMap<>();
scores.put("Charlie", 88);
scores.put("Alice",   95);
scores.put("Bob",     72);

// التكرار دائمًا يُعطي المفاتيح بترتيب أبجدي تصاعدي
for (var entry : scores.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}
// الناتج:
// Alice   = 95
// Bob     = 72
// Charlie = 88

لأن الشجرة مرتّبة دائمًا، يكشف TreeMap عن مجموعة غنية من دوال التنقّل التي لا تتوفّر في الخرائط العادية:

TreeMap<Integer, String> calendar = new TreeMap<>();
calendar.put(1,  "January");
calendar.put(6,  "June");
calendar.put(9,  "September");
calendar.put(12, "December");

System.out.println(calendar.firstKey());          // 1
System.out.println(calendar.lastKey());           // 12
System.out.println(calendar.floorKey(7));         // 6  (أكبر مفتاح <= 7)
System.out.println(calendar.ceilingKey(7));       // 9  (أصغر مفتاح >= 7)
System.out.println(calendar.headMap(9));          // {1=January, 6=June}
System.out.println(calendar.tailMap(6));          // {6=June, 9=September, 12=December}
System.out.println(calendar.subMap(6, 12));       // {6=June, 9=September}

واجهة NavigableMap: ينفّذ TreeMap واجهة NavigableMap التي تضيف: floorKey وceilingKey وlowerKey وhigherKey وheadMap وtailMap وsubMap. صرّح بمتغيّراتك كـ NavigableMap<K,V> عندما تريد كشف هذه الدوال للمستدعِين.

ترتيب مخصّص باستخدام Comparator

عندما تحتاج ترتيبًا مختلفًا — كالترتيب الأبجدي العكسي أو الترتيب غير الحساس لحالة الأحرف — مرّر Comparator إلى المُنشئ:

// ترتيب أبجدي عكسي
TreeMap<String, Integer> reversed = new TreeMap<>(Comparator.reverseOrder());
reversed.put("banana", 2);
reversed.put("apple",  1);
reversed.put("cherry", 3);

reversed.keySet().forEach(System.out::println);
// cherry → banana → apple

يجب أن تكون المفاتيح قابلة للمقارنة (أو يُزوَّد مُقارِن). إن خزّنت مفاتيح من فئة لا تنفّذ Comparable ولم تُقدّم مُقارِنًا، ستُقذف استثناء ClassCastException عند أول put في وقت التشغيل.

LinkedHashMap — مرتّب حسب الإدراج

يغلّف LinkedHashMap<K, V> جدول تجزئة عاديًا بقائمة مترابطة مضاعفة تمرّ عبر كل إدخال بحسب ترتيب إدراجه. عمليات البحث لا تزال O(1) — تمامًا كـ HashMap — لكن التكرار يعكس الترتيب الذي أُضيفت به المفاتيح أولًا.

import java.util.LinkedHashMap;

LinkedHashMap<String, String> capitals = new LinkedHashMap<>();
capitals.put("France",  "Paris");
capitals.put("Japan",   "Tokyo");
capitals.put("Brazil",  "Brasília");
capitals.put("Canada",  "Ottawa");

// ترتيب التكرار == ترتيب الإدراج
capitals.forEach((country, capital) ->
    System.out.println(country + " -> " + capital));
// France  -> Paris
// Japan   -> Tokyo
// Brazil  -> Brasília
// Canada  -> Ottawa

وضع الوصول — بناء ذاكرة تخزين LRU

يوجد شكل ثانٍ للمُنشئ: new LinkedHashMap<>(initialCapacity, loadFactor, true). المعامل الثالث يُحوّل الخريطة من ترتيب الإدراج إلى ترتيب الوصول: كل get أو put ينقل الإدخال المُصلَح إلى ذيل القائمة المترابطة. بالتزامن مع تجاوز removeEldestEntry تحصل على ذاكرة تخزين مؤقت بسيطة من نوع LRU (الأقل استخدامًا مؤخرًا) في نحو عشرة أسطر:

import java.util.LinkedHashMap;
import java.util.Map;

int MAX = 3;

LinkedHashMap<String, String> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > MAX;
    }
};

lruCache.put("a", "apple");
lruCache.put("b", "banana");
lruCache.put("c", "cherry");

lruCache.get("a");            // "a" أصبح الأكثر استخدامًا مؤخرًا

lruCache.put("d", "date");    // يُشغّل removeEldestEntry؛ "b" الأقدم → يُحذف

System.out.println(lruCache.keySet()); // [c, a, d]

هذا نمط ذاكرة LRU الكلاسيكي في Java. يعمل بشكل مثالي للذاكرات المؤقتة بحجم عشرات الآلاف من الإدخالات في سياق أحادي الخيط. لذاكرة LRU آمنة للخيوط، اعمل على تغليفها بـ Collections.synchronizedMap أو استخدم مكتبة متخصصة.

الاختيار بين تطبيقات الخريطة الثلاثة

HashMap — الأسرع (O(1) مُخفَّف)، لا ضمان للترتيب. استخدمها حين لا يهمّك الترتيب.
LinkedHashMap — بحث O(1)، تحفظ ترتيب الإدراج (أو الوصول). استخدمها لتكرار يمكن التنبّؤ به، أو ترتيب تسلسل JSON، أو ذاكرات LRU.
TreeMap — عمليات O(log n)، مرتّبة دائمًا. استخدمها حين تحتاج استعلامات نطاق أو دوال تنقّل أو ناتج مرتّب مضمون.

مقارنة سريعة

// HashMap   — ترتيب عشوائي، الأسرع
Map<String, Integer> hash   = new HashMap<>();

// LinkedHashMap — ترتيب الإدراج، نفس سرعة HashMap
Map<String, Integer> linked = new LinkedHashMap<>();

// TreeMap   — ترتيب مرتّب، أبطأ (log n)
Map<String, Integer> tree   = new TreeMap<>();

برمج للواجهة. صرّح بمتغيّراتك كـ Map<K, V> إلا إن احتجت تحديدًا دوال NavigableMap. هذا يُبقي كودك مرنًا — تستطيع تبديل التطبيق دون لمس مواقع الاستدعاء.

الخلاصة

يحتفظ TreeMap بالمفاتيح مرتّبة (ترتيب طبيعي أو Comparator مخصّص) على حساب عمليات O(log n)، ويضيف دوال تنقّل قوية كـ floorKey وceilingKey وsubMap. أما LinkedHashMap فيحافظ على ترتيب الإدراج (أو ترتيب الوصول عند تفعيل ذلك الخيار) بسرعة O(1) — مما يجعله مثاليًا للتكرار المتوقّع وذاكرات LRU. اختر بناءً على ما إذا كنت تحتاج تنقّلًا مرتّبًا، أو ترتيب إدراج، أو أقصى سرعة.