Bỏ qua tới nội dung chính

Trước khi có cấu trúc dữ liệu

Cấu trúc dữ liệu và giải thuật: sắp xếp dữ liệu sao cho máy tìm nhanh

Vì sao cùng một dữ liệu, cất cách này tìm mất một giây, cách kia mất một giờ: mảng, danh sách liên kết, ngăn xếp, hàng đợi, bảng băm, cây, sắp xếp.

Ban biên tập OpenER

Cập nhật 09/11/2026 · 16 phút đọc · CC BY 4.0

Thử hình dung hai thư viện cùng có một triệu cuốn sách. Thư viện thứ nhất chất sách thành đống theo thứ tự ngày nhập. Thư viện thứ hai xếp sách lên kệ theo mã chủ đề, có tủ phiếu tra cứu theo tên tác giả và tên sách. Muốn tìm một cuốn, ở thư viện thứ nhất bạn có thể phải lật cả đống; ở thư viện thứ hai, vài phút là xong. Hai thư viện có cùng số sách — khác nhau ở cách cất.

Máy tính cũng vậy. Ứng dụng nhắn tin tìm lại một tin nhắn cũ trong hàng chục nghìn tin, trình soạn thảo hoàn tác (Ctrl+Z) đúng thao tác vừa làm, ô tìm kiếm gợi ý chữ tiếp theo khi bạn mới gõ hai ký tự — tất cả nhanh không phải nhờ máy mạnh, mà nhờ dữ liệu được cất trong đúng cấu trúc dữ liệu (data structure), và được xử lý bằng đúng giải thuật (algorithm). Năm 1976, Niklaus Wirth — tác giả ngôn ngữ Pascal — đặt tên cho cuốn sách của mình bằng một phương trình mà sinh viên ngành này vẫn nhắc: Giải thuật + Cấu trúc dữ liệu = Chương trình.

Trước khi có cấu trúc dữ liệu

Bài toán "cất dữ liệu sao cho tìm nhanh" có trước máy tính điện tử. Cuộc điều tra dân số năm 1880 ở Mỹ được kiểm đếm bằng tay và mất nhiều năm mới xong. Cho lần điều tra năm 1890, Herman Hollerith dùng bìa đục lỗ: mỗi người dân là một tấm bìa, mỗi đặc điểm là một vị trí lỗ, và máy đếm bằng điện đọc các lỗ đó. Việc kiểm đếm rút xuống còn khoảng một phần nhỏ thời gian cũ. Công ty của Hollerith về sau là một phần của IBM. Trong nhiều thập niên, "xử lý dữ liệu" nghĩa là máy phân loại bìa: xếp chồng bìa theo một cột, rồi theo cột tiếp theo — một dạng sắp xếp làm bằng cơ khí.

Khi máy tính điện tử ra đời, dữ liệu chuyển vào bộ nhớ, nhưng lúc đầu nó chỉ có một hình dạng: một dãy ô liền nhau — mảng (array). Muốn chèn một phần tử vào giữa, phải dời mọi phần tử phía sau. Muốn tìm, phải duyệt từ đầu. Các cấu trúc khác ra đời từng cái một, mỗi cái để giải một kiểu chậm:

  1. Bảng băm (hash table) — đầu thập niên 1950, Hans Peter Luhn ở IBM đề xuất ý tưởng chia dữ liệu vào các ngăn theo một phép tính trên khóa, để đi thẳng tới ngăn cần tìm thay vì duyệt cả dãy.
  2. Danh sách liên kết (linked list) — giữa thập niên 1950, Allen Newell, Cliff Shaw và Herbert Simon dùng nó trong ngôn ngữ IPL cho các chương trình trí tuệ nhân tạo đầu tiên: mỗi phần tử tự chỉ tới phần tử kế, nên chèn hay xóa ở giữa không phải dời ai.
  3. Ngăn xếp (stack) — cũng thập niên 1950, Friedrich Bauer và Klaus Samelson ở Đức dùng nguyên lý "vào sau, ra trước" để dịch biểu thức số học — nền của mọi trình biên dịch.
  4. Cây B (B-tree) — năm 1970, Rudolf Bayer và Edward McCreight thiết kế loại cây tối ưu cho ổ đĩa, đến nay vẫn là xương sống của hầu hết cơ sở dữ liệu và hệ thống file.

Đặt cạnh nhau:

Chỉ có dữ liệu xếp thành dãy
Có cấu trúc dữ liệu phù hợp
Tìm một phần tử trong 1 triệu
Duyệt tới 1 triệu lần
Khoảng 20 bước (cây, dãy đã sắp) hoặc gần như 1 bước (bảng băm)
Chèn vào giữa
Dời mọi phần tử phía sau
Đổi vài con trỏ
Lấy phần tử ưu tiên nhất
Duyệt cả dãy mỗi lần
Lấy ngay ở đỉnh đống (heap)
Hoàn tác thao tác vừa làm
Phải lưu và dò lại cả lịch sử
Lấy phần tử trên đỉnh ngăn xếp
Khi dữ liệu tăng gấp 1.000 lần
Chậm theo, thường còn tệ hơn
Thường gần như không đổi

Thiếu kiến thức này vẫn là nguyên nhân phổ biến nhất khiến phần mềm chậm hôm nay. Một bảng tính dùng VLOOKUP tra cả bảng cho từng dòng, mỗi lần tính lại mất cả phút. Một chương trình kiểm tra "mã này đã có chưa" bằng cách duyệt một danh sách dài, chạy tốt với 100 mã rồi bò như rùa với 1 triệu mã. Cách sửa thường chỉ là đổi một dòng — đổi danh sách thành tập hợp, thêm một chỉ mục — nếu người viết biết phải đổi thành gì.

Môn này trả lời câu hỏi gì

Môn Cấu trúc dữ liệu và giải thuật trả lời câu hỏi: với một tập dữ liệu và những thao tác cần làm trên nó — thêm, xóa, tìm, lấy theo thứ tự, lấy phần tử nhỏ nhất — nên cất dữ liệu theo hình dạng nào, và xử lý nó bằng cách nào, để các thao tác đó nhanh và tốn ít bộ nhớ?

Điểm mấu chốt: không có cấu trúc nào tốt nhất cho mọi việc. Mỗi cấu trúc nhanh ở một vài thao tác và chậm ở thao tác khác. Môn học dạy bạn một "hộp đồ nghề" — mảng, danh sách liên kết, ngăn xếp, hàng đợi, bảng băm, cây, đống, đồ thị — cùng với cách đánh giá chi phí của từng thao tác, để chọn đúng món cho từng việc.

Vì sao cần học? Vì đây là môn biến người "viết được code" thành người "viết được code chạy tốt". Nó cũng là môn được hỏi nhiều nhất trong phỏng vấn kỹ sư phần mềm, và là nền cho môn Thiết kế và phân tích thuật toán — nơi bạn học cách tự thiết kế thuật toán mới và chứng minh chúng đúng.

Năm ý tưởng cốt lõi

1. Mảng và danh sách liên kết: hai cách xếp hàng

Bộ nhớ máy tính là một dãy ô dài, mỗi ô có một địa chỉ. Có hai cách cơ bản để cất một danh sách vào đó.

Mảng đặt các phần tử sát nhau. Muốn lấy phần tử thứ 500.000, máy tính địa chỉ bằng một phép nhân và một phép cộng rồi đọc thẳng — gọi là truy cập ngẫu nhiên (random access), nhanh như nhau với mọi vị trí. Mảng còn được bộ xử lý ưu ái: đọc một phần tử thì các phần tử kế bên cũng được nạp sẵn vào bộ nhớ đệm, nên duyệt mảng rất nhanh. Cái giá: chèn hay xóa ở giữa phải dời cả đoạn phía sau.

Danh sách liên kết cho mỗi phần tử nằm ở đâu cũng được, kèm một con trỏ (pointer) chỉ tới phần tử kế tiếp — giống một cuộc truy tìm kho báu, mỗi mảnh giấy ghi nơi có mảnh giấy tiếp theo. Chèn vào giữa chỉ cần sửa hai con trỏ. Cái giá: muốn tới phần tử thứ 500.000, phải lần theo 500.000 con trỏ.

Bài học đầu tiên của môn này nằm ngay ở đây: chọn cấu trúc là chọn thao tác nào được nhanh. Danh sách nhạc bạn hay chèn bài vào giữa — liên kết. Bảng điểm bạn hay tra theo số thứ tự — mảng.

2. Ngăn xếp và hàng đợi: ai ra trước

Hai cấu trúc đơn giản nhất, cũng là hai cấu trúc có mặt ở khắp nơi, chỉ khác nhau ở thứ tự lấy ra:

  • Ngăn xếp (stack) — vào sau, ra trước, như chồng đĩa: đĩa đặt lên cuối cùng được lấy ra đầu tiên. Nút Hoàn tác trong trình soạn thảo, nút Quay lại trong trình duyệt, và chính cách máy tính gọi hàm — mỗi lời gọi hàm được đặt lên ngăn xếp lời gọi (call stack), hàm gọi sau cùng trả về trước tiên. Lỗi "stack overflow" nổi tiếng là khi chồng đĩa đó cao quá giới hạn, thường vì một hàm đệ quy không dừng.
  • Hàng đợi (queue) — vào trước, ra trước, như xếp hàng mua vé. Lệnh in đang chờ máy in, tin nhắn chờ gửi, yêu cầu chờ máy chủ xử lý.

Ngăn xếp giải gọn một bài toán mà bài Lý thuyết tính toán chỉ ra là biểu thức chính quy không làm được: kiểm tra ngoặc có cân bằng không.

python
def ngoac_can_bang(s):
    cap = {")": "(", "]": "[", "}": "{"}
    ngan_xep = []
    for c in s:
        if c in "([{":
            ngan_xep.append(c)                  # mở ngoặc: đặt lên đỉnh
        elif c in cap:
            if not ngan_xep or ngan_xep.pop() != cap[c]:
                return False                    # đóng mà không khớp ngoặc mở gần nhất
    return not ngan_xep                         # còn ngoặc mở chưa đóng thì sai

print(ngoac_can_bang("{[()()]}"), ngoac_can_bang("([)]"))   # True False

Trình soạn thảo code tô đỏ ngoặc thừa, trình biên dịch báo "thiếu dấu đóng ngoặc" — đều là một ngăn xếp như thế này.

3. Bảng băm: đi thẳng tới chỗ cần tìm

Muốn biết một số điện thoại có trong danh bạ một triệu số không, duyệt từng số là một triệu bước. Bảng băm (hash table) làm khác: dùng một hàm băm (hash function) biến khóa thành số thứ tự của một ngăn, rồi cất phần tử vào đúng ngăn đó. Khi tìm, tính lại hàm băm, đi thẳng tới ngăn — trung bình chỉ vài bước, dù có một triệu hay một tỷ phần tử.

dict và set của Python, HashMap của Java, Object và Map của JavaScript đều là bảng băm. Khác biệt thấy được ngay khi đo:

python
import time

ma = list(range(1_000_000))       # một triệu mã, cất trong danh sách
tap = set(ma)                     # cùng dữ liệu, cất trong bảng băm
can_tim = [999_999] * 200         # tìm phần tử nằm cuối, 200 lần

for ten, kho in [("danh sách", ma), ("bảng băm", tap)]:
    bat_dau = time.perf_counter()
    for x in can_tim:
        x in kho
    print(ten, f"{time.perf_counter() - bat_dau:.6f}", "giây")

Trên một máy tính thông thường, bản dùng bảng băm nhanh hơn hàng chục nghìn lần. Cùng dữ liệu, cùng câu lệnh x in kho — chỉ khác cách cất.

Hai ngăn có thể bị trùng, gọi là va chạm (collision) — theo nguyên lý chuồng bồ câu thì không tránh được, chỉ có thể làm cho hiếm và xử lý khéo. Hàm băm tốt rải dữ liệu đều; hàm băm tồi dồn mọi thứ vào vài ngăn và bảng băm chậm như một danh sách. Cái giá khác của bảng băm: nó không giữ thứ tự. Muốn lấy "mọi khách hàng có tên từ A tới C" theo thứ tự, bảng băm không giúp được — cần một cấu trúc khác.

4. Cây: dữ liệu có thứ bậc và có thứ tự

Cây (tree) là cấu trúc mà mỗi phần tử có thể có nhiều phần tử con. Bạn gặp nó mỗi ngày: thư mục chứa thư mục con, trang web là cây các thẻ HTML lồng nhau, sơ đồ tổ chức của công ty.

Một vài loại cây quan trọng nhất:

  • Cây tìm kiếm nhị phân (binary search tree): mỗi nút có tối đa hai con, con bên trái nhỏ hơn, con bên phải lớn hơn. Tìm, chèn, xóa đều chỉ đi dọc một nhánh — với cây cân bằng một triệu phần tử, khoảng 20 bước. Và khác bảng băm, cây giữ được thứ tự: lấy mọi phần tử trong một khoảng rất dễ.
  • Cây B (B-tree): mỗi nút chứa hàng trăm khóa, nên cây rất "lùn" — tìm trong hàng tỷ bản ghi chỉ cần vài lần đọc ổ đĩa. Khi bạn tạo một chỉ mục (index) trong cơ sở dữ liệu, gần như chắc chắn bạn đang tạo một cây B.
  • Đống (heap): một cây luôn giữ phần tử nhỏ nhất (hoặc lớn nhất) ở gốc. Đó là hàng đợi ưu tiên (priority queue): hệ điều hành chọn tiến trình chạy tiếp, ứng dụng chỉ đường chọn ngã tư gần nhất để xét tiếp, bệnh viện chọn bệnh nhân nặng nhất để khám trước.
  • Cây tiền tố (trie): mỗi nhánh là một chữ cái, nên mọi từ có chung phần đầu nằm chung một nhánh. Gõ "ng" vào ô tìm kiếm và thấy ngay "nguyễn", "ngân hàng", "ngữ pháp" — đó là một cây tiền tố.

Một bẫy cần nhớ: chèn dữ liệu đã sắp sẵn vào cây tìm kiếm nhị phân thì cây thành một nhánh dài, chậm như danh sách. Cây tự cân bằng (AVL, đỏ đen) tự xoay lại sau mỗi lần chèn để giữ cây lùn.

5. Sắp xếp và nghệ thuật đánh đổi

Sắp xếp là bài toán được nghiên cứu nhiều nhất của ngành, vì dữ liệu đã sắp thì mọi việc khác dễ hơn: tìm nhị phân, gộp hai danh sách, loại phần tử trùng. Môn học đi qua một loạt cách sắp, mỗi cách là một bài học về đánh đổi:

Cách sắp
Ý tưởng
Điểm mạnh
Điểm yếu
Sắp xếp chèn (insertion sort)
Như xếp bài trên tay: lấy từng lá, chèn vào đúng chỗ
Rất nhanh với dữ liệu nhỏ hoặc gần như đã sắp
Chậm theo bình phương với dữ liệu lớn
Sắp xếp trộn (merge sort)
Chia đôi, sắp từng nửa, trộn lại
Luôn nhanh, giữ thứ tự của phần tử bằng nhau
Cần thêm bộ nhớ
Sắp xếp nhanh (quicksort)
Chọn một phần tử làm mốc, chia thành nhỏ hơn và lớn hơn mốc
Thường nhanh nhất trên thực tế, không cần thêm nhiều bộ nhớ
Có trường hợp xấu chậm theo bình phương

Quicksort do Tony Hoare nghĩ ra khoảng năm 1959 – 1960, khi ông cần sắp xếp các từ để làm một chương trình dịch máy. Hàm sort mà bạn gọi hằng ngày thường là một lai ghép của vài cách trên: thuật toán Timsort, do Tim Peters viết cho Python năm 2002, kết hợp sắp xếp trộn với sắp xếp chèn và tận dụng những đoạn dữ liệu thật thường đã sắp sẵn một phần.

Bài học lớn hơn là đánh đổi: nhanh hơn thường tốn bộ nhớ hơn, và tốt với dữ liệu ngẫu nhiên chưa chắc tốt với dữ liệu thật. Người giỏi môn này không thuộc lòng "cái nào tốt nhất", mà hỏi: dữ liệu của mình trông thế nào, và cần thao tác nào nhanh?

Cấu trúc dữ liệu nằm ở đâu trong chồng tầng

Nếu bạn đã đọc Từ electron đến ứng dụng, máy tính là một chồng tầng trừu tượng. Cấu trúc dữ liệu là tầng nối giữa bộ nhớ và ý nghĩa:

Tầng dưới đưa lên

bộ nhớ là một dãy ô có địa chỉ, đọc ô liền kề nhanh hơn nhảy xa (nhờ bộ nhớ đệm), ổ đĩa đọc theo từng khối lớn.

Đưa lên

danh sách, tập hợp, từ điển, hàng đợi, cây — những khái niệm mà người lập trình nghĩ bằng chúng, không cần nghĩ về địa chỉ.

Giấu đi

dữ liệu thật ra nằm ở ô nào, được dời đi khi nào, va chạm băm được xử lý ra sao.

Mọi tầng phía trên đều đứng trên chúng: hệ điều hành dùng hàng đợi để lập lịch và cây để quản lý bộ nhớ ảo; mạng máy tính dùng bảng định tuyến; cơ sở dữ liệu dùng cây B và bảng băm; trình biên dịch dựng cây cú pháp từ code của bạn.

Học trước và học sau

· 6 môn

Lập trình

Programming

Học trước sẽ dễ hơn: viết được hàm, vòng lặp, đệ quy.

Xem chủ đề trên OpenER: Programming

Toán rời rạc, logic và chứng minh

Mathematics for Computer Science

Học trước một phần: quy nạp, đếm.

Xem chủ đề trên OpenER: Mathematics for Computer Science

Thiết kế và phân tích thuật toán

Design and Analysis of Algorithms

Học sau, dùng lại môn này.

Xem chủ đề trên OpenER: Design and Analysis of Algorithms

Hệ cơ sở dữ liệu

Database Systems

Học sau, dùng lại môn này.

Xem chủ đề trên OpenER: Database Systems

Hệ điều hành

Operating Systems

Học sau, dùng lại môn này.

Xem chủ đề trên OpenER: Operating Systems

Ngôn ngữ lập trình và trình biên dịch

Programming Languages and Compilers

Học sau, dùng lại môn này.

Xem chủ đề trên OpenER: Programming Languages and Compilers

Gần như mọi môn còn lại cũng dùng lại môn này.

Ứng dụng thật và nghề nghiệp

  • Phỏng vấn kỹ thuật: phần lớn vòng phỏng vấn lập trình ở các công ty công nghệ — trong nước lẫn quốc tế — là bài toán cấu trúc dữ liệu. Đây là môn có lợi ích trực tiếp nhất khi đi tìm việc.
  • Backend và hệ thống lớn: chọn đúng cấu trúc là khác biệt giữa trang chạy trong 50 mili giây và trang chạy trong 5 giây; bộ đệm (cache) như Redis thực chất là những bảng băm và danh sách được tối ưu.
  • Cơ sở dữ liệu: hiểu chỉ mục là cây B để biết khi nào truy vấn nhanh, khi nào chậm, khi nào nên thêm chỉ mục.
  • Game, lập trình thi đấu, dữ liệu và AI: cây chia không gian để phát hiện va chạm; cây phân đoạn ở Olympic Tin học và ICPC; tìm vector gần nhất cho hệ gợi ý và mô hình ngôn ngữ.

Học xong làm được gì, bắt đầu từ đâu

Sau môn này bạn có thể:

  • chọn đúng cấu trúc dữ liệu cho một bài toán, và giải thích vì sao;
  • tự cài đặt mảng động, danh sách liên kết, ngăn xếp, hàng đợi, bảng băm, cây tìm kiếm, đống;
  • ước lượng chi phí của từng thao tác bằng ký hiệu O lớn;
  • tìm ra vì sao một đoạn code chậm, và sửa nó bằng cách đổi cấu trúc;
  • tự tin đi qua vòng phỏng vấn lập trình cơ bản.

Nên biết trước: lập trình được một ngôn ngữ — viết hàm, vòng lặp, đệ quy, dùng mảng. Python, Java hay C++ đều được; C hoặc C++ giúp thấy rõ con trỏ và bộ nhớ hơn. Chưa vững thì đi qua chủ đề Programming trước.

Bắt đầu trên OpenER: trang chủ đề Data Structures and Algorithms có các khóa học đã chọn lọc, và hướng dẫn học gợi ý thứ tự đi qua chúng. Lời khuyên cho môn này: tự cài từng cấu trúc ít nhất một lần, dù ngôn ngữ đã có sẵn. Vẽ các con trỏ ra giấy trước khi viết code, và dùng các trang mô phỏng trực quan — như VisuAlgo — để xem cấu trúc thay đổi qua từng bước.

Tài liệu tham khảo

  • Robert Sedgewick, Kevin Wayne — Algorithms (Đại học Princeton), kèm trang web và khóa học trực tuyến miễn phí.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein — Introduction to Algorithms (CLRS).
  • Pat Morin — Open Data Structures, sách mở đọc miễn phí.
  • MIT 6.006 Introduction to Algorithms — bài giảng mở trên MIT OpenCourseWare.
  • UC Berkeley CS 61B Data Structures; Stanford CS 106B Programming Abstractions.
  • VisuAlgo (Đại học Quốc gia Singapore) — mô phỏng trực quan các cấu trúc dữ liệu và thuật toán.

Ban biên tập OpenER, “Cấu trúc dữ liệu và giải thuật: sắp xếp dữ liệu sao cho máy tìm nhanh”, OpenER, 2026. Phát hành theo CC BY 4.0: được chia sẻ, chỉnh sửa, kể cả thương mại, miễn ghi công tác giả và dẫn link bài gốc.