Sử dụng hiệu quả std::map vs std::unorder_map

Chào mọi người, hôm nay mình sẽ bàn một chút về container std::map/unorder_map. Thông thường nếu muốn lưu trữ một kiểu dữ liệu theo cặp key-value chúng ta sẽ dùng std::map hoặc std::unordermap. Vậy std::mapstd::unorder_map có gì khác nhau? Lúc nào thì nên sử dụng std::map thay vì std::unorder_map và ngược lại?

Để sử dụng chúng một cách hiệu quả, trước hết chúng ta hãy tìm hiểu về bản chất của nó là gì. Về cơ bản thì std::map sử dụng nhóm nhạc BTS à nhầm cây nhị phân BST: red-black tree (cây tìm kiếm nhị phân tự cân bằng: self-balancing binary search tree ) còn std::unorder_map chúng sử dụng hash table. Mình sẽ bàn sơ qua về hashing và hash table để chúng ta có thể hình dung được bên dưới std::unorder_map được lập trình như nào

Hashing và Hash Table là gì?

Giả sử bạn có một object và bạn muốn gán cho object đó một cái key để dễ dàng tìm kiếm, bạn sẽ có một cặp key-value. Ví dụ một tập bạn muốn lưu tên và số điện thoại: name-phone number

  • John Smith: 521-1234
  • Lisa Smith: 521-8976
  • Sandra Dee: 521-9655

Bạn vẫn có thể lưu tập này dưới dạng mảng 2 chiều [string][string] tuy nhiên nếu muốn tìm kiếm một phần tử trong cái mảng đó bạn phải loop tuần tự qua mảng mới truy xuất kết quả ra được và thời gian thực thi là O(n). Vậy phải làm sao để tối ưu tốc độ truy cập, tìm kiếm cho mảng này?

Lúc này các cụ đã nghĩ ra một cách là sao mình không tìm cách chuyển cái key là string sang interger, lúc này cái mảng nó sẽ là [interger][string] và mỗi lần truy cập sẽ truy cập trực tiếp tới phần tử đó luôn và thời gian sẽ chỉ còn là O(1).  Và cái cách dùng để chuyển tên từ string sang interger đó gọi là hashing:

key = Hash(name)

source: https://en.wikipedia.org/wiki/Hash_table

Bây giờ tên của John Smith, Lisa Smith và Sandra Dee được chuyển đổi tương ứng lần lượt là 01, 02 và 14. Nếu bạn muốn tìm kiếm số điện thoại của Sandra Dee, trước hêt chỉ cần hashing tên Sandra Dee -> ra được số 14, trực tiếp truy cập đến index 14 là có được số điện thoại của Sandra Dee mà không cần phải loop từ đầu đến cuối

Ví dụ trên đã cung cấp cho bạn được một cái nhìn cơ bản và tổng quát về hashing, vậy còn hash table là gì? Hash Table đơn giản là cái bảng để lưu những giá trị đã hash tương ứng với giá trị.

Chúng ta đã hiểu sơ được bản chất của std::unorder_map, tiếp theo mình sẽ bàn về sự khác nhau giữa std::mapstd::unorder_map.

Sự khác nhau giữa std::map và std::unorder_map

Dưới đây chúng ta có một bảng tóm tắt sự khác nhau giữa map và unorder_map

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

[table id=2 /]

Chính vì sự khác nhau giữa Red-Black Tree và Hash Table nên chúng ta sẽ có sự khác nhau cơ bản giữa std::mapstd::unorder_map.

Thời gian tìm kiếm một phần tử

std::map sử dụng Red-Black Tree nên để kiếm một phần tử nó phải duyệt (traversal) qua các phần tử khác, thời gian để kiếm sẽ là O(log(n)). Đối với std::unorder_map bởi vì nó sử dụng hash table, như đã phân tích ở trên, thời gian trung bình để nó tìm một phần tử là O(1) có nghĩa là ngay tức thì. Tuy nhiên, nếu hash table không được implement tốt, đối với những dữ liệu rất lớn (từ vài chục triệu phần tử trở lên) hash table sẽ phải đối mặt với những vấn đề như: thời gian thực thi hàm hash, thời gian compare các key bị trùng hash, collision…trường hợp tệ nhất sẽ là O(n)

Hình dưới đây sẽ cho bạn thấy sự khác nhau về tốc độ tìm kiếm giữa std::mapstd::unorder_map khi số lượng phần tử là khoảng 32 triệu

source: https://www.youtube.com/watch?v=M2fKMP47slQ

Thứ tự các phần tử

Đúng như tên gọi cũng như cách implement ở bên dưới, các phần tử trong std::unorder_map không được sắp xếp, lộn xộn. Còn std::map vì được implement bằng Red-Black Tree nên các phần tử đã được sắp xếp theo thứ tự.

Thời gian insert và delete

std::map là một cây nhị phân, nên mỗi lần insert và delete nó sẽ phải mất một thời gian là log(n) sau đó phải cân bằng lại cây. Còn đối với std::unorder_map, chỉ cần hash key ra và sau đó insert hoặc delete trực tiếp nên thời gian thực thi lý tưởng sẽ là O(1)

Bộ nhớ

Như các bạn thấy ở hình đầu tiên của bài viết, hash table sẽ có những chỗ trống không được lấp đầy vì các key khi hash ra giá trị của chúng không liên tục với nhau, nên nó sẽ chiếm bộ nhớ không cần thiết. Còn đối với BST, thì bộ nhớ sẽ tương ứng với số lượng phần tử. Vì vậy nếu lưu dữ liệu với std::map về mặt cơ bản sẽ lợi về bộ nhớ hơn so với std::unorder_map.

Kết luận

Khi nào nên sử dụng std::map?

  • Bạn muốn dữ liệu của mình được sắp xếp
  • Bạn muốn in/truy xuất dữ liệu theo thứ tự
  • Bạn muốn sử dụng ít memory hơn để lưu trữ dữ liệu lớn

Khi nào nên sử dụng std::unorder_map?

  • Bạn muốn có tốc độ tìm kiếm cũng như insert/delete nhanh mà không quan tâm đến thứ tự của các phần tử

Các bạn thấy đấy std::mapstd::unorder_map về tên gọi chúng có thể khiến ta nhầm lần là chúng giống nhau (chỉ khác về phần unorder) nhưng về bản chất chúng lại rất khác nhau. Vì vậy, chúng ta nên tìm hiểu kỹ một chút để có thể đạt được hiệu năng tốt nhất cho từng trường hợp. Đối với dữ liệu nhỏ (khoảng mấy chục ngàn phần tử trở xuống) thì sự khác biệt ở tốc độ tìm kiếm thực sự không nhiều nên chúng ta có thể sử dụng std::map hoặc std::unorder_map. Tuy nhiên đối với dữ liệu lớn thì chúng ra phải đánh đổi giữa tốc độ tìm kiếm và bộ nhớ, nếu muốn tiết kiệm bộ nhớ thì sử dụng std::map còn nếu muốn tốc độ “bàn thờ” thì hãy sử dụng std::unorder_map.

 

Xem thêm: Lưu ý khi sử dụng operator[] của std::map

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *