Hashable

Część sekcji Programowanie obiektowe ścieżki Swift w Coddy. Lekcja 40 z 57.

Hashable pozwala przechowywać wartości w Set lub używać ich jako kluczy w Dictionary. Hash to liczba obliczana na podstawie wartości, używana do jej szybkiego wyszukiwania. Struktury i wyliczenia, których wszystkie właściwości są typu Hashable, uzyskują tę zgodność, gdy ją zadeklarujesz:

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)))

Wynik:

2
true

Wartości, które można haszować, dobrze sprawdzają się jako klucze słownika, na przykład do zliczania wystąpień wartości strukturalnych:

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")]!)

Wynik:

Hashable opiera się na Equatable. Gdy == porównuje tylko niektóre właściwości, skrót musi używać tych samych właściwości, co odbywa się w hash(into:). W przeciwnym razie dwie równe wartości mogłyby otrzymać różne skróty, a zbiór przechowywałby obie:

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)

Wynik:

Zasada do zapamiętania: równe wartości muszą mieć równe skróty. Wartości skrótów zmieniają się między uruchomieniami programu, więc nigdy ich nie zapisuj ani nie wyświetlaj; używaj ich wyłącznie za pośrednictwem zbiorów i słowników.

// równe wartości -> równe hashe (wymagane)
// różne wartości -> zwykle różne hashe
func hash(into hasher: inout Hasher) {
    hasher.combine(id)          // dokładnie te właściwości, które porównuje ==
}

Wyzwanie

Łatwy

Robot porusza się po siatce o U, D, L, R — za każdym razem o jedno pole, zaczynając od (0, 0). Zaimplementuj Position (x, y) jako Hashable i dokończ explore(_:), która zwraca trzy wiersze: visited 5 cells (liczbę różnych pozycji, wliczając pozycję początkową), revisits 2 (ruchy, które zakończyły się na już odwiedzonym polu) oraz most visited (0, 0) x3 (pole, na które robot wszedł najwięcej razy, licząc pozycję początkową jako jedną wizytę; w przypadku remisu wygrywa pierwsze pole, które osiągnęło tę liczbę).

Dostarczony kod odczytuje jeden wiersz z ruchami i wyświetla każdy zwrócony wiersz.

Twój kod umieść w plikach Position.swift i Functions.swift. main.swift zawiera dostarczony kod wejścia/wyjścia i nie można go edytować.

Spróbuj swoich sił

// Dostarczony kod wejścia/wyjścia: pozostaw go bez zmian
var input: [String] = []
while let line = readLine() { input.append(line) }
for line in explore(input[0]) { print(line) }