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

HashSet وأسس مجموعات Set

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

HashSet وأسس مجموعات Set

تُعدّ Set مجموعةً لا تحتوي على عناصر مكرّرة أبدًا. هذا الضمان الوحيد يُشكّل كل قرار يتعلق بآلية عمل Set داخليًا وطريقة استخدامها. HashSet هي التطبيق الأكثر شيوعًا لـ Set في Java — إذ توفّر عمليات add وcontains وremove في وقت ثابت O(1) بالاستناد إلى جدول تجزئة داخلي.

عقد Set

تمتدّ الواجهة java.util.Set من Collection وتضيف قاعدة واحدة: لا يجوز تعايش عنصرين متساويين في المجموعة. "المساواة" تعني ما تُعيده equals() بقيمة true. لهذا السبب تُعيد add() القيمة false بدلًا من إطلاق استثناء حين تحاول إدراج عنصر مكرّر — يُتجاهَل العنصر ببساطة.

import java.util.HashSet;
import java.util.Set;

Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("backend");
tags.add("java");   // مكرّر — يُتجاهَل بصمت

System.out.println(tags.size());           // 2
System.out.println(tags.contains("java")); // true

ترتيب العناصر عند التكرار غير مضمون. لا يحفظ HashSet ترتيب الإدراج ولا أي ترتيب مُرتَّب. إن احتجتَ إلى ترتيب متوقّع، استخدم LinkedHashSet (ترتيب الإدراج) أو TreeSet (ترتيب مُرتَّب) — وكلاهما مُغطّى في دروس قادمة.

آلية عمل HashSet داخليًا

داخليًا، يعتمد HashSet<E> على HashMap<E, Object>. عند استدعاء add(element)، تقوم Java بخطوتين:

استدعاء element.hashCode() لتحديد "الدلو" الصحيح في جدول التجزئة.
استدعاء element.equals(other) مقابل أي عنصر موجود في ذلك الدلو للتحقق من التكرار.

هذه العملية ذات الخطوتين هي السبب في ضرورة صحة كلٍّ من hashCode وequals للكائنات الخاصة بك — لا يكفي أيٌّ منهما بمفرده.

عقد equals وhashCode

ينص عقد Java (الموثّق في Object) على:

إذا كانت a.equals(b) تُعيد true، فيجب أن تتحقق a.hashCode() == b.hashCode().
العكس غير مشترط: قد يتشارك كائنان نفس رمز التجزئة دون أن يكونا متساويين (تلك هي تصادمات التجزئة، وهي أمر طبيعي).

كسر العقد يُفسد HashSet بصمت. إن أعاد كائنان متساويان منطقيًا رموز تجزئة مختلفة، يهبطان في دلوَين مختلفين. لا تُقارنهما المجموعة بـ equals أبدًا، فيُخزَّن كلاهما — ينتهي بك الأمر بـ"مكرّرات" لا تستطيع المجموعة رؤيتها.

إليك فئة تُوضّح التطبيق الصحيح:

import java.util.Objects;

public final class Point {
    private final int x;
    private final int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point other)) return false;
        return x == other.x && y == other.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);   // متّسق مع equals
    }
}

مع هذه الفئة، يتعامل HashSet<Point> بصورة صحيحة مع كائنَي Point(1, 2) على أنهما متطابقان:

Set<Point> points = new HashSet<>();
points.add(new Point(1, 2));
points.add(new Point(1, 2));   // نفس القيمة، كائن مختلف

System.out.println(points.size());  // 1 — حُذف التكرار بشكل صحيح

ما يحدث مع equals وhashCode الافتراضيَّين

يُقارن Object.equals الافتراضي المراجع (نفس عنوان الذاكرة)، ويعتمد Object.hashCode على هوية الكائن. إن لم تُجاوز هذه التوابع، يُعدّ كل كائن فريدًا بصرف النظر عن قيم حقوله:

// Point بدون تجاوز equals/hashCode
Set<Point> broken = new HashSet<>();
broken.add(new Point(1, 2));
broken.add(new Point(1, 2));   // مرجع كائن مختلف

System.out.println(broken.size());  // 2 — لم يُحذف التكرار!

عمليات Set الشائعة

نظرًا لأن Set يُمثّل المجموعات الرياضية، فإن عمليات الدُفعات القياسية تُقابل مباشرة نظرية المجموعات:

Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4));
Set<Integer> b = new HashSet<>(Set.of(3, 4, 5, 6));

// الاتحاد  (a ∪ b)
Set<Integer> union = new HashSet<>(a);
union.addAll(b);             // {1, 2, 3, 4, 5, 6}

// التقاطع  (a ∩ b)
Set<Integer> intersection = new HashSet<>(a);
intersection.retainAll(b);   // {3, 4}

// الفرق  (a − b)
Set<Integer> difference = new HashSet<>(a);
difference.removeAll(b);     // {1, 2}

System.out.println(union);        // الترتيب غير مضمون
System.out.println(intersection);
System.out.println(difference);

استخدم Set.of(...) للمجموعات الصغيرة غير القابلة للتعديل. منذ Java 9 يمكنك كتابة Set.of(1, 2, 3) للحصول على مجموعة مدمجة وغير قابلة للتعديل. إن احتجتَ إلى مجموعة قابلة للتعديل مُملوءة مسبقًا، مرّرها إلى مُنشئ HashSet كما هو موضّح أعلاه.

اختيار تطبيق Set المناسب

HashSet — O(1) في المتوسط لعمليات الإضافة والبحث والحذف؛ دون ضمان للترتيب. الأفضل لمعظم حالات الاستخدام.
LinkedHashSet — أداء مماثل لـ HashSet لكنه يحفظ ترتيب الإدراج.
TreeSet — عمليات O(log n)؛ العناصر مرتّبة دائمًا. مُغطّى في الدرس التالي.

الخلاصة

تفرض Set التفرّد باستدعاء equals وhashCode على كل عنصر. يُطبّق HashSet هذا بجدول تجزئة، ما يمنح أداءً O(1) في المتوسط. القاعدة الحاسمة: إن خزّنتَ كائنات مخصّصة في أي Set (أو كمفاتيح في أي Map)، يجب عليك بالضرورة تجاوز كلٍّ من equals وhashCode بصورة متّسقة — كسر هذا العقد ينتج أخطاء بيانات صامتة يصعب تشخيصها للغاية.