Biết rồi, khổ lắm, nói mãi

Hôm nọ, nhân ngày Hà Nội ô nhiễm không khí thứ 2 thế giới, mình lôi C++ ra nghịch ngợm, mới phát hiện ra là, kiểu ADT Map được C++ implement bằng 2 cách, Hash table và Red-black tree. Ủa, sao lại lằng nhằng thế? Một ADT thì implement một kiểu mẹ nó đi, như Dictionary của Python ý, cho đời nó đơn giản.
Mồm thì đụ mẹ, nhưng trong đầu mình treo lủng lẳng câu hỏi “vì sao”. Hừm, vì sao C++ lại chọn cách tiếp cận phức tạp hơn Python? Tradeoff là gì? Đúng ra thì mình hoàn toàn có thể bỏ qua vụ này và để đầu óc thơ thẩn về mông, vú, những điều dân dã hơn. Hừm, nhưng mà:
Programmers know the benefits of everything and the tradeoffs of nothing.
Trích lời cụ Rich Hickey. Lời cụ như vả vào mồm mình. Hừm.
Okay, fine, challenge accepted cụ.

Challenge Accepted

Tự vấn lại bản thân xem đã biết những gì về Hashing, thì chợt nhận ra, 1.4 kilogram bã đậu trên cổ mình cứ mãi mông lũng giữa các thuật ngữ Hash Table, Hash Map và Hash Function, bla bla..
Và điều độc nhất mình gợi được về ADT (Abstract Data Type) này là:
def hash(x): return x % CONSTANT
Wao, quá là sâu sắc luôn.
Sau 5 năm ăn ngủ với backend, Assembly code chảy trong huyết quản, compiler chạy bên não trái, mê gái chạy bên não phải, mà giờ, điều duy nhất nói được về Hashing là cách implement kiểu trẻ con 6 tuổi cũng có thể hiểu được. Yeah. 😵‍💫
Thế là, mình mò lại Lecture 8 - Hashing của CS161.
cs161-stanford.github.io
Với ai chưa biết thì, CS161 là khóa Data Structures & Algorithms của Stanford. Theo mình đánh giá thì, giữa biển các khóa học rồi video trên Udemy hay YouTube về chủ đề này, CS161 là khóa duy nhất cố gắng truyền cho người học:
- (0) Culture nên có của người Kỹ sư: think - pair - share,
- (1) Theory,
- Và (2) Mindset,
- Chứ không phải (3) implementation.
Khi học những khóa DS&A khác, ngoài CS161, cảm nghĩ chung của mình:
- DS&A là một môn khó.
- Nó khó, không phải vì kiến thức cao siêu, mà vì mình không thể hiểu được, bằng cách nào, mà người ta nghĩ ra được những thuật toán đó.
- Mình muốn biết cách design thuật toán, để khi gặp một bài toán riêng biệt, có thể tự nghĩ ra cách giải của riêng mình, mà không cần đi nhờ AI.
Mông lung, là cảm giác duy nhất động lại.
CS161 giải ảo được sự mông lung đó.
(Đoạn này mình không được trả tiền affiliated đâu nhé.)

Hash Families

Quay trở lại với Hashing và Lecture 8 của CS161.
Review xong, não mình nhảy số ra 2 điều bất ngờ:
- Điều bất ngờ thứ 0, là khái niệm về Hash Families.
- Điều bất ngờ thứ 1, là mình nhận ra đây là lần thứ 2 mình bất ngờ vì điều số 0.
Hừm, đúng là đầu óc bã đậu, nước đổ lá khoai.
Xem nào, Hash Function thì anh em mình đều biết là gì rồi phải không, thì Hash Families là:
hash_families = [ hash_func_1, hash_func_2, .. ]
Sau đó, khi ta hash một key, sẽ là:
def hash(x): hash_f = choose_one_of(hash_families) return hash_f(x)
Vụ Hash Families, chẳng có YouTuber nào dạy mình cả.
Dù hay ho vậy, nhưng mà thực ra C++ và Python, chả cái nào áp dụng Hash Families cả. Hừm, sao lại thế nhờ?
Dựa trên mindset engineer thông thường, mình cho rằng, những người thiết kế 2 ngôn ngữ trên đã cân nhắc các tradeoff sau:
- Performance & Simplicity - Deterministic hash nhanh hơn, bởi vì nó tránh được overhead của việc Random Seed, hoặc những chi phí khác của việc thêm 1 bước nữa (Hash Families) vào Hashing.
- Predictability - Same input → same hash.
- Caching. Same key → same location.
- Debugging: Same run → same behavior.- --
Vậy giờ, giả sử là, ta chấp nhận mọi điểm xấu xí của Hash Families đi, và vẫn muốn đưa nó vào sử dụng, thì Hash Families cho mình những điểm đẹp gì?
- Hash Flooding Attack. Các chế chắc nhớ ra vụ Hash Collision nhờ?
Ở đoạn này, mình tiện tay bật chế độ Security mode cho 1.4 kilogram bã đậu. Attacker, nếu đoán được cách backend thực hiện hashing, rồi khai thác, thì sẽ làm cho Hash Table suy biến thành Linked List, tức từ O(1) thành O(n). Cũng hay.
Đào sâu một chút về cách Python implement Hash Table. Thì hóa ra Python có sử dụng tinh thần của Hash Families, bằng env PYTHONHASHSEED.
Thay đổi này đến từ version 3.3, cỡ năm 2012, khi lỗi CVE-2012-1150 được phát hiện: các hakers tạo ra hàng loạt string gây ra Hash Collision, nhằm tăng chi phí SEARCH của Hash Table từ O(1) lên O(n), gọi văn hoa là Denial of Service kiểu CPU Consumption, thế là các server chạy Python sập. Wao.
cve-details

access.redhat.com

Kết bài

Cô giáo cấp 2 của mình, hồi dạy văn nghị luận, bảo các con nên kết bài bằng một câu chốt sâu sắc, hoặc một lời khuyên chí tình. Mình thì, tự ngẫm bản thân là một thằng võ biền, suy nghĩ thì 9 phần nông cạn, 10 phần thô thiển, lại càng chẳng muốn đưa ra lời khuyên với người khác bao giờ.
Nhưng thôi mình cũng khiên cưỡng viết cái kết như này:
- Anh em nào có hứng thú học cách suy nghĩ của Engineer, về cách DS&A được tạo ra, thì hãy ngó qua khóa CS161. Không cần xem video đâu. Dài lắm, đọc slides là đủ rồi.
- Ai không hứng thú, thì thôi.
Hy vọng bài này cũng mua vui giúp bạn được một vài trống canh. Tạm biệt.