Bàn về Hash-Set trong Swift

HàPQ -

Có 2 vấn đề cần bàn luận ở đây, Hash Table và Set.

  • Hashtable phù hợp việc tìm kiếm với thời gian không đổi O(1)

Không biết cái O nó là gì thì quay lại học căn bản Time Complexity và nắm vững nó rồi mới tính tiếp.
https://en.wikipedia.org/wiki/Time_complexity

  • Set lưu trữ dữ liệu không trùng lắp.

Gộp 2 cái đó lại chúng ta có một cấu trúc dữ liệu phù hợp cho việc tìm kiếm mà tốn ít bộ nhớ hơn Dictionary (key-value).

Mặc định Set trong Swift đã là Hash-Set.
https://docs.swift.org/swift-book/LanguageGuide/CollectionTypes.html#ID484

Để kiểu dữ liệu có thể lưu trong Set, chúng ta cần cung cấp hàm băm (trả về Int) bằng cách implement protocol Hashable.

Một số bài toán có thể sử dụng Set.

  • Tạo Indexes (giống database) cho mảng dữ liệu (lookup)
  • Kiểm tra dữ liệu đã được sử dụng trước đó chưa (lookup)
  • So sánh hai bộ dữ liệu:
    isDisjoint(with:): kiểm tra 2 tập hợp hoàn toàn không có phần tử nào chung (không giao nhau)
    isStrictSuperset(of:): tập con nghiêm ngặt (tức là ngoại trừ trường hợp 2 tập giống nhau hoàn toàn)
    isSubset(of:): A là con của B nếu tất cả phần tử của A đều tìm thấy trong B. Theo định nghĩa thì A = B cũng chính là A con B
    isSuperset(of:): A đều chứa phần tử của B, trường hợp giống nhau vẫn là cha
    isStrictSuperset(of:): tập cha nghiêm ngặt ( là cha nhưng ngoại trừ trường hợp 2 tập giống nhau)

Và một số method khác để tạo ra set thứ 3 dựa vào 2 set ban đầu

Happy cheating!