Lập trình 22/09/2026 7 phút

Hash table O(1): phép màu tra cứu — và ba cách nó sụp đổ về O(n)

Map/dict cho tra cứu O(1) — nhanh bất kể dữ liệu lớn cỡ nào. Bài này đo thật trong go-lab: hashtable và map Go giữ ~1-21 ns dù N tăng 256 lần, trong khi quét slice tăng tuyến tính tới 32 µs. Nhưng O(1) chỉ là trung bình: hàm băm tệ (mọi key về một bucket) làm tra cứu chậm gấp 11.874 lần, và quên pre-size map khiến chèn chậm gấp đôi vì rehash.

Lập trình 22/09/2026 7 phút

BFS, DFS và cái giá của ma trận kề: vì sao duyệt đồ thị thưa bằng ma trận chậm hơn 344 lần

BFS và DFS cùng duyệt mọi đỉnh trong O(V+E) — khác nhau ở thứ tự thăm, không ở tốc độ. Nhưng cách BIỂU DIỄN đồ thị thì khác nhau một trời một vực. Bài này đo thật trong go-lab: trên đồ thị thưa 20.000 đỉnh, ma trận kề tốn 391 MB và duyệt chậm hơn danh sách kề 344 lần, trong khi danh sách chỉ dùng 1,68 MB. Vì sao, và khi nào ma trận mới đáng dùng.

Lập trình 22/09/2026 8 phút

Dijkstra với heap: vì sao đổi cách tìm đỉnh gần nhất biến 3,5 giây thành 17 mili giây

Dijkstra tìm đường đi ngắn nhất, nhưng tốc độ của nó phụ thuộc vào một chi tiết: tìm đỉnh gần nguồn nhất bằng cách nào. Bài này đo thật trong go-lab: bản quét mảng O(V²) mất 3,55 giây trên đồ thị thưa 50.000 đỉnh, còn bản dùng heap O((V+E)log V) chỉ 16,9 ms — nhanh hơn 210 lần, cùng kết quả. Nhưng trên đồ thị dày, bản mảng lại cạnh tranh.

Lập trình 22/09/2026 6 phút

Timing attack: so sánh token bằng == làm rò rỉ bí mật qua thời gian — và cách so constant-time

So sánh một token hay chữ ký bằng == trông vô hại, nhưng nó thoát sớm ở byte đầu tiên khác nhau — nên thời gian so sánh tiết lộ bạn đã đoán đúng bao nhiêu byte. Bài này đo thật trong Go: so sánh thoát sớm cho thời gian tuyến tính theo số byte khớp (từ 1.2ns khi khớp 0% lên 50.692ns khi khớp 100%), còn ConstantTimeCompare phẳng ~54.700ns bất kể khớp bao nhiêu. Về lý thuyết, kênh thời gian đó cho phép dò token từng byte.

Lập trình 22/09/2026 6 phút

Zero-copy serialization: đọc một field trong 0,25 nano giây, không cấp phát

JSON và Protobuf phải giải mã cả bản ghi thành struct trước khi đọc một field — lãng phí khi bạn chỉ cần vài field trong message lớn. Zero-copy (FlatBuffers, Cap'n Proto) đọc thẳng field từ buffer bằng offset, không giải mã, không cấp phát. Bài này đo thật bằng Go: đọc một trường mất 0,25 ns và 0 lần cấp phát, so với 1524 ns và 9 lần khi phải unmarshal cả bản ghi — nhanh hơn khoảng 6000 lần.

Lập trình 22/09/2026 6 phút

Nhóm bắt và thay thế: dùng regex để biến đổi chuỗi, không chỉ để tìm

Regex không chỉ tìm — nó trích và dựng lại. Bài này đo thật: nhóm (...) cắt '2026-09-22' thành ba phần, nhóm đặt tên (?P<nam>) đọc bằng tên, re.sub đổi 'yyyy-mm-dd' thành 'dd/mm/yyyy' bằng \3/\2/\1, sed đổi 'Nguyen Van A' thành 'Van A, Nguyen'. Và vì sao (?:...) không được đếm lại quan trọng: thêm một cặp () thừa làm \1 trong thay thế trỏ sai.