HashSet ב-Java

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

• כי המחלקה מיישמת את הממשק Set, היא יכולה לאחסן רק ערכים ייחודיים;
• יכול לאחסן ערכי NULL;
• סדר הוספת האלמנטים מחושב באמצעות קוד hash;
• HashSetמיישם גם את ה- Serializableו Cloneable.

כדי לשמור על זמן ביצוע קבוע של פעולות, הזמן המושקע בפעולות עם HashSet, חייב להיות פרופורציונלי ישיר למספר האלמנטים ב HashSet+ "הקיבולת" של המופע המובנה HashMap(מספר ה"סלים"). לכן, כדי לשמור על ביצועים, חשוב לא להגדיר את הקיבולת הראשונית גבוה מדי (או את מקדם העומס נמוך מדי). קיבולת ראשונית - המספר הראשוני של תאים ("פחים") בטבלת הגיבוב. אם כל התאים מלאים, מספרם יגדל באופן אוטומטי. מקדם העומס הוא מדד לכמה הוא יכול להיות מלא HashSetלפני שהקיבולת שלו תגדל אוטומטית. כאשר מספר האלמנטים ב HashSetהופך להיות גדול מהמכפלה של הקיבולת הראשונית ומקדם העומס, טבלת הגיבוב עוברת גיבוב מחדש (קודי הגיבוב של האלמנטים מחושבים מחדש והטבלה נבנית מחדש בהתאם לערכים שהתקבלו) והמספר של תאים בו מוכפל. מקדם העומס = מספר האלמנטים המאוחסנים בטבלה / גודל טבלת הגיבוב. לדוגמה, אם המספר ההתחלתי של התאים בטבלה הוא 16, ומקדם העומס הוא 0.75, אז נובע שכאשר מספר התאים המלאים מגיע ל-12, מספר התאים יגדל אוטומטית. מקדם עומס וקיבולת ראשונית הם שני הגורמים העיקריים המשפיעים על הביצועים של HashSet. מקדם עומס של 0.75 מספק ביצועים טובים בממוצע. אם הפרמטר הזה גדל, עומס הזיכרון יקטן (כיוון שהוא יקטין את מספר ה-hashs והבנייה מחדש), אבל זה ישפיע על פעולות ההוספה והחיפוש. כדי למזער את הזמן המושקע ב-hashing מחדש, עליך לבחור את פרמטר הקיבולת הראשוני הנכון. אם הקיבולת הראשונית גדולה מהמספר המרבי של אלמנטים חלקי מקדם העומס, אז לא תתרחש פעולת גיבוב מחדש כלל. חָשׁוּב: HashSetאינו מבנה נתונים עם סנכרון מובנה, כך שאם מספר שרשורים עובדים עליו בו זמנית, ולפחות אחד מהם מנסה לבצע שינויים, יש צורך לספק גישה מסונכרנת מבחוץ. זה נעשה לעתים קרובות על חשבון אובייקט מסונכרן אחר המקיף את ה- HashSet. אם אין אובייקט כזה, אז ה- Collections.synchronizedSet(). זוהי כרגע הדרך הטובה ביותר למנוע פעולות שאינן מסונכרנות עם HashSet.

Set s = Collections.synchronizedSet(new HashSet(...));

בוני HashSet:

1. HashSet h = new HashSet(); - בנאי ברירת מחדל. ברירת המחדל של הקיבולת הראשונית היא 16, מקדם הטעינה הוא 0.75.
2. HashSet h = new HashSet(int initialCapacity)– קונסטרוקטור בעל יכולת התחלתית נתונה. מקדם עומס – 0.75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);- קונסטרוקטור עם קיבולת התחלתית וגורם עומס נתון.
4. HashSet h = new HashSet(Collection C)– קונסטרוקטור המוסיף אלמנטים מאוסף אחר.

הקוד שלהלן מדגים כמה שיטות HashSet:

import java.util.*;

class Test
{
    public static void main(String[]args)
    {
        HashSet<String> h = new HashSet<String>();

        // Add elements to the HashSet using the add() method
        h.add("India");
        h.add("Australia");
        h.add("South Africa");
        h.add("India");// try to add another same element

        // Print the elements of the HashSet to the console
        System.out.println(h);
        System.out.println("List contains India or not:" +
                           h.contains("India"));

        // Remove elements from the set using the remove() method
        h.remove("Australia");
        System.out.println("List after removing Australia:"+h);

        // Loop through the elements of the HashSet using an iterator:
        System.out.println("Iterating over list:");
        Iterator<String> i = h.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}

סיכום:

[South Africa, Australia, India]
List contains India or not:true
List after removing Australia:[South Africa, India]
Iterating over list:
South Africa
India

כל המחלקות שמיישמות ממשק Setנתמכות באופן פנימי על ידי יישומים Map. HashSetמאחסן אלמנטים באמצעות HashMap. למרות HashMapשרכיב חייב להיות מיוצג כזוג מפתח-ערך כדי להוסיף לו אלמנט, HashSetרק הערך מתווסף אליו. למעשה, הערך שאנו מעבירים אליו HashSetהוא המפתח לאובייקט HashMap, וקבוע משמש כערך HashMap. כך, בכל זוג מפתח-ערך, לכל המפתחות יהיה אותו ערך. יישום HashSetב java doc:

private transient HashMap map;

// Constructor - 1
// All constructors implicitly create a HashMap object.
public HashSet()
{
    // Create an implicit HashMap object
    map = new HashMap();
}

// Constructor- 2
public HashSet(int initialCapacity)
{
    // Create an implicit HashMap object
    map = new HashMap(initialCapacity);
}

// An object of the Object class, each time acting as a value in the HashMap
private static final Object PRESENT = new Object();

אם אתה מסתכל על השיטה add()y HashSet:

public boolean add(E e)
{
   return map.put(e, PRESENT) == null;
}

אתה יכול לשים לב שהשיטה add()y HashSetקוראת למתודה put()על האובייקט הפנימי HashMap, ומעבירה לה את האלמנט שיש להוסיף כמפתח, ואת הקבוע PRESENT כערך. השיטה פועלת בצורה דומה remove(). זה קורא לשיטת remove()האובייקט הפנימי HashMap:

public boolean remove(Object o)
{
  return map.remove(o) == PRESENT;
}

HashSetמבוסס על טבלת גיבוב, ופעולות הוספה, מחיקה או חיפוש יסתיימו בממוצע בזמן קבוע (O(1)) . שיטות HashSet:

1. boolean add(E e): מוסיף אלמנט ל- HashSet, אם אין כזה, אבל אם אלמנט כזה כבר קיים, השיטה מחזירה false .
2. void clear():מסיר את כל הרכיבים מקבוצה.
3. boolean contains(Object o): מחזירה true אם האלמנט הנתון קיים בקבוצה.
4. boolean remove(Object o): מסיר את האלמנט הנתון מהקבוצה, אם קיים.
5. Iterator iterator(): מחזירה איטרטור עבור רכיבי הסט.
6. boolean isEmpty(): מחזירה true אם אין אלמנטים בקבוצה.
7. Object clone(): מבצע שיבוט משטח HashSet.

Javadoc: https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html