Không có cấu trúc dữ liệu tốt nhất — chỉ có đúng việc

Suốt cả sê-ri này, mỗi phần đo một cấu trúc và một đánh đổi. Đến đây có một câu hỏi tổng kết: rốt cuộc cấu trúc nào tốt nhất? Câu trả lời — và cũng là chủ đề xuyên suốt — là không có cái nào.

Hỏi "cấu trúc dữ liệu nào tốt nhất" cũng giống hỏi "dụng cụ nào tốt nhất trong hộp đồ nghề". Búa vô địch khi đóng đinh, thảm họa khi vặn ốc; tua vít ngược lại. Không ai hỏi "cái nào tốt nhất" — người ta hỏi "tôi đang làm gì". Cấu trúc dữ liệu y hệt: trên cùng một tập dữ liệu, cấu trúc thắng thay đổi hoàn toàn tùy bạn làm gì với nó nhiều nhất — đọc, ghi, hay duyệt. Tôi lấy đúng 100.000 phần tử, để vào ba cấu trúc quen thuộc (vector, unordered_map, std::list), rồi chạy ba mẫu truy cập khác nhau trong container gcc:13. Con số cho thấy winner đảo ngược theo workload — không phải vài phần trăm, mà hàng chục tới hàng trăm lần.

Ba mẫu truy cập, ba điểm mạnh khác nhau

Ba cấu trúc mạnh ở ba việc khác nhau, vì chúng đặt dữ liệu khác nhau:

• Đọc/tra cứu theo khóa: hash map băm thẳng tới chỗ — O(1). Mảng sắp xếp + tìm nhị phân là O(log n) nhưng mỗi bước là một truy cập rải rác (cache miss). Linked list là O(n) — tệ.
• Duyệt tuần tự toàn bộ: mảng phẳng liền mạch, cache tốt, prefetch — nhanh nhất. Hash map và list cùng chứa dữ liệu đó nhưng ở các node rải rác trên heap, nên duyệt chậm hơn dù cùng O(n).
• Chèn/xóa ở giữa (khi đã giữ vị trí): linked list chỉ nối lại vài con trỏ — O(1). Mảng phải dịch cả đuôi sang để chừa chỗ — O(n).

Không cấu trúc nào thắng cả ba. Chọn đúng nghĩa là biết thao tác nào chiếm đa số.

Đo: winner đảo hoàn toàn theo workload

Tôi để 100.000 phần tử vào cả ba, rồi đo ba workload:

Cùng 100.000 phần tử, 3 mẫu truy cập, g++ -O2:

A. ĐỌC/TRA CỨU theo khóa (5 triệu lần, ns/lần):
   unordered_map (hash O(1))      :  1,85 ns   <- THẮNG
   vector sắp xếp + tìm nhị phân  : 58,31 ns   (~31 lần chậm hơn)

B. DUYỆT TUẦN TỰ toàn bộ (ns/phần tử):
   vector (liền mạch)             : 0,114 ns   <- THẮNG
   std::list (con trỏ rải rác)    : 0,931 ns   (8,2 lần)
   unordered_map (rải rác)        : 1,055 ns   (9,2 lần)

C. CHÈN + XÓA Ở GIỮA, giữ vị trí (50.000 lần, ns/lần):
   vector (dịch cả đuôi O(n))     : 6140,2 ns
   std::list (O(1) tại chỗ)       :    8,40 ns  <- THẮNG (731 lần nhanh hơn)

Nhìn A — sân của hash: tra cứu một khóa qua unordered_map mất 1,85 ns, còn tìm nhị phân trên mảng sắp xếp mất 58,31 ns — chậm hơn ~31 lần. Dù nhị phân là O(log n) "tốt", mỗi trong ~17 bước của nó nhảy tới một vị trí xa trong mảng (cache miss + đoán nhánh sai), trong khi hash chỉ một phép băm + một hai lần chạm. Cho workload đọc-nhiều, hash map thắng.

Nhìn B — sân của mảng: duyệt và cộng toàn bộ, vector chỉ mất 0,114 ns/phần tử, còn list và unordered_map mất 0,931 và 1,055 ns — chậm hơn 8–9 lần, dù cả ba đều O(n) và chứa cùng dữ liệu. Toàn bộ khác biệt là cache: vector đọc bộ nhớ liền mạch (prefetch giấu độ trễ), còn list/hash theo con trỏ tới các node rải rác (cache miss mỗi bước). Cho workload duyệt-nhiều, mảng thắng đậm.

Nhìn C — sân của list: chèn rồi xóa ở giữa (giữ sẵn vị trí), vector mất 6140 ns mỗi lần vì phải dịch cả nửa đuôi mảng (O(n)), còn list chỉ mất 8,4 ns vì chỉ nối lại vài con trỏ (O(1)) — nhanh hơn 731 lần. Cho workload chèn/xóa-giữa-nhiều, linked list thắng áp đảo.

Ba workload, ba winner hoàn toàn khác nhau, trên cùng một dữ liệu. Đây là bằng chứng gọn nhất cho cả sê-ri: không có "cấu trúc tốt nhất" — chỉ có "cấu trúc đúng cho mẫu truy cập này".

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

Tôi từng có một cấu trúc "tủ" — hồi mới học là linked list (nghe linh hoạt), sau này là hash map (nghe O(1)) — và quơ nó cho mọi bài. Con số bác ngay: trên cùng 100.000 phần tử, winner đảo hoàn toàn theo mẫu truy cập. Hash map thắng đọc (31 lần) nhưng thua duyệt (9 lần chậm hơn mảng) và không chèn-giữa được; mảng thắng duyệt (8 lần) nhưng thua đọc-theo-khóa (31 lần chậm hơn hash) và thảm họa khi chèn giữa (731 lần chậm hơn list); list thắng chèn giữa (731 lần) nhưng tệ ở cả đọc lẫn duyệt. Không có cái "tốt nhất" — mỗi cái tốt nhất ở đúng một mẫu, đúng như búa với tua vít.

Nhưng nếu vì thế mà lùi về "vậy chọn theo Big-O của thao tác chính là đủ — đọc thì O(1) hash, duyệt thì O(n) mảng, xong" thì cũng chỉ nửa đúng, vì hằng số và cache lật kèo ngay trong cùng một bậc Big-O. Tìm nhị phân O(log n) thua hash O(1) tới 31 lần (không phải "gần bằng" như log n gợi ý) vì cache miss; và mảng duyệt thắng list/hash dù cả ba cùng O(n) — hằng số cache tạo khác biệt 8–9 lần mà Big-O hoàn toàn im lặng. Big-O gợi ý bậc, đo mới cho hằng số. Chọn theo Big-O rồi đo lại ở workload thật mới chắc.

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

Việc đầu tiên: đừng hỏi "cấu trúc nào tốt nhất" — hỏi "tôi làm thao tác gì nhiều nhất trên dữ liệu này". Đọc/tra cứu theo khóa nhiều → hash map. Duyệt/quét toàn bộ nhiều (tính tổng, lọc, xử lý theo lô) → mảng phẳng/vector. Chèn/xóa ở giữa nhiều tại vị trí đã biết → linked list. Ghi ở hai đầu → deque/ring buffer. Cần thứ tự + tra cứu → cây/sorted vector. Bắt đầu từ mẫu truy cập, không từ thói quen.

Việc thứ hai: nhiều workload trộn lẫn — chọn theo thao tác NÓNG nhất, rồi đo. Nếu bạn đọc một tập 1000 lần và chỉ chèn 5 lần, tối ưu cho đọc (hash/mảng), chấp nhận chèn chậm. Nếu duyệt toàn bộ mỗi khung hình nhưng hiếm khi tra theo khóa, dùng mảng dù tra chậm. Và khi hai cấu trúc "cùng Big-O" cho thao tác chính, đo — hằng số cache thường quyết định (mảng vs list khi duyệt là ví dụ điển hình).

Cái nguyên tắc "chọn theo mẫu truy cập" này là cùng một tư duy dùng ở mọi tầng, chỉ tên gọi to ra. Java cho bạn HashMap (đọc theo khóa), ArrayList (duyệt, truy cập theo chỉ số), LinkedList (chèn/xóa hai đầu) — và chọn nhầm là nguồn của vô số code chậm; đây cũng là lý do ArrayList gần như luôn thắng LinkedList trong thực tế, vì workload duyệt/index nhiều hơn chèn-giữa hơn ta tưởng. Lên tầng hệ thống, cùng câu hỏi định hình cả kiến trúc lưu trữ: dữ liệu đọc-theo-khóa nhiều thì key-value store (Redis, DynamoDB); quét/tổng hợp cả cột thì kho cột (ClickHouse, Parquet); ghi tuần tự nhiều đọc ngẫu nhiên ít thì LSM-tree (Cassandra, RocksDB); quan hệ + truy vấn linh hoạt thì B-tree của SQL. Mỗi "database" thực chất là một cấu trúc dữ liệu tối ưu cho một mẫu truy cập, và chọn sai ở quy mô đó đắt hơn nhiều một std::list sai chỗ. Nguyên tắc xuyên suốt: bắt đầu từ bạn sẽ truy cập dữ liệu thế nào, rồi đo ở đúng workload đó.

Muốn tự thấy thì lấy một tập vài chục nghìn phần tử và để vào ba cấu trúc: std::vector, std::unordered_map, std::list. Rồi chạy ba vòng bấm giờ. Một: tra cứu theo khóa vài triệu lần — hash map sẽ nhanh vượt trội, còn tìm nhị phân trên vector chậm hơn nhiều vì cache miss. Hai: duyệt và cộng toàn bộ nhiều lần — lần này vector thắng đậm, list và map chậm 8–9 lần vì con trỏ rải rác, dù cùng O(n). Ba: giữ một vị trí ở giữa và chèn-rồi-xóa vài chục nghìn lần — list gần như tức thời (O(1) nối con trỏ), còn vector chậm hàng trăm lần vì dịch cả đuôi. Ba kết quả, ba winner khác nhau, trên cùng dữ liệu. Ba mươi giây đó cho thấy điều mà "cấu trúc X là tốt nhất" giấu đi: không có cái tốt nhất — chỉ có cái đúng cho mẫu truy cập của bạn, và cách duy nhất để biết chắc là đo chính cái workload bạn sẽ chạy.