Trie (cây tiền tố, prefix tree) là cấu trúc lưu chuỗi theo từng ký tự trên đường từ gốc: cat là gốc → c → a → t. Các chuỗi chung tiền tố chia sẻ đường đi — cat và car cùng đi qua c → a. Nghe như một cách thông minh và tiết kiệm để lưu tập chuỗi, và nhiều người mặc định "chuỗi thì dùng trie". Nhưng khi tôi đo trie so với hash set trong container gcc:13, kết quả không đơn giản: trie thắng tuyệt đối ở một việc, nhưng thua ở những việc khác — và biết trie dùng để làm gì quan trọng hơn biết nó tồn tại.
Siêu năng lực tiền tố, cái giá bộ nhớ
Vì trie lưu chuỗi theo từng ký tự trên đường đi, nó có một khả năng mà hash không thể có: tra tiền tố. Muốn "mọi từ bắt đầu bằng ca"? Đi tới node ca (theo hai ký tự), rồi liệt kê cả cây con dưới đó — O(độ dài tiền tố + số kết quả). Đây chính là cơ chế của autocomplete, gợi ý tìm kiếm, kiểm tra từ điển. Hash thì băm cả chuỗi thành một số, làm mất hoàn toàn thông tin tiền tố — nó biết cat có trong tập không, nhưng không có cách nào hỏi "những gì bắt đầu bằng ca" ngoài việc quét toàn bộ tập.
Cái giá của trie là bộ nhớ. Mỗi node giữ một mảng con trỏ tới các con — 26 cho a-z, 256 cho byte tùy ý — nên mỗi node nặng (trong đo của tôi, 216 byte). Dù các chuỗi chia sẻ tiền tố, tổng số node vẫn rất lớn.
Đo: thắng prefix 94 lần, thua RAM 11 lần
Tôi dựng 500 nghìn từ (chia sẻ 100 tiền tố 3 ký tự) bằng cả trie (mảng 26 con) và unordered_set<string>:
500k từ, chia sẻ 100 tiền tố, g++ -O2:
A. TRA TIỀN TỐ (đếm số từ bắt đầu bằng prefix):
trie : 572 µs/truy vấn (walk tới prefix + liệt kê cây con)
hash : 53.966 µs/truy vấn (KHÔNG có index tiền tố -> QUÉT toàn bộ 500k từ!)
-> trie nhanh hơn ~94 lần (và hash bó tay về nguyên tắc)
B. BỘ NHỚ:
trie : 255,9 MB (1,18 triệu node × 216 B, mảng 26 con trỏ)
hash : ~23 MB
-> trie tốn ~11 lần NHIỀU hơn
C. EXACT MATCH (tra cứu chính xác 1 chuỗi, 1 triệu lần):
trie : 49,6 ns/tra cứu
hash : 64,8 ns/tra cứu
-> xấp xỉ nhau (trie hơi nhanh hơn ở đây)
Nhìn A: trie tra tiền tố trong 572 µs, còn hash mất 53.966 µs (~54 ms) — chậm hơn 94 lần. Nhưng con số 94 lần chưa nói hết: hash không có cách nào làm truy vấn tiền tố ngoài quét toàn bộ tập; nó không phải "chậm hơn" mà là sai công cụ. Với tập lớn hơn, khoảng cách còn giãn ra vì hash luôn O(N) mỗi truy vấn prefix. Đây là lý do trie tồn tại.
Nhưng B cho thấy cái giá: trie tốn 255,9 MB, hash chỉ 23 MB — trie ngốn ~11 lần nhiều hơn, vì mỗi node mang một mảng 26 con trỏ dù phần lớn rỗng. Và C phá vỡ một huyền thoại: nhiều người nghĩ "hash luôn nhanh hơn cho exact match". Ở đây, với chuỗi ngắn (6-10 ký tự) và tiền tố chung, trie thực ra hơi nhanh hơn (49,6 so với 64,8 ns) — vì các node tầng trên (tiền tố chung) luôn nóng trong cache, còn hash phải băm cả chuỗi. (Với chuỗi dài và ngẫu nhiên, hash thường thắng lại — kết quả phụ thuộc dữ liệu.) Điểm mấu chốt: exact match hai bên xấp xỉ, không phải trie kém.
Một lần tôi đo hớ: "trie luôn tốt" và "hash làm được mọi thứ"
Tôi vào đo với niềm tin "chuỗi thì dùng trie, nó thông minh hơn hash". Đo phá tan một nửa: trie tốn RAM gấp 11 lần, và exact match chỉ ngang hash — nếu bạn chỉ cần lưu và tra chính xác một tập chuỗi, hash gọn hơn và đủ nhanh. Trie không "luôn tốt hơn". Nhưng rồi đo cũng phá tan niềm tin ngược "hash làm được mọi thứ trie làm, cứ dùng hash": sai — hash băm cả chuỗi nên không truy vấn tiền tố được; nó phải quét toàn bộ, chậm 94 lần và không mở rộng. Trie thắng đúng một loại việc, nhưng thắng tuyệt đối, và đó là loại việc rất quan trọng (autocomplete, gợi ý).
Bài học đo lường: trie và hash cho tập chuỗi phục vụ mục đích KHÁC nhau — trie thắng TUYỆT ĐỐI ở tra tiền tố/autocomplete (đo 572 µs vs hash 53.966 µs = 94x, vì hash không index prefix được, phải quét O(N)); nhưng trie (mảng con trỏ) tốn RAM ~11x hash (255,9 vs 23 MB) và exact match chỉ xấp xỉ (49,6 vs 64,8 ns). Chọn trie khi cần truy vấn theo tiền tố; hash khi chỉ cần exact match và gọn bộ nhớ. Nếu tôi tin "trie luôn tốt" và dùng nó cho một tập chỉ cần tra chính xác, tôi phí 10 lần RAM vô ích; nếu tôi tin "hash làm được mọi thứ" và cần autocomplete, tôi phải quét toàn bộ mỗi lần gõ phím — không dùng được.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: dùng trie khi bạn cần truy vấn theo tiền tố; dùng hash khi chỉ cần thành viên/exact match. Autocomplete, gợi ý tìm kiếm, "tất cả từ khóa bắt đầu bằng…", định tuyến URL theo prefix, kiểm tra từ điển với hoàn thành — đây là sân của trie. Còn "chuỗi này đã thấy chưa", "map từ khóa tới giá trị" — unordered_set/unordered_map gọn hơn và đủ nhanh. Đừng chọn theo "cấu trúc nào nghe thông minh hơn"; chọn theo loại truy vấn.
Hệ quả thứ hai: nếu dùng trie mà lo bộ nhớ, chọn cách biểu diễn node phù hợp. Mảng 26/256 con trỏ nhanh nhưng tốn RAM (nhiều ô rỗng). Thay bằng một map/vector con nhỏ mỗi node thì nhẹ hơn nhiều nhưng tra chậm hơn (phải tìm trong danh sách con). Có các biến thể nén như radix tree/PATRICIA trie gộp các đoạn một-con thành một cạnh, giảm số node mạnh — đó là cái các router và cơ sở dữ liệu dùng cho chỉ mục chuỗi/IP.
Hệ quả thứ ba là tinh thần đo lường: so hai cấu trúc phải so trên truy vấn bạn thật sự cần, không so chung chung. Con số mang theo: trie (cây tiền tố) vs hash cho tập chuỗi: trie THẮNG tra tiền tố/autocomplete tuyệt đối (572 µs vs hash quét toàn bộ 53.966 µs = 94x — hash không index prefix được); nhưng trie mảng-con-trỏ tốn RAM ~11x (255,9 vs 23 MB) và exact match xấp xỉ (49,6 vs 64,8 ns, tùy độ dài chuỗi/cache). Chọn trie khi cần prefix; hash khi chỉ exact match + gọn RAM. Trie không "tốt hơn hash" — nó khác hash, và làm được một việc hash không làm nổi.
Thử ba mươi giây
Dựng một tập vài trăm nghìn chuỗi bằng cả unordered_set và một trie tự viết (mỗi node một mảng con). Thử hai truy vấn. Thứ nhất, "chuỗi X có trong tập không" (exact match): hai bên xấp xỉ, tùy độ dài chuỗi. Thứ hai, "liệt kê mọi chuỗi bắt đầu bằng tiền tố ab": với trie là đi tới node ab rồi duyệt cây con — vài micro-giây; với hash, bạn sẽ nhận ra không có cách nào ngoài quét toàn bộ tập, chậm hàng chục mili-giây, và tệ dần khi tập lớn. Rồi in số node của trie và ước tính bộ nhớ — bạn sẽ thấy nó ngốn nhiều RAM hơn hash. Ba mươi giây đó cho bạn thấy điều mà "chuỗi thì dùng trie" giấu đi: trie không phải phiên bản tốt hơn của hash — nó là công cụ cho truy vấn tiền tố, đổi bộ nhớ lấy một khả năng mà hash về nguyên tắc không có. Chọn cấu trúc theo câu hỏi bạn sẽ hỏi nó.
