Thuật toán 2 — Cấu trúc dữ liệu nền tảng & ứng dụng

Vì sao "chọn đúng cấu trúc dữ liệu là nửa lời giải"?

Ở bài Độ phức tạp thuật toán chúng ta đã thấy: cùng một bài toán, một thuật toán O(n) và một thuật toán O(n²) có thể chênh nhau từ vài giây thành vài giờ khi dữ liệu đủ lớn. Nhưng có một sự thật ít được nói ra: phần lớn sự chênh lệch đó không đến từ việc bạn viết vòng lặp khéo hơn, mà đến từ việc bạn chọn đúng cấu trúc dữ liệu.

Một cấu trúc dữ liệu quyết định thao tác nào rẻ và thao tác nào đắt. Nếu công việc của bạn tra cứu nhiều thì hãy chọn cấu trúc tra cứu rẻ (hash map, O(1)); nếu bạn cần lấy phần tử ra theo đúng thứ tự vào thì hãy chọn queue; nếu bạn cần luôn lấy phần tử "ưu tiên nhất" thì hãy chọn heap. Sai cấu trúc, và bạn sẽ phải viết code phức tạp để bù lại điều mà lẽ ra công cụ đã cho bạn miễn phí.

Câu hỏi cốt lõi xuyên suốt bài này rất đơn giản: "Thao tác nào chạy nhiều nhất?" — trả lời được câu này là bạn đã chọn được cấu trúc.

Toàn bộ ví dụ dưới đây là minh hoạ bằng Python. Sandbox của khoá này là PostgreSQL, nên Python không chạy trực tiếp ở đây — hãy đọc code như bản thiết kế tư duy.

1. Ánh xạ tư duy sang kiểu Python

Trước khi đi vào chi tiết, hãy nhớ bảng ánh xạ này — nó biến kiến thức lý thuyết thành công cụ dùng được ngay:

Điểm mấu chốt: một list Python không phải mảng cố định của C — nó là dynamic array (mảng động), tự cấp phát lại bộ nhớ khi đầy. Còn dict/set mới là "vũ khí bí mật" giúp hạ độ phức tạp từ O(n²) xuống O(n) trong vô số bài toán dữ liệu thực tế.

2. Array / Dynamic array — list

list là cấu trúc bạn dùng nhiều nhất, và cũng là cấu trúc dễ dùng sai nhất về hiệu năng. Bản chất là một mảng con trỏ liên tục trong bộ nhớ, có dư chỗ trống ở cuối để append không phải cấp phát lại mỗi lần.

Bảng độ phức tạp thao tác:

Khi nào dùng list: khi bạn cần một dãy có thứ tự, truy cập theo vị trí, và chủ yếu thêm/bớt ở cuối. Đây là lựa chọn mặc định đúng đắn cho hầu hết dữ liệu tuần tự.

Bẫy kinh điển 1 — chèn/xoá đầu list: list.pop(0) là O(n) vì phải dịch mọi phần tử còn lại lên một vị trí. Nếu bạn cần một hàng đợi (lấy ra ở đầu, thêm vào ở cuối), đừng dùng list — dùng deque (mục 5).

Bẫy kinh điển 2 — dùng in trên list lớn: x in my_list là O(n). Trong một vòng lặp, bạn vô tình tạo ra O(n²). Đây chính là mẫu chống chỉ định mà bài Độ phức tạp cảnh báo — và cách sửa gần như luôn là "đổi list kiểm tra thành set".

# (minh hoạ) O(n²) ẩn: kiểm tra 'in' trên list trong vòng lặp
known = load_known_ids()            # list 1 triệu phần tử
dups = [x for x in incoming if x in known]   # mỗi 'in' quét cả list → O(n*m)

# Cách sửa: đổi 'known' sang set → mỗi kiểm tra O(1) trung bình
known = set(load_known_ids())
dups = [x for x in incoming if x in known]   # O(n + m)

3. Hash map (dict) & set — trái tim của xử lý dữ liệu

Nếu chỉ được nhớ một cấu trúc dữ liệu, hãy nhớ hash map. Nó là công cụ mạnh nhất để biến các bài toán "tìm/khớp/đếm" từ chậm thành nhanh.

Vì sao lookup lại là O(1)?

dict và set được cài đặt bằng bảng băm (hash table). Ý tưởng: thay vì quét tuần tự để tìm key, ta dùng một hàm băm hash(key) biến key thành một số nguyên, rồi dùng số đó để tính ra vị trí (bucket/slot) trong một mảng nội bộ. Việc "nhảy thẳng" tới đúng slot làm cho tra cứu chỉ tốn thời gian hằng số trung bình, không phụ thuộc kích thước bảng.

Vấn đề duy nhất là va chạm (collision): hai key khác nhau có thể ánh xạ về cùng một slot. CPython xử lý bằng open addressing (địa chỉ mở): nếu slot đã bận, nó dò sang một slot khác theo một công thức thăm dò giả ngẫu nhiên (probing) cho tới khi tìm được chỗ trống. Để giữ tra cứu nhanh, bảng được nới rộng (resize) khi tỷ lệ lấp đầy (load factor) vượt ngưỡng — CPython giữ dưới khoảng 2/3 — nên số lần va chạm trung bình luôn nhỏ.

Vì cơ chế này dựa trên hash(key), mọi key của dict/phần tử của set phải hashable — nghĩa là bất biến. Đây là lý do tuple làm key được, còn list thì không (TypeError: unhashable type: 'list').

Ba ứng dụng "ăn tiền" của hash map

(a) Dedup — loại trùng bằng set. Đưa dữ liệu vào set là cách O(n) để loại phần tử trùng, thay vì so từng cặp O(n²).

# (minh hoạ) dedup danh sách mã giao dịch, giữ tính duy nhất
raw_ids = ["TX1", "TX2", "TX1", "TX3", "TX2"]
unique_ids = set(raw_ids)          # {'TX1', 'TX2', 'TX3'} — O(n)

# Nếu cần giữ nguyên thứ tự xuất hiện lần đầu:
seen = set()
deduped = []
for tid in raw_ids:
    if tid not in seen:            # kiểm tra thành viên O(1) trung bình
        seen.add(tid)
        deduped.append(tid)

(b) Đếm tần suất — Counter. Đếm số lần xuất hiện là mẫu quá phổ biến, nên thư viện chuẩn có sẵn collections.Counter.

# (minh hoạ) đếm số giao dịch theo từng khách hàng
from collections import Counter
cust_ids = ["C01", "C02", "C01", "C01", "C03", "C02"]
freq = Counter(cust_ids)           # Counter({'C01': 3, 'C02': 2, 'C03': 1})
freq.most_common(2)                # [('C01', 3), ('C02', 2)] — top KH giao dịch nhiều

(c) Lookup / join trong bộ nhớ — thay O(n²) bằng O(n). Đây là kỹ thuật nền tảng của "hash join". Muốn ghép hai tập dữ liệu theo key, đừng lồng hai vòng lặp; hãy đưa một tập vào dict trước (index), rồi duyệt tập kia và tra cứu O(1). Đây chính là bản chất của đối soát (reconciliation) đề cập trong bài Độ phức tạp.

# (minh hoạ) đối soát: ghép giao dịch với thông tin khách hàng
customers = {"C01": "Nguyen Van A", "C02": "Tran Thi B"}   # dựng index 1 lần: O(n)
txns = [("TX1", "C01"), ("TX2", "C99"), ("TX3", "C02")]

for tx_id, cid in txns:            # duyệt m giao dịch
    name = customers.get(cid)      # tra cứu O(1) trung bình
    if name is None:
        print(f"{tx_id}: KH {cid} KHÔNG tồn tại — nghi vấn cần soát")
    else:
        print(f"{tx_id}: {name}")
# Tổng: O(n + m) thay vì O(n * m) nếu quét list

Ngoài ra, dict còn là nền của cache / memoization: lưu kết quả tính toán tốn kém theo key để lần sau tra cứu ngay (functools.lru_cache chính là một dict có giới hạn kích thước bên dưới).

Bẫy với hash map:

• Key phải hashable & bất biến. Đừng dùng list làm key; dùng tuple.
• Thứ tự: từ Python 3.7, dict giữ thứ tự chèn — nhưng set thì không đảm bảo thứ tự. Đừng dựa vào thứ tự của set.
• Bộ nhớ: hash table đánh đổi RAM lấy tốc độ (phải giữ bảng thưa để ít va chạm). Với dữ liệu rất lớn, chi phí bộ nhớ của một dict/set có thể đáng kể.
• Hash không ổn định giữa các lần chạy với một số kiểu (như str, do hash randomization vì lý do bảo mật). Đừng dựa vào giá trị hash() cụ thể để lưu ra ngoài.

4. Stack (LIFO) — vào sau, ra trước

Stack tuân theo nguyên tắc LIFO (Last In, First Out): phần tử vào sau cùng được lấy ra đầu tiên — như chồng đĩa. Trong Python, chỉ cần một list với append() (push) và pop() (pop) — cả hai đều O(1).

Stack tự nhiên xuất hiện ở mọi nơi có "quay lui":

• Undo / redo: mỗi hành động đẩy vào stack; undo là pop hành động gần nhất.
• Duyệt sâu (DFS): thăm đồ thị/cây bằng cách đẩy các nút con vào stack.
• Kiểm tra ngoặc / biểu thức: mỗi ngoặc mở push vào, mỗi ngoặc đóng pop ra và kiểm tra khớp.
• Backtracking: thử một nhánh, nếu sai thì "quay lui" — chính là pop.
• Call stack: bản thân lời gọi hàm của Python là một stack (đệ quy quá sâu → RecursionError).

# (minh hoạ) kiểm tra ngoặc cân bằng bằng stack
def is_balanced(expr: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in expr:
        if ch in "([{":
            stack.append(ch)              # push
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:  # pop & so khớp
                return False
    return not stack                      # rỗng = cân bằng

is_balanced("(a[b]{c})")   # True
is_balanced("(a]")          # False

5. Queue (FIFO) & deque — vào trước, ra trước

Queue tuân theo FIFO (First In, First Out): ai vào trước ra trước — như hàng người xếp hàng. Đừng dùng list cho queue: list.pop(0) là O(n). Hãy dùng collections.deque, cấu trúc double-ended queue cho append và pop ở cả hai đầu đều O(1).

# (minh hoạ) hàng đợi xử lý job/message
from collections import deque
queue = deque()
queue.append("job1")        # đẩy vào cuối
queue.append("job2")
job = queue.popleft()       # lấy ra ở đầu — O(1), đúng thứ tự FIFO

Queue là mô hình tư duy của hàng đợi xử lý trong hệ thống thật: một producer đẩy message vào, một consumer lấy ra xử lý. Đây chính là ý tưởng đằng sau các hàng đợi phân tán như Kafka hay RabbitMQ — chỉ khác là chúng bền vững và chạy qua mạng. Một điểm hữu ích: trong CPython, deque.append() và deque.popleft() là thread-safe, nên deque là lựa chọn gọn cho mẫu producer-consumer đơn giản trong một tiến trình.

deque còn là công cụ chuẩn cho hai thuật toán quan trọng:

• Duyệt rộng (BFS): thăm đồ thị theo lớp, dùng queue để giữ thứ tự các nút chờ thăm.
• Sliding window (cửa sổ trượt): giữ một "cửa sổ" N phần tử gần nhất, thêm phần tử mới vào một đầu và bỏ phần tử cũ ở đầu kia — cả hai O(1). Đặc biệt, deque(maxlen=N) tự động đẩy phần tử cũ ra khi vượt quá N, biến nó thành bộ đệm cửa sổ trượt hoàn hảo.

# (minh hoạ) trung bình trượt trên 3 giá trị gần nhất
from collections import deque
window = deque(maxlen=3)
for amount in [100, 200, 300, 400]:
    window.append(amount)              # tự loại phần tử cũ khi đầy
    print(list(window), sum(window) / len(window))
# [100] 100.0 / [100,200] 150.0 / [100,200,300] 200.0 / [200,300,400] 300.0

Lưu ý về deque: truy cập theo chỉ số ở giữa deque là O(n) (không như list). Deque chỉ nhanh ở hai đầu — dùng đúng chỗ.

6. Linked list — nền tảng nên hiểu, hiếm khi tự viết trong Python

Linked list là chuỗi các nút, mỗi nút chứa dữ liệu và một con trỏ tới nút kế tiếp. Ưu điểm lý thuyết: chèn/xoá ở một vị trí đã biết là O(1) (chỉ nối lại con trỏ, không phải dịch mảng). Nhược điểm: không truy cập được theo chỉ số trong O(1) — muốn tới phần tử thứ i phải đi lần lượt O(i); và mỗi nút tốn thêm bộ nhớ cho con trỏ, lại nằm rải rác trong RAM nên kém thân thiện với cache CPU.

Trong Python thực tế bạn hiếm khi tự viết linked list: list (dynamic array) đã đủ tốt cho phần lớn nhu cầu, và deque (được cài bằng doubly linked list các block) đã lo phần thêm/bớt hai đầu O(1). Nhưng khái niệm này là nền tảng để hiểu deque, LRU cache, và nhiều cấu trúc nâng cao — nên đáng để nắm.

Array vs linked list, gọn lại: cần truy cập theo vị trí và duyệt tuần tự nhanh → array; cần chèn/xoá liên tục ở hai đầu → deque. Trong Python, gần như luôn là một trong hai cái này, chứ không phải linked list tự viết.

7. Priority queue / heap — nhắc trước

Có một họ bài toán mà FIFO/LIFO không giải được: "luôn lấy ra phần tử ưu tiên nhất" (nhỏ nhất, khẩn nhất, điểm rủi ro cao nhất). Cấu trúc cho việc này là heap — Python có heapq thao tác trên một list bình thường, cho lấy phần tử min trong O(log n). Ứng dụng: top-N, lập lịch theo ưu tiên, thuật toán Dijkstra. Chi tiết đầy đủ ở bài Trees & heaps.

8. Chọn cấu trúc theo thao tác — bảng quyết định

Đây là bảng bạn nên "in ra dán màn hình". Trả lời câu "thao tác nào chạy nhiều nhất?" rồi tra bảng:

Nguyên tắc vàng: tối ưu cho thao tác chạy trong vòng lặp nóng, chấp nhận thao tác hiếm chậm hơn. Ví dụ nếu bạn tra cứu một triệu lần nhưng chỉ dựng bảng một lần, hãy chọn dict — dù dựng bảng có tốn RAM.

Use case thực tế: giám sát giao dịch

Ghép ba cấu trúc trên vào một luồng xử lý giao dịch ngân hàng — mỗi cấu trúc lo một nhiệm vụ.

1) Dedup giao dịch trùng (set). Message từ hàng đợi có thể bị gửi lặp (at-least-once delivery). Một set các transaction_id đã thấy giúp bỏ trùng trong O(1)/giao dịch.

# (minh hoạ) chống xử lý lặp một giao dịch
seen_txn = set()
def process_once(txn_id, payload):
    if txn_id in seen_txn:          # O(1) trung bình
        return "duplicate — bỏ qua"
    seen_txn.add(txn_id)
    return handle(payload)

2) Đếm giao dịch theo khách (Counter). Đếm số giao dịch mỗi khách trong ngày để phát hiện tần suất bất thường.

from collections import Counter
per_customer = Counter()
for txn in today_txns:
    per_customer[txn["cust_id"]] += 1
suspects = [c for c, n in per_customer.items() if n > 50]   # nghi vấn tần suất cao

3) Sliding window velocity (deque). "Velocity check" là mẫu cốt lõi trong giám sát giao dịch AML: với mỗi khách, giữ mốc thời gian các giao dịch trong cửa sổ (ví dụ 60 giây); nếu số giao dịch trong cửa sổ vượt ngưỡng → cảnh báo. Deque cho phép "trượt" cửa sổ trong O(1): thêm giao dịch mới vào cuối, bỏ các mốc quá cũ ở đầu.

# (minh hoạ) velocity: >5 giao dịch trong 60 giây của cùng một khách
from collections import defaultdict, deque
windows = defaultdict(deque)          # cust_id -> deque[timestamp]
WINDOW, LIMIT = 60, 5

def check_velocity(cust_id, ts):
    dq = windows[cust_id]
    dq.append(ts)                     # thêm giao dịch mới — O(1)
    while dq and ts - dq[0] > WINDOW: # bỏ mốc đã ra khỏi cửa sổ — O(1)/lần
        dq.popleft()
    return len(dq) > LIMIT            # True = cảnh báo velocity

Lưu ý ở đây defaultdict(deque) gọn hơn hẳn: không cần kiểm tra "khách này đã có deque chưa" — truy cập key mới sẽ tự tạo một deque rỗng.

Khi khối lượng phân tích lớn và cần chạy theo lô trên bảng, các phép "đếm theo nhóm / cửa sổ trượt" này thường được đẩy sang pandas (groupby, rolling) hoặc SQL; còn khi xử lý theo luồng thời gian thực từng giao dịch một, các cấu trúc thuần Python ở trên là công cụ tự nhiên.

Cấu trúc Python chuyên dụng: collections

Module collections gói sẵn những biến thể mà bạn nên biết để không phải phát minh lại:

• defaultdict(factory) — dict tự tạo giá trị mặc định khi truy cập key mới. Tránh mẫu if key not in d: d[key] = [] lặp đi lặp lại. Rất hợp cho gom nhóm (defaultdict(list)) và bộ đếm (defaultdict(int)).
• Counter — dict chuyên đếm, có most_common(n), cộng/trừ được như multiset.
• deque — hàng đợi hai đầu O(1), hỗ trợ maxlen cho cửa sổ trượt.
• OrderedDict — dict nhớ thứ tự chèn. Từ Python 3.7 dict thường đã giữ thứ tự chèn, nên OrderedDict chủ yếu còn dùng khi cần các thao tác đặc thù về thứ tự (như move_to_end, hữu ích khi tự cài LRU cache).

Ghi nhớ

• Chọn cấu trúc = chọn thao tác nào rẻ. Luôn hỏi trước: "thao tác nào chạy nhiều nhất?"
• list cho dãy có thứ tự, truy cập theo chỉ số, thêm/bớt ở cuối. Tránh in và pop(0) trong vòng lặp — đó là O(n²) ẩn.
• set để dedup và kiểm tra thành viên O(1); dict/Counter để tra cứu, join trong bộ nhớ và đếm tần suất — đây là cách chuẩn để hạ O(n²) xuống O(n).
• Stack (list) cho LIFO: undo, DFS, kiểm tra ngoặc, backtracking. Queue (deque) cho FIFO: job queue, BFS.
• deque nhanh ở hai đầu (O(1)), chậm ở giữa; deque(maxlen=N) là bộ đệm cửa sổ trượt hoàn hảo cho velocity check.
• Hash map trả giá bằng RAM để mua tốc độ, và key phải hashable/bất biến. Đừng dựa vào thứ tự của set.
• Linked list hiếm khi tự viết trong Python — hiểu khái niệm là đủ, để dùng tốt deque và các cấu trúc nâng cao.
• Đọc tiếp: Sorting & searching để thấy vì sao dữ liệu đã sắp xếp mở ra thuật toán tra cứu nhanh hơn, và Trees & heaps cho priority queue.