Trong quá trình phát triển ứng dụng web, việc chuyển đổi dữ liệu từ mảng sang dạng bảng băm (Dictionary / Hash Map) bằng phương thức reduce hoặc vòng lặp để phục vụ tìm kiếm là một kỹ thuật phổ biến. Hãy giải thích lợi ích về độ phức tạp thuật toán của kỹ thuật này.

Question

Accepted Answer

Bài toán tìm kiếm trên mảng thông thường
Giả sử bạn có một mảng chứa 10,000 đối tượng người dùng. Nếu bạn cần tìm kiếm thông tin của một người dùng dựa vào userId nhiều lần trong ứng dụng, việc sử dụng phương thức Array.prototype.find() hoặc Array.prototype.filter() sẽ có độ phức tạp thời gian là $O(N)$ cho mỗi lần tìm kiếm. Nếu thực hiện tìm kiếm trong một vòng lặp khác, độ phức tạp tổng thể sẽ tăng lên mức $O(N^2)$, gây nghẽn cổ chai hiệu năng.
Giải pháp chuyển đổi sang Hash Map (Index Mapping)
Chúng ta chuyển đổi mảng thành một đối tượng (Dictionary) với khóa là userId và giá trị là đối tượng người dùng đó. Thao tác này chỉ tốn $O(N)$ ở bước khởi tạo ban đầu, nhưng các lần tra cứu (Lookup) sau đó sẽ đạt độ phức tạp $O(1)$.
Ví dụ cài đặt thực tế
const users = [
  { id: 'u1', name: 'An' },
  { id: 'u2', name: 'Binh' },
  { id: 'u3', name: 'Cuong' }
];

// Chuyển mảng thành Hash Map
const userMap = users.reduce((acc, user) => {
  acc[user.id] = user;
  return acc;
}, {});

// Tra cứu cực nhanh với độ phức tạp O(1)
const targetUser = userMap['u2']; 
console.log(targetUser); // { id: 'u2', name: 'Binh' }
Lưu ý kinh nghiệm thực chiến

Kỹ thuật này đánh đổi không gian bộ nhớ (Space Complexity tăng thêm $O(N)$ để lưu trữ đối tượng map) lấy tốc độ xử lý thời gian (Time Complexity giảm xuống $O(1)$).
Chỉ nên áp dụng khi dữ liệu dạng tĩnh hoặc ít thay đổi, và cần thực hiện các thao tác tra cứu lặp đi lặp lại nhiều lần trong vòng đời của component.

Bài toán tìm kiếm trên mảng thông thường

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi arrays liên quan cùng chủ đề