Java HashSet: ערכים ייחודיים, בדיקת שייכות ופעולות על קבוצות

Set שומר ערכים ייחודיים

HashSet (מ-java.util) הוא אוסף שמחזיק כל ערך לכל היותר פעם אחת. אין בו מפתחות וערכים בזוגות כמו ב-HashMap: רק שק של איברים שונים זה מזה. כל התפקיד שלו הוא לענות מהר על שאלה אחת: "האם הדבר הזה נמצא כאן?"

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

public class Main {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("backend");
        tags.add("java");   // כפילות: מתעלמים ממנה

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

יש פרמטר טיפוס אחד, <ElementType>. כמו עם ArrayList ו-HashMap, בדרך כלל מגדירים את המשתנה כממשק Set ויוצרים HashSet.

add מחזירה אם הערך היה חדש

add לא רק שומרת את הערך: היא מחזירה boolean שאומר אם הקבוצה באמת השתנתה. הוספה של ערך שכבר קיים מחזירה false ומשאירה את הקבוצה בלי שינוי.

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

public class Main {
    public static void main(String[] args) {
        Set<Integer> seen = new HashSet<>();

        System.out.println(seen.add(7));  // true: 7 היה חדש
        System.out.println(seen.add(7));  // false: כבר קיים
        System.out.println(seen);
    }
}

ערך ההחזרה הזה שימושי באמת: if (!seen.add(x)) { /* x is a repeat */ } מאפשר לזהות כפילויות בשורה אחת תוך כדי תנועה.

הסרת כפילויות מרשימה

מכיוון שקבוצה דוחה חזרות, הדרך המהירה ביותר להסיר כפילויות מאוסף היא לשפוך אותו לתוך קבוצה. הבנאי של HashSet מקבל כל אוסף אחר:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Ada", "Boris", "Ada", "Chen", "Boris"));

        Set<String> unique = new HashSet<>(names);
        System.out.println(unique);          // כל שם פעם אחת
        System.out.println(unique.size());   // 3

        // צריכים בחזרה List?
        List<String> deduped = new ArrayList<>(unique);
        System.out.println(deduped.size());  // 3
    }
}

זו הסיבה הנפוצה ביותר שמתחילים פונים לקבוצה. רק דעו שבדרך הלוך ושוב מאבדים את הסדר המקורי: השתמשו ב-LinkedHashSet אם הסדר חשוב (על זה בהמשך).

contains, remove ו-size

הפעולות היומיומיות דומות לאלה של האוספים האחרים:

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

public class Main {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("backend");
        tags.add("api");

        System.out.println(tags.contains("api"));  // true
        System.out.println(tags.size());           // 3

        tags.remove("backend");
        System.out.println(tags.contains("backend")); // false

        tags.clear();
        System.out.println(tags.isEmpty());         // true
    }
}

היתרון הגדול על פני ArrayList הוא contains. רשימה צריכה לעבור על כל איבר כדי לענות (O(n)); HashSet קופץ כמעט ישר לתשובה (בערך O(1)). כשאתם מוצאים את עצמכם קוראים ל-list.contains(...) בתוך לולאה, זה בדרך כלל הסימן לעבור לקבוצה.

פעולות על קבוצות: איחוד, חיתוך, הפרש

קבוצות זורחות כשמשלבים אותן. המתודות נקראות בפשטות ברגע שיודעים מי זו מי:

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

public class Main {
    public static void main(String[] args) {
        Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4));
        Set<Integer> b = new HashSet<>(Set.of(3, 4, 5, 6));

        Set<Integer> union = new HashSet<>(a);
        union.addAll(b);            // כל מה שנמצא באחת מהקבוצות
        System.out.println(union);  // 1 2 3 4 5 6

        Set<Integer> intersection = new HashSet<>(a);
        intersection.retainAll(b);  // רק מה שנמצא בשתיהן
        System.out.println(intersection); // 3 4

        Set<Integer> difference = new HashSet<>(a);
        difference.removeAll(b);    // ב-a אבל לא ב-b
        System.out.println(difference);   // 1 2
    }
}

המלכודת העיקרית: addAll, retainAll ו-removeAll משנות את הקבוצה שעליה הן נקראות. בגלל זה כל דוגמה מעתיקה קודם את a ל-HashSet חדש: אחרת הייתם הורסים את המקור. בנו קבוצה חדשה לכל תוצאה.

HashSet לא שומר על סדר

כמו HashMap, גם HashSet לא מבטיח שום סדר מעבר, והסדר יכול להשתנות בין הרצות. אם צריך סדר צפוי:

• LinkedHashSet שומר על סדר ההכנסה: הסדר שבו הוספתם את האיברים.
• TreeSet שומר את האיברים ממוינים לפי הסדר הטבעי (או לפי Comparator שתספקו).

import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<String> insertion = new LinkedHashSet<>();
        insertion.add("gamma");
        insertion.add("alpha");
        insertion.add("beta");
        System.out.println(insertion);  // [gamma, alpha, beta]

        Set<String> sorted = new TreeSet<>(insertion);
        System.out.println(sorted);      // [alpha, beta, gamma]
    }
}

שלושתם מממשים את הממשק Set, כך שהחלפה ביניהם היא שינוי של שורה אחת בבנאי.

איברים חייבים לתמוך ב-hashing

מתחת לפני השטח HashSet מבוסס על HashMap, ולכן אותו כלל חל: הוא מאתר איברים על ידי hashing, כלומר hashCode() ו-equals() של איבר חייבים להסכים ביניהם. טיפוסים מובנים כמו String ו-Integer כבר עושים את זה נכון, ולכן מחרוזות "java" כפולות מתמזגות כמו שצריך בדוגמאות הקודמות. אם אתם שומרים מופעים של מחלקה משלכם, דרסו גם את equals וגם את hashCode: אחרת שני אובייקטים ש"שווים" במשמעות שלהם ייחשבו שונים, ו-contains והסרת הכפילויות ייכשלו בשקט.

הבא בתור: מעבר על אוספים

הכרתם עכשיו את שלושת האוספים העיקריים: ArrayList, HashMap ו-HashSet. על כל אחד עוברים קצת אחרת, ויש מלכודות עדינות (כמו שינוי אוסף בזמן שעוברים עליו בלולאה). בהמשך נחבר את הכול יחד ונסביר איך לעבור על אוספים בצורה נקייה עם לולאת for-each, איטרטורים ו-forEach.