Cấu trúc dữ liệu Core

Chọn đúng cấu trúc dữ liệu = Chọn đúng công cụ cho công việc

Learning Outcomes

Sau khi hoàn thành trang này, bạn sẽ:

🎯 Hiểu time complexity của các operations trên list, dict, set
🎯 Nắm được memory layout và cách Python lưu trữ dữ liệu
🎯 Biết cách chọn đúng cấu trúc dữ liệu cho từng use case
🎯 Tránh được các Production Pitfalls phổ biến

Time Complexity Table

List Operations

Operation	Average Case	Worst Case	Ghi chú
`list[i]`	O(1)	O(1)	Truy cập index
`list.append(x)`	O(1)	O(1)	Amortized
`list.insert(i, x)`	O(n)	O(n)	Phải shift elements
`list.pop()`	O(1)	O(1)	Pop cuối
`list.pop(i)`	O(n)	O(n)	Phải shift elements
`x in list`	O(n)	O(n)	Linear search
`list.remove(x)`	O(n)	O(n)	Tìm + shift
`list.sort()`	O(n log n)	O(n log n)	Timsort
`len(list)`	O(1)	O(1)	Cached
`list[i:j]`	O(k)	O(k)	k = j - i

Dict Operations

Operation	Average Case	Worst Case	Ghi chú
`dict[key]`	O(1)	O(n)	Hash collision
`dict[key] = value`	O(1)	O(n)	Hash collision
`key in dict`	O(1)	O(n)	Hash lookup
`dict.get(key)`	O(1)	O(n)	Safe access
`del dict[key]`	O(1)	O(n)	Hash collision
`dict.keys()`	O(1)	O(1)	View object
`dict.values()`	O(1)	O(1)	View object
`dict.items()`	O(1)	O(1)	View object
`len(dict)`	O(1)	O(1)	Cached

Set Operations

Operation	Average Case	Worst Case	Ghi chú
`x in set`	O(1)	O(n)	Hash lookup
`set.add(x)`	O(1)	O(n)	Hash collision
`set.remove(x)`	O(1)	O(n)	Hash collision
`set \| other`	O(len(s)+len(t))	-	Union
`set & other`	O(min(len(s),len(t)))	-	Intersection
`set - other`	O(len(s))	-	Difference
`len(set)`	O(1)	O(1)	Cached

⚠️ WORST CASE LÀ GÌ?

Worst case O(n) xảy ra khi có hash collision - nhiều keys có cùng hash value. Trong thực tế với hash function tốt, điều này hiếm khi xảy ra.

Memory Layout

List - Dynamic Array

┌─────────────────────────────────────────────────────────┐
│                    PyListObject                         │
├─────────────────────────────────────────────────────────┤
│  ob_refcnt  │  ob_type  │  ob_size  │  allocated       │
│     8B      │    8B     │    8B     │     8B           │
├─────────────────────────────────────────────────────────┤
│                    ob_item (pointer)                    │
│                         8B                              │
└─────────────────────────────────────────────────────────┘
                          │
                          ▼
┌─────────────────────────────────────────────────────────┐
│  ptr[0]  │  ptr[1]  │  ptr[2]  │  ...  │  (allocated)  │
│   8B     │   8B     │   8B     │       │               │
└─────────────────────────────────────────────────────────┘
     │          │          │
     ▼          ▼          ▼
  PyObject  PyObject  PyObject

Key Points:

List lưu pointers đến objects, không phải objects trực tiếp
allocated >= ob_size (over-allocation cho append nhanh)
Mỗi pointer = 8 bytes trên 64-bit system

python

import sys

# List overhead
lst = []
print(sys.getsizeof(lst))  # 56 bytes (empty list)

lst = [1, 2, 3]
print(sys.getsizeof(lst))  # 88 bytes (56 + 3*8 + padding)

Dict - Hash Table

┌─────────────────────────────────────────────────────────┐
│                    PyDictObject                         │
├─────────────────────────────────────────────────────────┤
│  ma_used  │  ma_version_tag  │  ma_keys  │  ma_values  │
└─────────────────────────────────────────────────────────┘
                                    │
                                    ▼
┌─────────────────────────────────────────────────────────┐
│                   PyDictKeysObject                      │
├─────────────────────────────────────────────────────────┤
│  dk_refcnt  │  dk_size  │  dk_lookup  │  dk_usable    │
├─────────────────────────────────────────────────────────┤
│                    dk_indices[]                         │
│  [sparse hash table - indices into dk_entries]         │
├─────────────────────────────────────────────────────────┤
│                    dk_entries[]                         │
│  [compact array of (hash, key, value) tuples]          │
└─────────────────────────────────────────────────────────┘

Key Points:

Python 3.7+ dict giữ insertion order (compact dict)
Hash table với open addressing (không dùng chaining)
Load factor ~2/3 trước khi resize

python

import sys

# Dict overhead
d = {}
print(sys.getsizeof(d))  # 64 bytes (empty dict)

d = {"a": 1, "b": 2, "c": 3}
print(sys.getsizeof(d))  # 184 bytes

Set - Hash Table (Keys Only)

┌─────────────────────────────────────────────────────────┐
│                    PySetObject                          │
├─────────────────────────────────────────────────────────┤
│  fill  │  used  │  mask  │  table  │  hash  │  finger  │
└─────────────────────────────────────────────────────────┘
                              │
                              ▼
┌─────────────────────────────────────────────────────────┐
│                    setentry[]                           │
│  [(hash, key), (hash, key), ...]                       │
└─────────────────────────────────────────────────────────┘

Key Points:

Tương tự dict nhưng chỉ lưu keys
Không giữ insertion order (khác với dict)
Tối ưu cho membership testing

List vs Tuple vs Set

Bảng So sánh Nhanh

Đặc điểm	List	Tuple	Set
Có thể thay đổi	✅ Có	❌ Không	✅ Có
Có thứ tự	✅ Có	✅ Có	❌ Không
Cho phép trùng	✅ Có	✅ Có	❌ Không
Truy cập index	✅ Có	✅ Có	❌ Không
Hashable	❌ Không	✅ Có	❌ Không
Tìm kiếm	O(n)	O(n)	O(1)

List - Khi cần thay đổi dữ liệu

python

# ✅ ĐÚNG: List khi cần modify
users = ["Alice", "Bob"]
users.append("Charlie")  # Thêm phần tử
users[0] = "Alicia"      # Thay đổi phần tử

# ❌ SAI: Dùng list để kiểm tra membership
if "Bob" in users:  # O(n) - chậm với list lớn
    pass

Tuple - Khi dữ liệu là bất biến

python

# ✅ ĐÚNG: Tuple cho dữ liệu cố định
TOA_DO_HCM = (10.762622, 106.660172)  # Vĩ độ, Kinh độ
RGB_DO = (255, 0, 0)

# ✅ ĐÚNG: Tuple làm key cho dict (vì hashable)
cache = {}
cache[(10, 20)] = "gia_tri_cache"

# ✅ ĐÚNG: Trả về nhiều giá trị
def lay_user() -> tuple[str, int]:
    return ("HPN", 28)

ten, tuoi = lay_user()  # Unpacking

Set - Khi cần unique + tìm kiếm nhanh

python

# ✅ ĐÚNG: Set để kiểm tra membership
ip_bi_chan = {"192.168.1.1", "10.0.0.1", "172.16.0.1"}

if ip in ip_bi_chan:  # O(1) - cực nhanh!
    chan_request()

# ✅ ĐÚNG: Loại bỏ trùng lặp
emails = ["a@x.com", "b@x.com", "a@x.com"]
emails_duy_nhat = list(set(emails))  # ["a@x.com", "b@x.com"]

# ✅ ĐÚNG: Các phép toán tập hợp
admins = {"alice", "bob"}
moderators = {"bob", "charlie"}

tat_ca_nhan_vien = admins | moderators  # Hợp: {"alice", "bob", "charlie"}
ca_hai_vai_tro = admins & moderators    # Giao: {"bob"}
chi_admin = admins - moderators         # Hiệu: {"alice"}

💡 QUY TẮC CỦA HPN

Cần thay đổi? → List
Dữ liệu cố định? → Tuple
Cần unique + tìm nhanh? → Set

Dict - Bảng băm (Hash Map)

Cách Dict hoạt động

Python Dict là Hash Table với:

O(1) trung bình cho lookup, insert, delete
O(n) trường hợp xấu nhất (hash collision)

Các Pattern với Dict

python

# ✅ Hiện đại: Dict comprehension
binh_phuong = {x: x**2 for x in range(10)}
# {0: 0, 1: 1, 2: 4, 3: 9, ...}

# ✅ Truy cập an toàn với .get()
user = {"ten": "HPN"}
tuoi = user.get("tuoi", 0)  # Trả về 0 nếu key không tồn tại

# ❌ TRÁNH: Rủi ro KeyError
tuoi = user["tuoi"]  # Ném KeyError!

# ✅ setdefault - Lấy hoặc Đặt
cache = {}
cache.setdefault("users", []).append("Alice")
# Tạo list rỗng nếu chưa có, rồi append

# ✅ defaultdict - Tự động khởi tạo
from collections import defaultdict
dem_tu = defaultdict(int)
for tu in danh_sach_tu:
    dem_tu[tu] += 1  # Không cần kiểm tra key tồn tại

Gộp Dict (Python 3.9+)

python

# ✅ Hiện đại: Toán tử merge
mac_dinh = {"theme": "dark", "lang": "vi"}
tuy_chinh = {"theme": "light"}

cuoi_cung = mac_dinh | tuy_chinh  # {"theme": "light", "lang": "vi"}

# ✅ Cập nhật tại chỗ
mac_dinh |= tuy_chinh

List Comprehension

Tại sao nhanh hơn vòng lặp For?

python

# ❌ CHẬM: Vòng lặp truyền thống
ket_qua = []
for x in range(1000000):
    ket_qua.append(x * 2)

# ✅ NHANH: List comprehension
ket_qua = [x * 2 for x in range(1000000)]

Tại sao List Comprehension nhanh hơn?

Bytecode tối ưu: Python compiler tối ưu riêng cho comprehension
Ít function calls: .append() là method call = overhead
Pre-allocation: Python biết trước size của list mới

Benchmark

python

import timeit

# Vòng lặp for: ~0.12s
timeit.timeit('[x*2 for x in range(1000000)]', number=10)

# Vòng lặp append: ~0.18s (chậm hơn 50%!)
timeit.timeit('''
ket_qua = []
for x in range(1000000):
    ket_qua.append(x*2)
''', number=10)

Comprehension Nâng cao

python

# Lọc dữ liệu
chan = [x for x in range(100) if x % 2 == 0]

# Lồng nhau (làm phẳng list 2D)
ma_tran = [[1, 2], [3, 4], [5, 6]]
phang = [so for hang in ma_tran for so in hang]
# [1, 2, 3, 4, 5, 6]

# Dict comprehension
users = [("alice", 25), ("bob", 30)]
user_dict = {ten: tuoi for ten, tuoi in users}

# Set comprehension
do_dai_duy_nhat = {len(tu) for tu in ["hi", "hello", "hey"]}
# {2, 3, 5}

Generator Expression - Tiết kiệm bộ nhớ

python

# ❌ List: Nạp TẤT CẢ vào bộ nhớ
sum([x**2 for x in range(10_000_000)])  # ~400MB RAM

# ✅ Generator: Tính toán lười (lazy)
sum(x**2 for x in range(10_000_000))  # ~0MB RAM

⚠️ MẸO HIỆU NĂNG

Với dữ liệu lớn, dùng Generator Expression (x for x in ...) thay vì List Comprehension [x for x in ...] để tiết kiệm bộ nhớ.

Bảng Tóm tắt

python

# === CHỌN ĐÚNG CẤU TRÚC DỮ LIỆU ===

# List: Có thứ tự, thay đổi được, cho phép trùng
items = [1, 2, 3, 2]

# Tuple: Có thứ tự, bất biến, hashable
toa_do = (10, 20)
cache_key = (user_id, trang)

# Set: Không thứ tự, duy nhất, O(1) lookup
da_xem = {1, 2, 3}

# Dict: Key-value, O(1) theo key
config = {"debug": True}

# === COMPREHENSIONS ===

# List comp (tạo list)
[f(x) for x in items if dieu_kien]

# Generator exp (lazy, tiết kiệm bộ nhớ)
(f(x) for x in items if dieu_kien)

# Dict comp
{k: v for k, v in pairs}

# Set comp
{f(x) for x in items}

Production Pitfalls

Pitfall 1: Mutable Default Arguments

python

# ❌ BUG KINH ĐIỂN: Mutable default argument
def them_user(user: str, users: list = []) -> list:
    users.append(user)
    return users

print(them_user("Alice"))  # ['Alice']
print(them_user("Bob"))    # ['Alice', 'Bob'] - WTF?!

# ✅ SỬA: Dùng None làm default
def them_user(user: str, users: list | None = None) -> list:
    if users is None:
        users = []
    users.append(user)
    return users

Tại sao? Default arguments được evaluate một lần khi function được định nghĩa, không phải mỗi lần gọi.

Pitfall 2: Modifying List While Iterating

python

# ❌ BUG: Modify list trong khi iterate
numbers = [1, 2, 3, 4, 5]
for n in numbers:
    if n % 2 == 0:
        numbers.remove(n)  # Skip elements!

print(numbers)  # [1, 3, 5]? NO! [1, 3, 5] may vary

# ✅ SỬA 1: Iterate over copy
for n in numbers[:]:  # Slice tạo copy
    if n % 2 == 0:
        numbers.remove(n)

# ✅ SỬA 2: List comprehension (preferred)
numbers = [n for n in numbers if n % 2 != 0]

# ✅ SỬA 3: Filter với reversed index
for i in range(len(numbers) - 1, -1, -1):
    if numbers[i] % 2 == 0:
        del numbers[i]

Pitfall 3: Dict Key Mutation

python

# ❌ BUG: Dùng mutable object làm dict key
class User:
    def __init__(self, name: str):
        self.name = name
    
    def __hash__(self):
        return hash(self.name)
    
    def __eq__(self, other):
        return self.name == other.name

user = User("Alice")
cache = {user: "data"}

user.name = "Bob"  # Mutate key!
print(cache.get(user))  # None - key "lost"!

# ✅ SỬA: Dùng immutable keys hoặc frozen dataclass
from dataclasses import dataclass

@dataclass(frozen=True)
class User:
    name: str

user = User("Alice")
cache = {user: "data"}
# user.name = "Bob"  # FrozenInstanceError!

Pitfall 4: Shallow Copy Surprise

python

# ❌ BUG: Shallow copy với nested structures
original = [[1, 2], [3, 4]]
copy = original[:]  # Shallow copy

copy[0][0] = 999
print(original)  # [[999, 2], [3, 4]] - Original bị modify!

# ✅ SỬA: Deep copy cho nested structures
import copy
deep = copy.deepcopy(original)
deep[0][0] = 999
print(original)  # [[1, 2], [3, 4]] - Original intact

Pitfall 5: Set/Dict với Unhashable Types

python

# ❌ ERROR: List không hashable
my_set = {[1, 2, 3]}  # TypeError: unhashable type: 'list'

# ✅ SỬA: Convert to tuple
my_set = {(1, 2, 3)}  # OK

# ❌ ERROR: Dict với list key
cache = {[1, 2]: "value"}  # TypeError

# ✅ SỬA: Dùng tuple làm key
cache = {(1, 2): "value"}  # OK

Pitfall 6: Memory Explosion với Large Lists

python

# ❌ CHẬM + TỐN RAM: Load tất cả vào memory
def xu_ly_file_lon(path: str) -> list[str]:
    with open(path) as f:
        lines = f.readlines()  # Load ALL lines!
    return [line.upper() for line in lines]

# ✅ TỐT: Generator - lazy evaluation
def xu_ly_file_lon(path: str):
    with open(path) as f:
        for line in f:  # Iterate line by line
            yield line.upper()

# Hoặc dùng generator expression
lines = (line.upper() for line in open(path))

Pitfall 7: `is` vs `==` Confusion

python

# ❌ BUG: Dùng `is` để so sánh values
a = [1, 2, 3]
b = [1, 2, 3]
print(a is b)  # False - different objects!
print(a == b)  # True - same values

# Tricky case với small integers (CPython caches -5 to 256)
x = 256
y = 256
print(x is y)  # True (cached)

x = 257
y = 257
print(x is y)  # False (not cached) - NEVER rely on this!

# ✅ QUY TẮC: Dùng `is` CHỈ cho None, True, False
if value is None:  # ✅ Correct
    pass

if value == None:  # ❌ Works but not Pythonic
    pass

🚨 PRODUCTION RULE

Luôn dùng == để so sánh values, is chỉ dùng cho identity check (None, singletons).

Cross-links

Memory Model - Hiểu sâu về reference counting và GC
Performance Optimization (Phase 3) - Tối ưu memory với __slots__
Algorithms - Data Structures - Các cấu trúc dữ liệu nâng cao

Bảng Tóm tắt

python

# === CHỌN ĐÚNG CẤU TRÚC DỮ LIỆU ===

# List: Có thứ tự, thay đổi được, cho phép trùng
items = [1, 2, 3, 2]

# Tuple: Có thứ tự, bất biến, hashable
toa_do = (10, 20)
cache_key = (user_id, trang)

# Set: Không thứ tự, duy nhất, O(1) lookup
da_xem = {1, 2, 3}

# Dict: Key-value, O(1) theo key
config = {"debug": True}

# === COMPREHENSIONS ===

# List comp (tạo list)
[f(x) for x in items if dieu_kien]

# Generator exp (lazy, tiết kiệm bộ nhớ)
(f(x) for x in items if dieu_kien)

# Dict comp
{k: v for k, v in pairs}

# Set comp
{f(x) for x in items}

Cấu trúc dữ liệu Core ​

Learning Outcomes ​

Time Complexity Table ​

List Operations ​

Dict Operations ​

Set Operations ​

Memory Layout ​

List - Dynamic Array ​

Dict - Hash Table ​

Set - Hash Table (Keys Only) ​

List vs Tuple vs Set ​

Bảng So sánh Nhanh ​

List - Khi cần thay đổi dữ liệu ​

Tuple - Khi dữ liệu là bất biến ​

Set - Khi cần unique + tìm kiếm nhanh ​

Dict - Bảng băm (Hash Map) ​

Cách Dict hoạt động ​

Các Pattern với Dict ​

Gộp Dict (Python 3.9+) ​

List Comprehension ​

Tại sao nhanh hơn vòng lặp For? ​

Benchmark ​

Comprehension Nâng cao ​

Generator Expression - Tiết kiệm bộ nhớ ​

Bảng Tóm tắt ​

Production Pitfalls ​

Pitfall 1: Mutable Default Arguments ​

Pitfall 2: Modifying List While Iterating ​

Pitfall 3: Dict Key Mutation ​

Pitfall 4: Shallow Copy Surprise ​

Pitfall 5: Set/Dict với Unhashable Types ​

Pitfall 6: Memory Explosion với Large Lists ​

Pitfall 7: is vs == Confusion ​

Cross-links ​

Bảng Tóm tắt ​

Cấu trúc dữ liệu Core

Learning Outcomes

Time Complexity Table

List Operations

Dict Operations

Set Operations

Memory Layout

List - Dynamic Array

Dict - Hash Table

Set - Hash Table (Keys Only)

List vs Tuple vs Set

Bảng So sánh Nhanh

List - Khi cần thay đổi dữ liệu

Tuple - Khi dữ liệu là bất biến

Set - Khi cần unique + tìm kiếm nhanh

Dict - Bảng băm (Hash Map)

Cách Dict hoạt động

Các Pattern với Dict

Gộp Dict (Python 3.9+)

List Comprehension

Tại sao nhanh hơn vòng lặp For?

Benchmark

Comprehension Nâng cao

Generator Expression - Tiết kiệm bộ nhớ

Bảng Tóm tắt

Production Pitfalls

Pitfall 1: Mutable Default Arguments

Pitfall 2: Modifying List While Iterating

Pitfall 3: Dict Key Mutation

Pitfall 4: Shallow Copy Surprise

Pitfall 5: Set/Dict với Unhashable Types

Pitfall 6: Memory Explosion với Large Lists

Pitfall 7: `is` vs `==` Confusion

Cross-links

Bảng Tóm tắt