Cấu trúc dữ liệu thần thánh mang tên map

     

Trong quy trình học tập cùng tìm hiểu, bao gồm thể các bạn rất quen thuộc và thường dùng các phép toán bên trên mảng, xâu kí tự. Trong bài viết này, bản thân sẽ ra mắt với chúng ta 1 cấu tạo dữ liệu tương đối mạnh, giúp giải quyết nhiều việc với tốc độ cao và cách cài đặt đơn giản. Cấu tạo dữ liệu này với tên bản đồ (trong C# tốt Python thì hotline là Dictionary).

Bạn đang xem: Cấu trúc dữ liệu thần thánh mang tên map

Map là gì?

Trong 1 số ngôn từ lập trình, bản đồ được gọi là Dictionary (như Python tốt C#). Trong khuôn khổ nội dung bài viết này, mình dùng từ bản đồ do thông thạo với C++ với Java.

Các kết cấu dữ liệu như mảng giỏi xâu kí tự, khi truy xuất dữ liệu bạn sẽ sử dụng một tham số call là chỉ số, ví dụ như arr<1>, str<2>, … Đối với cấu tạo dữ liệu map, nhằm truy xuất dữ liệu các bạn sẽ sử dụng một tham số call là key

Cấu trúc tài liệu kiểu map là một cấu tạo dữ liệu ánh xạ giữa dòng gọi là khoá (key) sang cực hiếm của khoá kia (gọi là value)

Trong cấu tạo dữ liệu này, mỗi một key đã nhận một cực hiếm khác nhau.

Xem thêm: Cách Viết Lưu Bút Hài Hước, Hóm Hỉnh Cho Học Sinh Cuối Khóa

*

Ứng dụng

Ứng dụng của maps có siêu nhiều. Mình chuyển ra một số ít bài toán cơ bạn dạng nhé:

Cho một danh sách các số smartphone kèm theo thương hiệu của nhà thuê bao đó. Yêu mong đầu vào là một số điện thoại (key), hãy giới thiệu tên của nhà thuê bao (value)Cho list thể hiện lịch sử hào hùng đi muộn của các nhân viên một công ty nào đó. Hãy kiếm tìm xem nhân viên (key) nào tất cả số lần đi muộn (value) nhiều nhất?Cho một danh sách những IP kèm theo các domain. Hãy trả ra ip (value) tương ứng domain (key) hoặc trái lại trong thời hạn nhanh nhất?

Với những bài toán này, bạn cũng có thể sử dụng 2 mảng tài liệu có cùng độ dài. Một mảng bạn lưu list key, một mảng bạn lưu danh sách những value tương ứng với key kia (cùng chỉ số truy cập mảng). Khi bạn cần kiếm tìm value của một key như thế nào đó, chúng ta duyệt mảng key, tìm kiếm chỉ số của thành phần trong mảng có giá trị bởi key bắt buộc tìm rồi trả ra giá trị tương ứng ở mảng value. Mã mang của đoạn code này như sau:

for (int i=0; i

Với đoạn mã như trên, độ phức tạp thuật toán đang là O(N) (do bạn phải trông nom cả mảng keysArray để tìm mẫu key các bạn muốn). Để tăng tốc độ cho đoạn mã này, chúng ta cũng có thể cải tiến hàm tìm kiếm theo cách thức tìm tìm nhị phân (với đk mảng keysArray vẫn được sắp tới xếp). Tất yếu cách có tác dụng này vẫn tốn công thiết đặt hơn không ít lần so với vấn đề bạn sử dụng maps (hay dictionary) thông qua dòng lệnh duy nhất sau:

if (mymap.find(key) != mymap.end()) return mymap;else return "notFound";

Không chỉ cần dễ cài đặt và sử dụng, câu hỏi sử dụng bản đồ còn đáp ứng tốc độ chạy chương trình tương đối cao (có chút biệt lập giữa 1 vài cách thiết đặt map của các ngôn ngữ hoặc thư viện, nhưng chắc chắn là ngon rộng mình tự sở hữu rồi :D)

Các loại maps và đặc điểm:

Nhìn chung tất cả 2 loại map, phụ thuộc cách cài đặt của map. Một loại là map được thiết lập dựa bên trên cây đỏ black (red-black tree), một nhiều loại là map được thiết lập dựa trong bảng băm (hashtable)

Với C++, map là loại map được thiết lập dựa trên cây đỏ đen, còn unordered_map là loại bản đồ được cài đặt dựa trên nguyên tắc Hash. Với Java, TreeMap là loại map được cài đặt bởi cây, còn HashMap là loại map đc setup bởi bảng băm (hash table)

Tree map:Map được cài bởi cây đỏ đen. Mỗi một node vào cây có một key và một value, trỏ vào 2 node bên trái và mặt phải. Giá trị key của node mặt trái bé dại hơn cực hiếm key sinh sống node thân phụ và bé dại hơn giá trị key nghỉ ngơi node mặt phải.Độ phức tạp thuật toán của các phép toán thêm một node, kéo ra giá trị của một key là O(logn)
*
HashMap

Map được thiết đặt dựa trên nguyên lýHashing– băm. Để gọi vềHashing, họ cần rứa được 3 khái niệm:Hashfunction,hashvaluebucket.Hash function, hay còn gọi là hàm băm, là 1 trong những hàm nhưng khi ta đem đầu vào là 1 trong giá trị bất kỳ thì làm việc đầu ra, hash fuction sẽ cho ta một dãy code – được hotline làhash value. Mỗi nguồn vào chỉ códuy nhấtmột hash value.

Xem thêm: Nghị Luận: Thế Nào Là Cuộc Sống Có Ý Nghĩa Cuộc Sống Của Mỗi Con Người

*

Bucketlà khu vực mà họ lưu trữ các cặp key-value.Độ tinh vi thuật toán phép thêm và lấy dữ liệu là O(1).Bạn hoàn toàn có thể tìm phát âm và nghiên cứu và phân tích sự không giống nhau giữa 2 loại bản đồ này tại một số link như:

https://www.geeksforgeeks.org/map-vs-unordered_map-c/

hay

https://stackoverflow.com/questions/2444359/what-is-the-difference-between-a-hashmap-and-a-treemap

Cách sử dụng:

Đa phần map có một trong những phương thức cơ bạn dạng và giải pháp sử dụng tương tự như nhau ở 1 số ít ngôn ngữ:

Khai báo:map(với C++) hoặcDictionaryvới C# hoặcTreeMap trong JavaThêm một cặp key/value: cần sử dụng phương thứcinsert(key, value)hoặcmap = valueTruy cập: dùngmapKiểm tra bản đồ có chứa key nào đó không: dùngfind(key)(với C++) hoặcmap.containsKey(với C#)

Bài tập ứng dụng:

Hãy test dùng maps để giải quyết các bài tập thuật toán sinh sống trong này https://thietkewebshop.vn/learning/detail/thuat-toan-can-banhoặc https://thietkewebshop.vn/learning/detail/thu-vien-chuan-cppbạn nhé.