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