Trie không 'tốt hơn' hash — nó làm được thứ hash chịu thua

Nghĩ về một cuốn từ điển giấy so với một hộp danh thiếp đổ lộn xộn. Muốn tìm "từ cat có trong từ điển không", cả hai đều làm được — từ điển thì lật tới trang, hộp thì bốc từng tấm. Nhưng hỏi "cho tôi mọi từ bắt đầu bằng ca", từ điển lật đúng một chỗ rồi đọc xuôi cả loạt, còn cái hộp thì bó tay: bạn phải lật từng tấm một để lọc. Từ điển sắp theo thứ tự chữ cái nên câu hỏi "bắt đầu bằng…" gần như miễn phí; cái hộp thì mỗi tấm là một danh tính rời rạc. Một trie chính là cuốn từ điển đó, và một hash set chính là cái hộp.

Trie (cây tiền tố, prefix tree) 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. Đúng cảnh lật từng tấm danh thiế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ôi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, 500k từ chia sẻ 100 tiền tố, mỗi số lấy MIN sau warmup. Con số đổi theo độ dài chuỗi và bảng chữ; cái cần nhìn là trie index được prefix còn hash thì không, và cái giá RAM của mảng con trỏ.)

Hai niềm tin đối nghịch, cùng sai

Tôi vào đo với niềm tin "chuỗi thì dùng trie, nó thông minh hơn hash". Con số 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 đo cũng phá tan niềm tin ngược "hash làm được mọi thứ trie làm, cứ dùng hash cho gọn": 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 ý). Hai cấu trúc không xếp hạng hơn-kém; chúng trả lời hai loại câu hỏi khác nhau.

Về đến code hằng ngày

Điều đầ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.

Điều 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.

Chỗ này đúng là nơi trie âm thầm chạy dưới nhiều hệ thống bạn dùng hằng ngày, dưới cái tên radix tree nén. Bảng định tuyến IP trong kernel Linux dùng một biến thể trie (LPC-trie/radix) để tìm "prefix mạng dài nhất khớp" — đúng bài toán tiền tố, chỉ trên bit thay vì chữ. Router HTTP của nhiều framework web (Go có httprouter, và Gin dùng nó) khớp đường dẫn URL bằng radix tree, nên /users/:id và /users/settings chia sẻ nhánh /users/. Ở tầng database, chỉ mục cho truy vấn LIKE 'abc%' tận dụng đúng thứ tự tiền tố của B-tree — cùng tinh thần "sắp theo thứ tự thì hỏi tiền tố gần như miễn phí". Còn autocomplete của thanh tìm kiếm thì gần như luôn có một trie (hoặc cấu trúc họ hàng) ở sau. Nhận ra "à, đây là bài toán tiền tố" là lúc bạn với tay tới trie thay vì hash.

Muốn tự thấy thì 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. Vài phút đó 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ó.