Searching Algorithms & Hashing (Day 34) | FE Master

🎯 Mò kim đáy bể như thế nào cho nhanh?

Tìm kiếm là thao tác phổ biến nhất trong phần mềm (Google Search, Ctrl+F, tra từ điển...).

1. Linear Search (Tìm kiếm Tuyến tính)

Cách "ngây thơ" nhất: Duyệt từ đầu đến cuối for (i=0; i < n; i++).

Độ phức tạp: O(N).
Ưu điểm: Dữ liệu lộn xộn cũng tìm được. Không cần sắp xếp.

2. Binary Search (Tìm kiếm Nhị phân) - "Chia đôi nỗi sầu"

Điều kiện bắt buộc: Mảng PHẢI ĐƯỢC SẮP XẾP trước.

Giống như tra từ điển: Bạn không lật từng trang từ trang 1. Bạn mở đại trang giữa. Nếu từ cần tìm vần T (sau M) -> Bạn vứt bỏ nửa đầu quyển sách, chỉ tìm ở nửa sau. Cứ thế chia đôi mãi.

Ví dụ: Tìm số 42 trong mảng [10, 20, 30, 40, 50, 60, 70]

Low = 0, High = 6.
Bước 1: Giữa (Mid) = (0+6)/2 = 3. Giá trị A[3] = 40.
42 > 40 -> Tìm ở bên phải (bỏ bên trái).
Low mới = Mid + 1 = 4.
Bước 2: Low = 4, High = 6. Mid = (4+6)/2 = 5. Giá trị A[5] = 60.
42 < 60 -> Tìm ở bên trái.
High mới = Mid - 1 = 4.
Bước 3: Low = 4, High = 4. Mid = 4. Giá trị A[4] = 50.
42 < 50 -> High = 3.
Bước 4: Low (4) > High (3). -> Tìm kiếm thất bại. Không có số 42.

Độ phức tạp: O(log N). Siêu nhanh. (Với 1 tỷ phần tử, chỉ cần tìm tối đa 30 lần).

3. Hashing (Băm) - Tìm kiếm O(1)

Kỹ thuật "thần thánh" biến Key thành Index mảng.

Hàm băm (Hash Function): h(x) = x % 10.

Cần lưu số 15 -> h(15) = 5 -> Lưu vào ô số 5.
Cần tìm số 15 -> Tính h(15) = 5 -> Nhảy đến ô 5 lấy ra ngay. Không cần For, không cần chia đôi. Mất đúng 1 nhịp.

Xử lý Va chạm (Collision)

Chuyện gì xảy ra nếu cần lưu số 25? 25 % 10 = 5. Ôi thôi, ô số 5 đã có số 15 ngồi rồi!

Đây là xung đột (Collision). Có 2 cách giải quyết:

Chaining (Dùng danh sách liên kết): Tại ô số 5, ta móc thêm một cái xích. Ô 5 chứa danh sách: [15] -> [25]. Khi tìm thì phải duyệt cái xích này.
Open Addressing (Địa chỉ mở): Ô 5 bận rồi hả? Thử ô 6 xem? Ô 6 bận thì thử ô 7. (Linear Probing).

4. Ứng dụng thực tế: Index & Hash

Bạn có bao giờ tự hỏi database chứa cả triệu dòng mà tìm mất có 0.01s không?

Database Indexing (B-Tree): Giống mục lục sách. Giúp tìm kiếm O(log N) thay vì O(N).
HashMap/Dictionary: Dùng trong lập trình để lưu Cache, Session. (Ví dụ: users['user_123'] để lấy thông tin user ngay lập tức).

🎯 Mò kim đáy bể như thế nào cho nhanh?

Tìm kiếm là thao tác phổ biến nhất trong phần mềm (Google Search, Ctrl+F, tra từ điển...).

1. Linear Search (Tìm kiếm Tuyến tính)

Cách "ngây thơ" nhất: Duyệt từ đầu đến cuối for (i=0; i < n; i++).

Độ phức tạp: O(N).
Ưu điểm: Dữ liệu lộn xộn cũng tìm được. Không cần sắp xếp.

2. Binary Search (Tìm kiếm Nhị phân) - "Chia đôi nỗi sầu"

Điều kiện bắt buộc: Mảng PHẢI ĐƯỢC SẮP XẾP trước.

Ví dụ: Tìm số 42 trong mảng [10, 20, 30, 40, 50, 60, 70]

Low = 0, High = 6.
Bước 1: Giữa (Mid) = (0+6)/2 = 3. Giá trị A[3] = 40.
42 > 40 -> Tìm ở bên phải (bỏ bên trái).
Low mới = Mid + 1 = 4.
Bước 2: Low = 4, High = 6. Mid = (4+6)/2 = 5. Giá trị A[5] = 60.
42 < 60 -> Tìm ở bên trái.
High mới = Mid - 1 = 4.
Bước 3: Low = 4, High = 4. Mid = 4. Giá trị A[4] = 50.
42 < 50 -> High = 3.
Bước 4: Low (4) > High (3). -> Tìm kiếm thất bại. Không có số 42.

Độ phức tạp: O(log N). Siêu nhanh. (Với 1 tỷ phần tử, chỉ cần tìm tối đa 30 lần).

3. Hashing (Băm) - Tìm kiếm O(1)

Kỹ thuật "thần thánh" biến Key thành Index mảng.

Hàm băm (Hash Function): h(x) = x % 10.

Cần lưu số 15 -> h(15) = 5 -> Lưu vào ô số 5.
Cần tìm số 15 -> Tính h(15) = 5 -> Nhảy đến ô 5 lấy ra ngay. Không cần For, không cần chia đôi. Mất đúng 1 nhịp.

Xử lý Va chạm (Collision)

Chuyện gì xảy ra nếu cần lưu số 25? 25 % 10 = 5. Ôi thôi, ô số 5 đã có số 15 ngồi rồi!

Đây là xung đột (Collision). Có 2 cách giải quyết:

Chaining (Dùng danh sách liên kết): Tại ô số 5, ta móc thêm một cái xích. Ô 5 chứa danh sách: [15] -> [25]. Khi tìm thì phải duyệt cái xích này.
Open Addressing (Địa chỉ mở): Ô 5 bận rồi hả? Thử ô 6 xem? Ô 6 bận thì thử ô 7. (Linear Probing).

4. Ứng dụng thực tế: Index & Hash

Bạn có bao giờ tự hỏi database chứa cả triệu dòng mà tìm mất có 0.01s không?

Database Indexing (B-Tree): Giống mục lục sách. Giúp tìm kiếm O(log N) thay vì O(N).
HashMap/Dictionary: Dùng trong lập trình để lưu Cache, Session. (Ví dụ: users['user_123'] để lấy thông tin user ngay lập tức).

Thuật toán Tìm kiếm (Searching) & Hashing

lesson.content.title

🎯 Mò kim đáy bể như thế nào cho nhanh?

1. Linear Search (Tìm kiếm Tuyến tính)

2. Binary Search (Tìm kiếm Nhị phân) - "Chia đôi nỗi sầu"

Ví dụ: Tìm số 42 trong mảng [10, 20, 30, 40, 50, 60, 70]

3. Hashing (Băm) - Tìm kiếm O(1)

Xử lý Va chạm (Collision)

4. Ứng dụng thực tế: Index & Hash

Thuật toán Tìm kiếm (Searching) & Hashing

lesson.content.title

🎯 Mò kim đáy bể như thế nào cho nhanh?

1. Linear Search (Tìm kiếm Tuyến tính)

2. Binary Search (Tìm kiếm Nhị phân) - "Chia đôi nỗi sầu"

Ví dụ: Tìm số 42 trong mảng [10, 20, 30, 40, 50, 60, 70]

3. Hashing (Băm) - Tìm kiếm O(1)

Xử lý Va chạm (Collision)

4. Ứng dụng thực tế: Index & Hash