Hashable

חלק מהיחידה תכנות מונחה עצמים במסלול ה-Swift של Coddy. שיעור 40 מתוך 57.

Hashable מאפשר לאחסן ערכים ב-Set או להשתמש בהם כמפתחות של Dictionary. גיבוב הוא מספר שמחושב מתוך הערך ומשמש לאיתור מהיר שלו. מבנים ומניינים שכל המאפיינים שלהם הם Hashable מקבלים את האפשרות הזו באמצעות הצהרה על התאימות לפרוטוקול:

struct Point: Hashable {
    let x: Int, y: Int
}

var visited: Set<Point> = []
visited.insert(Point(x: 0, y: 0))
visited.insert(Point(x: 1, y: 0))
visited.insert(Point(x: 0, y: 0))
print(visited.count)
print(visited.contains(Point(x: 1, y: 0)))

פלט:

2
true

ערכים בני־גיבוב מתאימים כמפתחות במילון, למשל לספירת מופעים של ערכים מובנים:

struct Pair: Hashable {
    let from: String, to: String
}

let trips = [Pair(from: "A", to: "B"), Pair(from: "B", to: "C"), Pair(from: "A", to: "B")]
var counts: [Pair: Int] = [:]
for t in trips { counts[t, default: 0] += 1 }
print(counts[Pair(from: "A", to: "B")]!)

פלט:

Hashable מבוסס על Equatable. כש־== משווה רק חלק מהמאפיינים, הגיבוב חייב להשתמש באותם מאפיינים, והדבר נעשה באמצעות hash(into:). אחרת, שני ערכים שווים עלולים לקבל ערכי גיבוב שונים, וקבוצה תשמור את שניהם:

struct User: Hashable {
    let id: Int
    var name: String

    static func == (lhs: User, rhs: User) -> Bool { lhs.id == rhs.id }
    func hash(into hasher: inout Hasher) { hasher.combine(id) }
}

let users: Set<User> = [User(id: 1, name: "Ada"), User(id: 1, name: "Ada L."), User(id: 2, name: "Bo")]
print(users.count)

פלט:

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

// ערכים שווים -> גיבובים שווים (חובה)
// ערכים שונים -> בדרך כלל גיבובים שונים
func hash(into hasher: inout Hasher) {
    hasher.combine(id)          // בדיוק המאפיינים ש-== משווה
}

אתגר

קל

רובוט על גבי רשת נע צעד אחד בכל פעם בכיוונים U, D, L, R, החל מ־(0, 0). הפכו את Position (x, y) ל־Hashable והשלימו את explore(_:), שמחזירה שלוש שורות: visited 5 cells (מספר המיקומים הייחודיים, כולל נקודת ההתחלה), revisits 2 (צעדים שנחתו בתא שכבר ביקרו בו) ו־most visited (0, 0) x3 (התא שאליו נכנסו במספר הפעמים הרב ביותר, כאשר נקודת ההתחלה נחשבת לביקור אחד; התא הראשון שהגיע למספר הזה מנצח במקרה של שוויון).

הקוד שסופק קורא שורת צעדים אחת ומדפיס כל שורה שמוחזרת.

הקוד שלכם ייכתב ב־Position.swift וב־Functions.swift. הקובץ main.swift מכיל את קוד הקלט/פלט שסופק ואי אפשר לערוך אותו.

נסו בעצמכם

// קוד קלט/פלט שסופק: השאירו אותו כפי שהוא
var input: [String] = []
while let line = readLine() { input.append(line) }
for line in explore(input[0]) { print(line) }