Hashable

Thuộc phần Lập trình hướng đối tượng trong hành trình Swift của Coddy. Bài học 40 trên 57.

Hashable cho phép lưu các giá trị trong Set hoặc dùng làm khóa của Dictionary. Giá trị băm là một con số được tính từ giá trị đó, dùng để tìm giá trị nhanh chóng. Các struct và enum có mọi thuộc tính đều là Hashable sẽ tự có khả năng này khi khai báo tuân thủ:

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

Đầu ra:

2
true

Các giá trị có thể băm thích hợp làm khóa từ điển, chẳng hạn để đếm số lần xuất hiện của các giá trị có cấu trúc:

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

Đầu ra:

Hashable được xây dựng dựa trên Equatable. Khi == chỉ so sánh một số thuộc tính, giá trị băm phải dùng chính những thuộc tính đó, thông qua hash(into:). Nếu không, hai giá trị bằng nhau có thể có giá trị băm khác nhau, khiến tập hợp lưu cả hai:

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)

Đầu ra:

Quy tắc cần nhớ: các giá trị bằng nhau phải có mã băm bằng nhau. Mã băm thay đổi giữa các lần chạy chương trình, vì vậy đừng bao giờ lưu trữ hoặc in chúng ra; chỉ dùng chúng thông qua tập hợp và từ điển.

// Giá trị bằng nhau -> mã băm bằng nhau (bắt buộc)
// Giá trị khác nhau -> mã băm thường khác nhau
func hash(into hasher: inout Hasher) {
    hasher.combine(id)          // Đúng những thuộc tính mà == so sánh
}

Thử thách

Dễ

Một rô-bốt trên lưới di chuyển từng bước một theo hướng U, D, L, R, bắt đầu từ (0, 0). Hãy tạo Position (x, y) tuân theo Hashable và hoàn thành explore(_:). Hàm này trả về ba dòng: visited 5 cells (số vị trí riêng biệt, tính cả điểm xuất phát), revisits 2 (số bước đi đến ô đã ghé thăm) và most visited (0, 0) x3 (ô được đi vào nhiều lần nhất, tính điểm xuất phát là một lần ghé thăm; nếu hòa, ô đạt số lần đó trước sẽ thắng).

Code được cung cấp đọc một dòng chứa các bước di chuyển và in ra từng dòng được trả về.

Đặt code của bạn trong Position.swift và Functions.swift. main.swift chứa code đầu vào/đầu ra được cung cấp và bạn không thể chỉnh sửa tệp này.

Tự làm thử

// Đoạn code đầu vào/đầu ra đã được cung cấp: giữ nguyên
var input: [String] = []
while let line = readLine() { input.append(line) }
for line in explore(input[0]) { print(line) }