Trong quá trình học tập và tìm hiểu, có thể các bạn rất quen thuộc và hay sử dụng các phép toán trên mảng, xâu kí tự. Trong bài viết này, mình sẽ giới thiệu với bạn 1 cấu trúc dữ liệu khá mạnh, giúp giải quyết nhiều bài toán với tốc độ cao và cách cài đặt đơn giản. Cấu trúc dữ liệu này mang tên Map [trong C# hay Python thì gọi là Dictionary].
Map là gì?
Trong 1 số ngôn ngữ lập trình, Map được gọi là Dictionary [như Python hay C#]. Trong khuôn khổ bài viết này, mình dùng từ map do thông thạo với C++ và Java.
Các cấu trúc dữ liệu như mảng hay xâu kí tự, khi truy xuất dữ liệu bạn sẽ sử dụng một tham số gọi là chỉ số, ví dụ như arr[1], str[2], … Đối với cấu trúc dữ liệu map, để truy xuất dữ liệu bạn sẽ sử dụng một tham số gọi là key
Cấu trúc dữ liệu kiểu map là một cấu trúc dữ liệu ánh xạ giữa cái gọi là khoá [key] sang giá trị của khoá đó [gọi là value]
Trong cấu trúc dữ liệu này, mỗi một key sẽ nhận một giá trị khác nhau.
Ứng dụng
Ứng dụng của map có rất nhiều. Mình đưa ra 1 số bài toán cơ bản nhé:
- Cho một danh sách các số điện thoại kèm theo tên của chủ thuê bao đó. Yêu cầu đầu vào là một số điện thoại [key], hãy đưa ra tên của chủ thuê bao [value]
- Cho danh sách thể hiện lịch sử đi muộn của các nhân viên một công ty nào đó. Hãy tìm xem nhân viên [key] nào có số lần đi muộn [value] nhiều nhất?
- Cho một danh sách các IP kèm theo các domain. Hãy trả ra ip [value] tương ứng domain [key] hoặc ngược lại trong thời gian nhanh nhất?
Với các bài toán này, bạn có thể sử dụng 2 mảng dữ liệu có cùng độ dài. Một mảng bạn lưu danh sách key, một mảng bạn lưu danh sách các value tương ứng với key đó [cùng chỉ số truy cập mảng]. Khi bạn cần tìm value của một key nào đó, bạn duyệt mảng key, tìm chỉ số của phần tử trong mảng có giá trị bằng key cần tìm rồi trả ra giá trị tương ứng ở mảng value. Mã giả của đoạn code này như sau:
for [int i=0; i