19. HashSet

HashSet

לפעמים אנחנו רוצים שיהיה לנו איזה Collection, שכל מה שמעניין אותנו זה שנוכל לבדוק האם איבר נמצא בו או לא בדרך מהירה.

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

אם נשתמש בList, או בCollection סטנדרטי אחר חיפוש איבר יקח $ o(n) $, כיוון שפשוט אנחנו עוברים על כל האיברים ובודקים על כל אחד האם הוא שווה לאיבר שאנחנו מחפשים או לאו.

לכן עולה הרעיון של להשתמש במנגנון של GetHashCode בכדי למצוא איבר במהירות.

הדרך המרושלת לעשות זאת זה לאנוס Dictionary בשביל הצורך הזה:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Dictionary<string, bool> bandMembers =
    new Dictionary<string, bool>();
bandMembers["George"] = true;
bandMembers["Paul"] = true;
bandMembers["John"] = true;
bandMembers["Ringo"] = true;
// ...
if (bandMembers.ContainsKey("George"))
{
    // ...
}
if (bandMembers.ContainsKey("Gaga"))
{
    // ...
}

ContainsKey של Dictionary אכן עובד עם GetHashCode ולכן יספק תשובה באופן מהיר יותר, אך זה שימוש לא נכון בDictionary מאחר ואנחנו בכלל לא מתייחסים לValue.

לפני Framework 3.5 לא היה פתרון כל כך טוב בBCL והאלטרנטיבה הכי טובה הייתה להשתמש בSet של PowerCollections, או לממש בעצמנו מנגנון כזה.

בFramework 3.5 הוסיפו מחלקה בשם HashSet<T>, בnamespace System.Collections.Generic בSystem.Core.dll.

המחלקה בעצם מייצגת קבוצה מתמטית סופית, עליה ניתן לשאול אם איבר נמצא או לא.

היא משתמשת בGetHashCode כדי לענות על שאלה זו בצורה מהירה.

הדוגמה הקודמת תכתב כך:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
HashSet<string> bandMembers =
    new HashSet<string>();
bandMembers.Add("George");
bandMembers.Add("Paul");
bandMembers.Add("John");
bandMembers.Add("Ringo");
if (bandMembers.Contains("George"))
{
    // ...
}
if (bandMembers.Contains("Gaga"))
{
    // ...
}

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

יום טוב

שתף