Cấu trúc dữ liệu Python — List, Tuple, Set, Dict & Beyond Core

Hình dung bạn đang xây một hệ thống xử lý đơn hàng cho sàn thương mại điện tử. Mỗi giây có hàng nghìn request đổ về: kiểm tra sản phẩm tồn kho, lọc đơn trùng, nhóm đơn theo khu vực giao hàng, đếm số lượt mua theo danh mục. Bạn chọn list cho tất cả — và sau hai tuần, response time từ 50ms nhảy lên 2 giây khi database có 500K sản phẩm. Lý do? product_id in list_500k là O(n), trong khi product_id in set_500k là O(1).

Chọn sai cấu trúc dữ liệu không phải lỗi cú pháp — nó là lỗi kiến trúc. Code vẫn chạy, test vẫn pass, nhưng production sẽ phạt bạn bằng latency và memory. Bài này đi sâu vào từng cấu trúc dữ liệu built-in của Python: khi nào dùng gì, tại sao, và CPython triển khai chúng như thế nào bên dưới.

Fast win ngay bây giờ: nếu bạn đang dùng if x in my_list với list lớn hơn vài trăm phần tử, hãy chuyển sang set. Chỉ một dòng thay đổi, nhưng tốc độ tìm kiếm tăng hàng trăm lần.

Bức tranh tư duy

Hãy tưởng tượng bạn quản lý một nhà kho lớn ở khu công nghiệp.

List là một dãy kệ đánh số thứ tự. Bạn biết chính xác món hàng nằm ở vị trí nào (truy cập theo index cực nhanh), thêm hàng vào cuối dãy dễ dàng. Nhưng muốn chèn hàng vào giữa? Phải dịch tất cả các thùng phía sau sang một ô — tốn công O(n). Muốn tìm một món hàng cụ thể mà không biết vị trí? Phải đi dọc từng kệ — lại O(n).

Dict là hệ thống kệ có bảng tra cứu (hash table). Mỗi món hàng có mã vạch riêng. Bạn quét mã, bảng tra cứu chỉ thẳng đến vị trí chính xác — O(1). Đổi lại, bảng tra cứu chiếm thêm bộ nhớ, và mã vạch phải là duy nhất, bất biến (hashable).

Set là kệ kiểm tra "có/không" — như danh sách đen IP bị chặn. Không cần biết vị trí, chỉ cần trả lời nhanh: "món này có trong kho không?". Nhanh như dict nhưng không lưu giá trị, chỉ lưu khóa.

Tuple là thùng hàng đã niêm phong. Một khi đóng gói xong, không ai được mở ra sửa. Chính vì bất biến nên tuple nhẹ hơn list, và có thể dùng làm mã vạch (dict key) — thứ mà list không làm được.

Nguyên tắc chọn kho: dữ liệu thay đổi → list, dữ liệu cố định → tuple, tra cứu nhanh theo khóa → dict, kiểm tra tồn tại → set. Phần còn lại của bài sẽ giải thích tại sao.

Cốt lõi kỹ thuật

Tổng quan & Bảng so sánh

Đặc điểm	`list`	`tuple`	`set`	`dict`
Có thứ tự (ordered)	✅	✅	❌	✅ (3.7+)
Thay đổi được (mutable)	✅	❌	✅	✅
Cho phép trùng lặp	✅	✅	❌	Key: ❌
Truy cập theo index	✅ O(1)	✅ O(1)	❌	❌
Kiểm tra `in`	O(n)	O(n)	O(1)	O(1)
Hashable (làm key)	❌	✅	❌	❌
Memory overhead (empty)	56 B	40 B	216 B	64 B

List — Mảng động

List là cấu trúc mặc định khi bạn cần một tập hợp có thứ tự và có thể thay đổi. Bên dưới, CPython triển khai list như một mảng con trỏ (array of pointers) — chi tiết ở phần Under the Hood.

python

# Khởi tạo và thao tác cơ bản
orders: list[str] = ["ORD-001", "ORD-002", "ORD-003"]
orders.append("ORD-004")          # O(1) amortized — thêm cuối
orders.insert(0, "ORD-000")       # O(n) — phải dịch toàn bộ
removed = orders.pop()             # O(1) — xóa cuối
removed_at = orders.pop(1)         # O(n) — xóa giữa, dịch phần tử

# List comprehension — cách Pythonic để biến đổi dữ liệu
prices: list[float] = [100.0, 250.5, 89.9, 310.0]
discounted: list[float] = [p * 0.9 for p in prices if p > 100]

Bảng complexity — List:

Operation	Average	Amortized	Ghi chú
`lst[i]`	O(1)	—	Truy cập theo index
`lst.append(x)`	O(1)	O(1)	Thỉnh thoảng resize
`lst.insert(i, x)`	O(n)	—	Dịch phần tử phía sau
`lst.pop()`	O(1)	—	Xóa cuối
`lst.pop(i)`	O(n)	—	Dịch phần tử
`x in lst`	O(n)	—	Duyệt tuyến tính
`lst.sort()`	O(n log n)	—	Timsort
`lst[i:j]`	O(k)	—	k = j − i
`len(lst)`	O(1)	—	Giá trị cached

Tuple — Bản ghi bất biến

Tuple không chỉ là "list không sửa được". Tuple truyền đạt ý nghĩa ngữ nghĩa: dữ liệu này là một bản ghi cố định, như tọa độ (lat, lng) hay kết quả trả về (status, payload).

python

# Tuple là bản ghi — mỗi vị trí có ý nghĩa
HCM_COORDS: tuple[float, float] = (10.762622, 106.660172)

# Hashable → dùng làm dict key hoặc set element
visited: set[tuple[int, int]] = {(0, 0), (1, 2), (3, 4)}
cache: dict[tuple[str, int], str] = {}
cache[("user_profile", 42)] = '{"name": "Minh"}'

# Unpacking — cách trả về nhiều giá trị
def divide(a: int, b: int) -> tuple[int, int]:
    """Trả về (thương, dư)."""
    return divmod(a, b)

quotient, remainder = divide(17, 5)  # quotient=3, remainder=2

Tuple nhỏ (1–5 phần tử) được CPython cache và tái sử dụng, nên tạo tuple nhanh hơn tạo list tương đương.

Set — Tập hợp duy nhất

Set tối ưu cho hai thao tác: kiểm tra tồn tại O(1) và phép toán tập hợp (hợp, giao, hiệu).

python

# Kiểm tra tồn tại — use case phổ biến nhất
blocked_ips: set[str] = {"192.168.1.100", "10.0.0.55", "172.16.0.99"}

def is_blocked(ip: str) -> bool:
    return ip in blocked_ips  # O(1), không phụ thuộc kích thước set

# Loại bỏ trùng lặp nhưng giữ thứ tự (Python 3.7+)
raw_ids: list[int] = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
unique_ids: list[int] = list(dict.fromkeys(raw_ids))
# [3, 1, 4, 5, 9, 2, 6] — giữ nguyên thứ tự xuất hiện đầu tiên

# Phép toán tập hợp — mạnh mẽ trong phân quyền
admins: set[str] = {"minh", "lan"}
editors: set[str] = {"lan", "duc", "hoa"}
viewers: set[str] = {"minh", "lan", "duc", "hoa", "tuan"}

can_publish: set[str] = admins | editors          # Hợp
shared_roles: set[str] = admins & editors          # Giao: {"lan"}
admin_only: set[str] = admins - editors            # Hiệu: {"minh"}
exclusive: set[str] = admins ^ editors             # Đối xứng: {"minh", "duc", "hoa"}

Bảng complexity — Set:

Operation	Average	Worst	Ghi chú
`x in s`	O(1)	O(n)	Hash collision (cực hiếm)
`s.add(x)`	O(1)	O(n)	Có thể resize
`s.remove(x)`	O(1)	O(n)	KeyError nếu không tồn tại
`s.discard(x)`	O(1)	O(n)	Im lặng nếu không tồn tại
`s \| t`	O(len(s) + len(t))	—	Union
`s & t`	O(min(len(s), len(t)))	—	Intersection
`s - t`	O(len(s))	—	Difference

Dict — Bảng băm

Dict là cấu trúc dữ liệu mạnh nhất và được dùng nhiều nhất trong Python. Từ Python 3.7, dict chính thức giữ thứ tự chèn.

python

# Truy cập an toàn — luôn dùng .get() thay vì indexing trực tiếp
config: dict[str, str] = {"host": "0.0.0.0", "port": "8080"}
db_host: str = config.get("db_host", "localhost")  # Trả về default nếu thiếu key

# Dict comprehension — biến đổi dữ liệu
raw_prices: dict[str, float] = {"apple": 25000, "banana": 15000, "grape": 80000}
vat_prices: dict[str, float] = {k: v * 1.1 for k, v in raw_prices.items()}

# Merge dict (Python 3.9+) — gộp config
defaults: dict[str, str] = {"theme": "dark", "lang": "vi", "debug": "false"}
overrides: dict[str, str] = {"theme": "light", "debug": "true"}
final_config: dict[str, str] = defaults | overrides
# {"theme": "light", "lang": "vi", "debug": "true"}

# setdefault — gom nhóm trong một lần duyệt
orders_by_region: dict[str, list[str]] = {}
for order_id, region in [("O1", "HCM"), ("O2", "HN"), ("O3", "HCM")]:
    orders_by_region.setdefault(region, []).append(order_id)
# {"HCM": ["O1", "O3"], "HN": ["O2"]}

Bảng complexity — Dict:

Operation	Average	Worst	Ghi chú
`d[key]`	O(1)	O(n)	Hash collision
`d[key] = val`	O(1)	O(n)	Có thể resize
`key in d`	O(1)	O(n)	Hash lookup
`d.get(key)`	O(1)	O(n)	Không raise KeyError
`del d[key]`	O(1)	O(n)	Hash collision
`d.keys() / .values() / .items()`	O(1)	O(1)	Trả về view object
`len(d)`	O(1)	—	Giá trị cached

⚠️ Worst case O(n) của hash-based structures

Worst case O(n) xảy ra khi tất cả key hash vào cùng một slot (hash collision hàng loạt). Với hash function mặc định của CPython, xác suất này gần như bằng không trong thực tế. Hãy luôn tính theo average case O(1).

collections.deque — Hàng đợi hai đầu

list.pop(0) là O(n) vì phải dịch toàn bộ mảng. Nếu bạn cần hàng đợi (queue) hoặc cửa sổ trượt (sliding window), hãy dùng deque.

python

from collections import deque

# Sliding window — giữ 5 giá trị gần nhất
recent_latencies: deque[float] = deque(maxlen=5)
for latency in [12.1, 15.3, 9.8, 22.0, 11.5, 14.2, 8.9]:
    recent_latencies.append(latency)
# deque([22.0, 11.5, 14.2, 8.9], maxlen=5) — tự động loại bỏ cũ nhất

avg_latency: float = sum(recent_latencies) / len(recent_latencies)

# BFS — deque là lựa chọn chuẩn
def bfs(graph: dict[str, list[str]], start: str) -> list[str]:
    visited: list[str] = []
    queue: deque[str] = deque([start])
    seen: set[str] = {start}
    while queue:
        node = queue.popleft()  # O(1), không phải O(n) như list.pop(0)
        visited.append(node)
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                queue.append(neighbor)
    return visited

Operation	`list`	`deque`
`append(x)` (cuối)	O(1)	O(1)
`appendleft(x)` (đầu)	O(n)	O(1)
`pop()` (cuối)	O(1)	O(1)
`popleft()` (đầu)	O(n)	O(1)
`x[i]` (index)	O(1)	O(n)

Đánh đổi rõ ràng: deque nhanh ở hai đầu nhưng chậm khi truy cập ngẫu nhiên theo index.

collections.defaultdict — Dict tự khởi tạo

defaultdict loại bỏ pattern lặp đi lặp lại "kiểm tra key → khởi tạo → gán".

python

from collections import defaultdict

# Nhóm đơn hàng theo trạng thái
orders: list[tuple[str, str]] = [
    ("ORD-01", "pending"), ("ORD-02", "shipped"),
    ("ORD-03", "pending"), ("ORD-04", "delivered"),
    ("ORD-05", "shipped"),
]

by_status: defaultdict[str, list[str]] = defaultdict(list)
for order_id, status in orders:
    by_status[status].append(order_id)
# defaultdict(<class 'list'>, {
#     'pending': ['ORD-01', 'ORD-03'],
#     'shipped': ['ORD-02', 'ORD-05'],
#     'delivered': ['ORD-04']
# })

# Đếm tần suất — cách thủ công
word_count: defaultdict[str, int] = defaultdict(int)
for word in "the quick brown fox jumps over the lazy dog".split():
    word_count[word] += 1  # int() trả về 0 khi key chưa tồn tại

collections.Counter — Đếm tần suất chuyên dụng

Counter là defaultdict(int) được nâng cấp với các phương thức đếm mạnh mẽ.

python

from collections import Counter

# Phân tích log: đếm HTTP status codes
status_codes: list[int] = [200, 200, 404, 200, 500, 404, 200, 301, 500]
code_counts: Counter[int] = Counter(status_codes)
# Counter({200: 4, 404: 2, 500: 2, 301: 1})

# Top N — cực kỳ hữu ích cho analytics
top_2: list[tuple[int, int]] = code_counts.most_common(2)
# [(200, 4), (404, 2)]

# Cộng/trừ Counter — so sánh hai khoảng thời gian
morning: Counter[str] = Counter({"login": 150, "purchase": 30, "error": 5})
afternoon: Counter[str] = Counter({"login": 200, "purchase": 45, "error": 12})
total: Counter[str] = morning + afternoon
# Counter({'login': 350, 'purchase': 75, 'error': 17})

diff: Counter[str] = afternoon - morning
# Counter({'login': 50, 'purchase': 15, 'error': 7}) — chỉ giữ giá trị dương

typing.NamedTuple — Tuple có tên trường

Khi tuple thường quá mơ hồ (phần tử thứ 0 là gì?), NamedTuple cho bạn tên trường rõ ràng với chi phí memory gần như bằng tuple.

python

from typing import NamedTuple

class Coordinate(NamedTuple):
    lat: float
    lng: float
    label: str = ""

hcm = Coordinate(lat=10.7626, lng=106.6601, label="Ho Chi Minh City")
hanoi = Coordinate(lat=21.0285, lng=105.8542, label="Ha Noi")

# Truy cập theo tên — rõ ràng hơn hcm[0]
print(hcm.lat)    # 10.7626
print(hcm.label)  # "Ho Chi Minh City"

# Vẫn là tuple — hashable, iterable, unpacking
lat, lng, _ = hcm
coords_set: set[Coordinate] = {hcm, hanoi}

So sánh nhanh: NamedTuple nhẹ hơn dataclass (không có __dict__), nhưng dataclass linh hoạt hơn khi cần mutable fields hay methods phức tạp. Dùng NamedTuple khi dữ liệu thực sự là bản ghi bất biến.

Thực chiến

Scenario 1 — Xây lớp cache đơn giản với dict và TTL

Hệ thống API gateway cần cache response để giảm tải database. Yêu cầu: lookup O(1), tự hết hạn sau N giây, giới hạn kích thước cache.

python

import time
from collections import OrderedDict
from typing import Any

class LRUCache:
    """LRU Cache với TTL — dùng OrderedDict để đảm bảo eviction order."""

    def __init__(self, max_size: int = 1000, ttl_seconds: float = 300.0) -> None:
        self._store: OrderedDict[str, tuple[Any, float]] = OrderedDict()
        self._max_size = max_size
        self._ttl = ttl_seconds

    def get(self, key: str) -> Any | None:
        if key not in self._store:
            return None
        value, created_at = self._store[key]
        if time.monotonic() - created_at > self._ttl:
            del self._store[key]
            return None
        # Di chuyển key lên cuối (recently used)
        self._store.move_to_end(key)
        return value

    def put(self, key: str, value: Any) -> None:
        if key in self._store:
            self._store.move_to_end(key)
        self._store[key] = (value, time.monotonic())
        if len(self._store) > self._max_size:
            self._store.popitem(last=False)  # Xóa phần tử cũ nhất (LRU)

# Sử dụng
cache = LRUCache(max_size=5000, ttl_seconds=60.0)
cache.put("user:42", {"name": "Minh", "role": "admin"})
result = cache.get("user:42")  # O(1) lookup

Tại sao OrderedDict thay vì dict? Dù dict giữ thứ tự chèn từ 3.7, OrderedDict cung cấp move_to_end() và popitem(last=False) — hai thao tác thiết yếu cho LRU mà dict thường không có.

Scenario 2 — Deduplicate event stream với set và deque

Hệ thống nhận event từ nhiều microservice. Cùng một event có thể đến nhiều lần (at-least-once delivery). Cần: loại bỏ trùng, giữ lại cửa sổ N event gần nhất để tránh memory leak.

python

from collections import deque

class EventDeduplicator:
    """Loại bỏ event trùng trong cửa sổ kích thước cố định."""

    def __init__(self, window_size: int = 10_000) -> None:
        self._seen_ids: set[str] = set()
        self._id_queue: deque[str] = deque(maxlen=window_size)

    def is_duplicate(self, event_id: str) -> bool:
        if event_id in self._seen_ids:  # O(1) lookup
            return True
        # Nếu deque đầy, phần tử cũ nhất sẽ bị đẩy ra
        if len(self._id_queue) == self._id_queue.maxlen:
            evicted_id: str = self._id_queue[0]
            self._seen_ids.discard(evicted_id)
        self._id_queue.append(event_id)
        self._seen_ids.add(event_id)
        return False

# Xử lý stream
dedup = EventDeduplicator(window_size=50_000)
incoming_events = [
    ("evt-001", "user.login"),
    ("evt-002", "order.created"),
    ("evt-001", "user.login"),  # duplicate
]
for event_id, event_type in incoming_events:
    if not dedup.is_duplicate(event_id):
        print(f"Processing: {event_id} — {event_type}")
    # evt-001 chỉ được xử lý một lần

Pattern này kết hợp set (lookup O(1)) với deque (maxlen tự evict) để giữ memory bounded. Không cần timestamp, không cần TTL — kích thước cửa sổ là đủ cho nhiều use case.

Sai lầm điển hình

1. Mutable default argument — Bug kinh điển

python

# ❌ SAI — list mặc định được chia sẻ giữa mọi lần gọi
def add_tag(tag: str, tags: list[str] = []) -> list[str]:
    tags.append(tag)
    return tags

print(add_tag("python"))   # ['python']
print(add_tag("docker"))   # ['python', 'docker'] — BUG!

# ✅ ĐÚNG — dùng None sentinel
def add_tag(tag: str, tags: list[str] | None = None) -> list[str]:
    if tags is None:
        tags = []
    tags.append(tag)
    return tags

Tại sao sai? Python evaluate default arguments một lần duy nhất tại thời điểm định nghĩa hàm, không phải mỗi lần gọi. Object [] được tạo một lần và tái sử dụng — mọi lời gọi chia sẻ cùng một list. Đây là nguyên nhân của hàng nghìn bug trong production, đặc biệt nguy hiểm vì unit test thường chỉ gọi hàm một lần nên không phát hiện.

2. Dùng list làm hàng đợi — Chậm thầm lặng

python

# ❌ SAI — list.pop(0) là O(n)
queue: list[str] = []
queue.append("task-1")
queue.append("task-2")
task = queue.pop(0)  # O(n) — dịch toàn bộ mảng

# ✅ ĐÚNG — deque.popleft() là O(1)
from collections import deque
queue: deque[str] = deque()
queue.append("task-1")
queue.append("task-2")
task = queue.popleft()  # O(1)

Tại sao sai? Với 100 phần tử bạn không thấy khác biệt. Với 1 triệu phần tử, list.pop(0) mất hàng trăm millisecond mỗi lần gọi vì phải dịch toàn bộ mảng nội bộ. deque dùng doubly-linked list nội bộ nên thao tác ở cả hai đầu luôn là O(1).

3. Dict key phải hashable và bất biến

python

# ❌ SAI — list không hashable
cache: dict = {}
cache[[1, 2, 3]] = "value"  # TypeError: unhashable type: 'list'

# ✅ ĐÚNG — chuyển sang tuple
cache[(1, 2, 3)] = "value"

# ❌ NGUY HIỂM — key bị mutate sau khi chèn
class Config:
    def __init__(self, env: str) -> None:
        self.env = env
    def __hash__(self) -> int:
        return hash(self.env)
    def __eq__(self, other: object) -> bool:
        return isinstance(other, Config) and self.env == other.env

cfg = Config("prod")
registry: dict[Config, str] = {cfg: "us-east-1"}
cfg.env = "staging"  # Mutate key!
print(registry.get(cfg))  # None — key "mất tích" trong hash table

# ✅ ĐÚNG — dùng frozen dataclass
from dataclasses import dataclass

@dataclass(frozen=True)
class Config:
    env: str

cfg = Config("prod")
registry = {cfg: "us-east-1"}
# cfg.env = "staging"  # FrozenInstanceError — an toàn

4. Shallow copy với nested structures

python

# ❌ SAI — shallow copy chỉ copy lớp ngoài
matrix: list[list[int]] = [[1, 2], [3, 4]]
clone = matrix[:]       # hoặc matrix.copy() hoặc list(matrix)

clone[0][0] = 999
print(matrix[0][0])     # 999 — bản gốc bị ảnh hưởng!

# ✅ ĐÚNG — deep copy cho nested structures
import copy
clone = copy.deepcopy(matrix)
clone[0][0] = 999
print(matrix[0][0])     # 1 — bản gốc an toàn

Tại sao sai? Shallow copy tạo list mới nhưng các phần tử bên trong vẫn trỏ đến cùng object. Với list lồng (list of lists, list of dicts), bạn buộc phải dùng copy.deepcopy() hoặc tạo lại thủ công từng phần tử.

5. Sửa list trong khi duyệt

python

# ❌ SAI — bỏ sót phần tử
numbers: list[int] = [1, 2, 3, 4, 5, 6]
for n in numbers:
    if n % 2 == 0:
        numbers.remove(n)
print(numbers)  # [1, 3, 5]? Không — kết quả thực tế là [1, 3, 5] nhưng bỏ sót 4!

# ✅ ĐÚNG — tạo list mới bằng comprehension
numbers = [n for n in numbers if n % 2 != 0]

# ✅ ĐÚNG — duyệt ngược nếu phải sửa tại chỗ
for i in range(len(numbers) - 1, -1, -1):
    if numbers[i] % 2 == 0:
        del numbers[i]

Under the Hood

List — Dynamic array với over-allocation

Trong CPython, PyListObject lưu một con trỏ ob_item đến mảng con trỏ PyObject*. Hai giá trị quan trọng: ob_size (số phần tử thực) và allocated (kích thước mảng đã cấp phát).

PyListObject (56 bytes trên 64-bit)
├── ob_refcnt    (8B) — reference count
├── ob_type      (8B) — pointer đến type object
├── ob_size      (8B) — số phần tử hiện tại
├── allocated    (8B) — kích thước mảng con trỏ đã cấp phát
└── ob_item      (8B) — pointer đến mảng PyObject*
         │
         ▼
    ┌──────┬──────┬──────┬──────┬───────────┐
    │ ptr0 │ ptr1 │ ptr2 │ ...  │ (trống)   │
    └──┬───┴──┬───┴──┬───┴──────┴───────────┘
       ▼      ▼      ▼
    PyObj  PyObj  PyObj

Khi append() vượt quá allocated, CPython resize theo công thức: new_size = old_size + (old_size >> 3) + 6. Chuỗi capacity thực tế: 0 → 4 → 8 → 16 → 25 → 35 → 46 → 58 → 72 → 88 → ... Đây là chiến lược over-allocation, đảm bảo append() có amortized O(1).

python

import sys

# Quan sát over-allocation
sizes: list[tuple[int, int]] = []
lst: list[int] = []
for i in range(20):
    lst.append(i)
    sizes.append((len(lst), sys.getsizeof(lst)))

# len=1 → 88B, len=4 → 88B (cùng allocation)
# len=5 → 120B (resize!), len=8 → 120B
# len=9 → 184B (resize!)...

Dict — Compact hash table (kể từ Python 3.6)

Trước 3.6, dict dùng một bảng hash duy nhất trong đó mỗi slot chứa (hash, key, value). Các slot trống vẫn chiếm đủ memory → lãng phí. Từ 3.6, Raymond Hettinger thiết kế lại thành hai mảng tách biệt:

PyDictKeysObject
├── dk_indices[]  — mảng indices (int8/int16/int32 tùy kích thước)
│   Sparse hash table: hash(key) % dk_size → index vào dk_entries
│   Slot trống = -1, slot đã xóa = -2
│
└── dk_entries[]  — mảng compact, chỉ chứa entries thực tế
    Mỗi entry = (hash: Py_hash_t, key: PyObject*, value: PyObject*)
    Entries lưu theo thứ tự chèn → dict ordered!

Tại sao compact dict tiết kiệm memory? Mảng dk_indices chỉ chứa integer nhỏ (1–4 bytes mỗi slot), thay vì 3 con trỏ 8 bytes. Mảng dk_entries không có slot trống. Kết quả: tiết kiệm 20–25% memory so với thiết kế cũ.

Open addressing với probing: khi hash collision xảy ra, CPython không dùng chaining (linked list) mà dùng perturbation probing: next_index = (5 * index + perturb + 1) % size; perturb >>= 5. Pattern này phân tán collision tốt hơn linear probing.

Resize: khi dk_usable (số slot khả dụng) về 0, dict resize gấp đôi. Load factor mục tiêu là 2/3 — nghĩa là bảng hash kích thước 8 chỉ chứa tối đa 5 entry trước khi resize.

Set — Hash table thuần túy

PySetObject dùng một bảng hash đơn giản hơn dict: mỗi slot là (hash, key), không có value. Không dùng thiết kế compact hai mảng như dict, nên set không đảm bảo thứ tự chèn (khác dict).

So sánh memory thực tế

python

import sys

# Cùng 1000 phần tử — memory khác biệt đáng kể
n = 1000
data_range = range(n)

list_mem = sys.getsizeof(list(data_range))    # ~8056 bytes
tuple_mem = sys.getsizeof(tuple(data_range))  # ~8040 bytes
set_mem = sys.getsizeof(set(data_range))      # ~32984 bytes
dict_mem = sys.getsizeof({i: i for i in data_range})  # ~36960 bytes

# set và dict tốn memory gấp ~4 lần list/tuple
# (do hash table cần slot trống cho load factor 2/3)

Structure	1000 phần tử	Ghi chú
`list`	~8 KB	Chỉ mảng con trỏ
`tuple`	~8 KB	Tương tự list, ít overhead hơn
`set`	~33 KB	Hash table + load factor
`dict`	~37 KB	Hash table + values

Bộ nhớ trên chỉ tính overhead của container, chưa tính bộ nhớ của chính các object bên trong. Với int nhỏ (< 256), CPython cache sẵn nên không tốn thêm. Với object lớn, container overhead trở nên không đáng kể so với payload.

Checklist ghi nhớ

✅ Checklist triển khai

Chọn đúng cấu trúc

[ ] Dùng set hoặc dict khi cần kiểm tra in trên tập dữ liệu > 100 phần tử
[ ] Dùng tuple cho dữ liệu bất biến và khi cần hashable key
[ ] Dùng deque thay vì list khi cần queue (popleft / appendleft)
[ ] Dùng NamedTuple thay vì tuple thường khi có > 2 trường

Tránh lỗi phổ biến

[ ] Không dùng mutable object (list, dict) làm default argument
[ ] Không sửa list/dict/set trong khi đang duyệt — tạo bản mới
[ ] Dùng copy.deepcopy() khi clone nested structures
[ ] Chỉ dùng hashable, immutable object làm dict key hoặc set element

collections là bạn

[ ] defaultdict(list) cho nhóm dữ liệu — sạch hơn setdefault()
[ ] Counter cho đếm tần suất — không cần viết tay
[ ] deque(maxlen=N) cho sliding window — tự evict khi đầy

Performance

[ ] Generator expression (x for x in ...) cho dữ liệu lớn — tiết kiệm RAM
[ ] dict.fromkeys(lst) để dedup và giữ thứ tự — nhanh hơn thủ công
[ ] Profile trước khi optimize — sys.getsizeof() và tracemalloc là điểm bắt đầu

Bài tập luyện tập

Bài 1 — Phân tích log với Counter

🧠 Quiz

Câu hỏi: Cho danh sách status code từ access log, hãy viết hàm trả về dictionary {status_group: count} với status_group là "2xx", "3xx", "4xx", "5xx".

python

codes = [200, 200, 301, 404, 200, 500, 404, 200, 301, 503, 200]
# Kết quả mong đợi: {"2xx": 5, "3xx": 2, "4xx": 2, "5xx": 2}

[ ] A. Dùng if/elif lồng nhau cho từng status code
[ ] B. Dùng defaultdict(int) với code // 100 làm key
[x] C. Dùng Counter kết hợp generator expression
[ ] D. Dùng list.count() cho mỗi nhóm

Giải thích: Counter kết hợp với phép chia nguyên // 100 cho lời giải gọn nhất. Option B cũng đúng nhưng Counter giảm boilerplate. Option D gọi .count() nhiều lần → O(n × k).

Lời giải

python

from collections import Counter

def group_status_codes(codes: list[int]) -> dict[str, int]:
    """Nhóm HTTP status code theo nhóm 2xx, 3xx, 4xx, 5xx."""
    group_counter: Counter[str] = Counter(
        f"{code // 100}xx" for code in codes
    )
    return dict(group_counter)

codes = [200, 200, 301, 404, 200, 500, 404, 200, 301, 503, 200]
print(group_status_codes(codes))
# {'2xx': 5, '3xx': 2, '4xx': 2, '5xx': 2}

Bài 2 — Top K sản phẩm bán chạy

Cho danh sách đơn hàng (product_id, quantity), viết hàm trả về K sản phẩm có tổng số lượng bán cao nhất.

python

orders = [
    ("P001", 5), ("P002", 3), ("P001", 2), ("P003", 10),
    ("P002", 7), ("P004", 1), ("P003", 5), ("P001", 8),
]
# top_products(orders, k=2) → [("P001", 15), ("P003", 15)]

Lời giải

python

from collections import Counter

def top_products(
    orders: list[tuple[str, int]],
    k: int,
) -> list[tuple[str, int]]:
    """Trả về k sản phẩm có tổng quantity cao nhất."""
    total_qty: Counter[str] = Counter()
    for product_id, qty in orders:
        total_qty[product_id] += qty
    return total_qty.most_common(k)

orders = [
    ("P001", 5), ("P002", 3), ("P001", 2), ("P003", 10),
    ("P002", 7), ("P004", 1), ("P003", 5), ("P001", 8),
]
print(top_products(orders, k=2))
# [('P001', 15), ('P003', 15)]

Counter.most_common(k) dùng heapq.nlargest bên dưới — O(n log k) thay vì O(n log n) khi sort toàn bộ.

Bài 3 — Sliding window maximum

Cho list số nguyên và kích thước cửa sổ k, trả về list chứa giá trị lớn nhất trong mỗi cửa sổ trượt. Dùng deque để đạt O(n).

python

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
# sliding_max(nums, 3) → [3, 3, 5, 5, 6, 7]

Lời giải

python

from collections import deque

def sliding_max(nums: list[int], k: int) -> list[int]:
    """Tìm max trong mỗi cửa sổ trượt kích thước k — O(n)."""
    result: list[int] = []
    # deque lưu index, đảm bảo nums[dq[0]] luôn là max trong cửa sổ
    dq: deque[int] = deque()

    for i, val in enumerate(nums):
        # Loại bỏ phần tử ngoài cửa sổ
        if dq and dq[0] <= i - k:
            dq.popleft()
        # Loại bỏ phần tử nhỏ hơn val — chúng không bao giờ là max
        while dq and nums[dq[-1]] <= val:
            dq.pop()
        dq.append(i)
        # Thêm kết quả khi cửa sổ đủ kích thước
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

print(sliding_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

Mỗi phần tử chỉ được thêm và loại khỏi deque tối đa một lần → tổng thao tác O(n). Đây là pattern kinh điển dùng deque như monotone queue.

Liên kết học tiếp

Glossary: hash table · amortized complexity · open addressing · load factor · compact dict · dynamic array · over-allocation · sliding window · monotone queue

Cấu trúc dữ liệu Python — List, Tuple, Set, Dict & Beyond Core ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Tổng quan & Bảng so sánh ​

List — Mảng động ​

Tuple — Bản ghi bất biến ​

Set — Tập hợp duy nhất ​

Dict — Bảng băm ​

collections.deque — Hàng đợi hai đầu ​

collections.defaultdict — Dict tự khởi tạo ​

collections.Counter — Đếm tần suất chuyên dụng ​

typing.NamedTuple — Tuple có tên trường ​

Thực chiến ​

Scenario 1 — Xây lớp cache đơn giản với dict và TTL ​

Scenario 2 — Deduplicate event stream với set và deque ​

Sai lầm điển hình ​

1. Mutable default argument — Bug kinh điển ​

2. Dùng list làm hàng đợi — Chậm thầm lặng ​

3. Dict key phải hashable và bất biến ​

4. Shallow copy với nested structures ​

5. Sửa list trong khi duyệt ​

Under the Hood ​

List — Dynamic array với over-allocation ​

Dict — Compact hash table (kể từ Python 3.6) ​

Set — Hash table thuần túy ​

So sánh memory thực tế ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1 — Phân tích log với Counter ​

Bài 2 — Top K sản phẩm bán chạy ​

Bài 3 — Sliding window maximum ​

Liên kết học tiếp ​

Cấu trúc dữ liệu Python — List, Tuple, Set, Dict & Beyond Core

Bức tranh tư duy

Cốt lõi kỹ thuật

Tổng quan & Bảng so sánh

List — Mảng động

Tuple — Bản ghi bất biến

Set — Tập hợp duy nhất

Dict — Bảng băm

collections.deque — Hàng đợi hai đầu

collections.defaultdict — Dict tự khởi tạo

collections.Counter — Đếm tần suất chuyên dụng

typing.NamedTuple — Tuple có tên trường

Thực chiến

Scenario 1 — Xây lớp cache đơn giản với dict và TTL

Scenario 2 — Deduplicate event stream với set và deque

Sai lầm điển hình

1. Mutable default argument — Bug kinh điển

2. Dùng list làm hàng đợi — Chậm thầm lặng

3. Dict key phải hashable và bất biến

4. Shallow copy với nested structures

5. Sửa list trong khi duyệt

Under the Hood

List — Dynamic array với over-allocation

Dict — Compact hash table (kể từ Python 3.6)

Set — Hash table thuần túy

So sánh memory thực tế

Checklist ghi nhớ

Bài tập luyện tập

Bài 1 — Phân tích log với Counter

Bài 2 — Top K sản phẩm bán chạy

Bài 3 — Sliding window maximum

Liên kết học tiếp