Dictionary và Set

Dictionary và Set đều là bảng băm, và cả hai phụ thuộc hoàn toàn vào việc Hashable được cài đặt đúng. Làm sai thì chẳng có gì sập — hiệu năng lặng lẽ tụt từ O(1) xuống O(n), hoặc giá trị biến mất.

Bản hợp đồng

Hashable có đúng một quy tắc, và nó chỉ chạy theo một chiều:

Nếu hai giá trị bằng nhau thì chúng phải có cùng giá trị băm.

Chiều ngược lại không bắt buộc. Hai giá trị khác nhau có thể trùng mã băm — đó là va chạm, và bảng xử lý nó bằng cách so sánh bằng == trong cùng một ngăn.

Phá vỡ quy tắc theo chiều còn lại là thứ làm mất giá trị:

struct User: Hashable {
    let id: UUID
    var lastSeen: Date

    static func == (lhs: User, rhs: User) -> Bool {
        lhs.id == rhs.id                     // phép bằng bỏ qua lastSeen
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(id)
        hasher.combine(lastSeen)             // nhưng mã băm thì không — hỏng
    }
}

Hai user cùng id và khác lastSeen thì == với nhau, nhưng băm ra khác nhau. Chèn một cái vào một Set rồi tra cái kia thì không tìm thấy, vì lượt tra đi tới sai ngăn và không bao giờ chạm tới phép so sánh.

Việc băm được gieo hạt lại ở mỗi lần khởi chạy

Hasher được gieo hạt ngẫu nhiên ở mỗi lần tiến trình khởi động, nên các giá trị băm không ổn định qua các lần chạy. Có hai hệ quả:

Đừng bao giờ lưu lại một hashValue. Không lưu vào file, không vào cơ sở dữ liệu, không vào một khóa cache sống lâu hơn tiến trình. Ngày mai nó sẽ khác.

Thứ tự duyệt không ổn định. Một Dictionary hay Set duyệt theo thứ tự do hạt băm quyết định, nên cùng một đoạn code cho ra thứ tự khác ở lần chạy sau. Code có vẻ chạy đúng vì một dictionary tình cờ duyệt theo thứ tự bảng chữ cái rồi sẽ hỏng, và nó sẽ hỏng trong môi trường thật chứ không phải trong test.

for (key, value) in settings.sorted(by: { $0.key < $1.key }) { … }

Nếu thứ tự quan trọng, hãy sắp xếp tường minh. Nếu thứ tự quan trọng và là một phần của mô hình dữ liệu, hãy dùng một mảng các cặp hoặc một tập hợp có thứ tự.

Các thao tác dictionary đáng biết

Phép truy cập kèm giá trị mặc định dẹp đi phần lớn đoạn code vụng về quanh việc đếm và gom nhóm:

var counts: [String: Int] = [:]
for word in words {
    counts[word, default: 0] += 1
}

Dòng đó đọc và ghi qua cùng một phép truy cập, và vì nó dựa trên _modify nên nó không sao chép giá trị ra rồi lại vào — nó sửa tại chỗ.

Ba bộ khởi tạo lo được phần lớn phần còn lại:

Dictionary(grouping: users, by: \.city)             // [String: [User]]
Dictionary(uniqueKeysWithValues: pairs)             // sập khi có khóa trùng
Dictionary(pairs, uniquingKeysWith: { old, _ in old })   // giải quyết khóa trùng

uniqueKeysWithValues đáng được gọi tên: khi gặp khóa trùng, nó không trả về nil và cũng không ném lỗi, nó sập. Dựng một dictionary từ dữ liệu máy chủ bằng bộ khởi tạo đó là một cú sập đang chờ id trùng đầu tiên. Hãy dùng uniquingKeysWith: cho bất cứ dữ liệu nào không do chính bạn sinh ra.

merge và merging gộp hai dictionary với một quy tắc xử lý xung đột tường minh, và đó là hình dạng nên với tới thay cho một vòng lặp:

defaults.merging(overrides) { _, override in override }

Khi nào Set là câu trả lời đúng

Bản ba dòng: Set đúng khi bạn cần kiểm tra thành viên, tính duy nhất, hoặc đại số tập hợp; và sai khi bạn cần thứ tự hoặc cần phần tử lặp.

Trường hợp người ta hay bỏ sót là kiểm tra thành viên bên trong một vòng lặp:

// O(n × m)
let filtered = items.filter { blockedIDs.contains($0.id) }      // blockedIDs là một Array

// O(n)
let blocked = Set(blockedIDs)
let filtered = items.filter { blocked.contains($0.id) }

Array.contains là một lượt quét tuyến tính. Nằm trong một filter trên một nghìn phần tử, với một nghìn id bị chặn, đó là một triệu phép so sánh thay vì một nghìn lượt tra. Chuyển sang Set tốn một lượt duyệt và hoàn vốn ngay lập tức.

Các phương thức đại số tập hợp đáng thuộc tên, vì viết tay bằng vòng lặp thì dài hơn và chậm hơn:

current.subtracting(previous)      // đã thêm
previous.subtracting(current)      // đã bỏ
current.intersection(previous)     // không đổi
current.symmetricDifference(previous)

Cặp đầu tiên chính là toàn bộ một thuật toán so sánh khác biệt cho dữ liệu không có thứ tự, và đó là cách bạn tìm ra cần chèn gì và xóa gì mà không phải so từng phần tử của hai mảng.

Copy-on-write cũng áp dụng ở đây

Cả hai kiểu đều là kiểu giá trị bọc quanh một vùng đệm trên heap, đúng như chương về giá trị và tham chiếu đã mô tả. Truyền một dictionary lớn cho một hàm là sao chép một con trỏ; sửa một bản sao thì nhân đôi vùng đệm.

Cái giá riêng của dictionary là băm lại khi phình ra. Một dictionary lớn quá sức chứa sẽ cấp phát một vùng đệm lớn hơn rồi băm lại mọi khóa vào đó. Vì thế dựng một dictionary lớn trong một vòng lặp sẽ băm lại vài lần, và minimumCapacity tránh được điều đó:

var index = Dictionary<String, Item>(minimumCapacity: items.count)

Đáng làm khi kích thước đã biết trước và lớn. Không đáng làm trong các trường hợp khác — chiến lược cấp phát lại đã được khấu hao, và đây là một tối ưu vi mô ở khắp mọi nơi trừ đúng cái vòng lặp mà nó không phải vậy.