+5

Unordered_map và unordered_set

I. Unordered_map

1. Đặt vấn đề

Như chúng ta đã biết, mapmap dùng để lưu trữ dữ liệu dưới dạng key - value, và các dữ liệu của chúng ta được tự động sắp xếp theo thứ tự. Về cơ bản thì mapmap sử dụng cây nhị phân BST: red-black tree (cây tìm kiếm nhị phân tự cân bằng). Ngoài ra, nếu các bạn tìm hiểu sâu hơn về kiểu dữ liệu này sẽ phát hiện còn có thêm một kiểu dữ liệu với cái tên khá tương đồng: unordered_mapunordered\_map. Qua tên thì chúng ta cũng đoán được phần nào về kiểu dữ liệu này rồi nhỉ, có thể tạm hiểu là mapmap nhưng không thứ tự!

2. Unordered_map - Những điều có thể bạn chưa biết

Cải tiến hơn so với mapmap, unordered_mapunordered\_map lưu trữ dữ liệu thông qua một bảng hashhash (hashtablehash table).

Về cơ bản, hashhash chỉ một quá trình mã hóa theo một phương thức nào đó biến một bản rõ (plaintext) thành bản mã (ciphertext) với mong muốn không thể giải mã ngược lại. Mục đích để bảo mật thông tin một cách tốt hơn. Trong kiểu dữ liệu unordered_mapunordered\_map, thay vì lưu các biến dạng stringstringstring-string, thì chúng ta sẽ lưu các biến về dạng hashidstringhashid-string. Việc làm này có một ưu điểm lớn trong việc tìm kiếm các phần tử.

Ví dụ, trong mapmap bạn lưu các biến với keykey là tên người và valuevalue là món ăn yêu thích, như vậy mỗi khi cần tìm kiếm một người có món ăn yêu thích là gì chúng ta cần thực hiện với độ phức tạp O(n)O(n). Tương ứng trong unordered_mapunordered\_map, chúng ta lưu dạng keykeyhashidhashid của tên người, valuevalue vẫn là tên món ăn, như vậy khi tìm kiếm, ta chỉ cần thêm một bước là hashinghashing tên người, sau đó tìm kiếm theo keykeyhashidhashid tương ứng sẽ đưa độ phức tạp về O(1)O(1).

3. So sánh giữa map và unordered_map

3.1. Sự sắp xếp

Vì sử dụng Red-Black Tree nên các phần tử trong mapmap được săp xếp theo một thứ tự theo nhu cầu người sử dụng. Đối với kiểu dữ liệu unordered_mapunordered\_map thì các phần tử không được sắp xếp.

3.2. Thời gian thao tác với các phần tử

Do mapmap bản chất là một cây nhị phân, nên mỗi lần thực hiện thao tác với các phần tử, chẳng hạn insert hoặc delete chúng ta sẽ cần sử dụng một khoảng thời gian với độ lớn là O(log(n))O(log(n)) (sau đó mapmap cần thêm thao tác cân bằng lại cây). Đối với kiểu dữ liệu unordered_mapunordered\_map, chúng ta chỉ cần hash key ra và sau đó insert hoặc delete trực tiếp nên thời gian thực thi được đưa về lý tưởng là O(1)O(1).

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

Trong kiểu dữ liệu mapmap, vì phải tìm kiếm tuần tự, duyệt qua các phần tử nên thời gian tìm kiếm một phần tử tùy ý là O(log(n))O(log(n)). Đối với unordered_mapunordered\_map, chúng ta chỉ cần thêm một bước hashing sẽ có thể đưa thời gian tìm kiếm trở về O(1)O(1).

3.4. Bộ nhớ sử dụng

Đối với cây BST trong mapmap, bộ nhớ tương ứng với số lượng phần tử lưu trữ. Đây là một ưu điểm so với không gian lưu trữ dạng hashtablehash table vì có nhiều các chỗ trống không được lấp đầy.

4. Sự lựa chọn giữa map và unodered_map

Với các đặc điểm trên, chúng ta có thể thấy mapmap phù hợp trong các bài toán chú trọng về thứ tự các phần tử, còn đối với những bài toán với nhu cầu tìm kiếm cao hơn, chúng ta nên sử dụng unordered_mapunordered\_map. Tuy nhiên, việc sử dụng unordered_mapunordered\_map sẽ cần thêm thao tác xây dựng hash table nên cần thận trọng, vì đối với những dữ liệu lớn, chúng ta cần phải quan tâm đến các yếu tố như thời gian thực thi hàm hash, rủi ro trùng kết quả hash, cũng như những kết quả hash đặc biệt (tuy khác nhau nhưng có thể bị hệ thống hiểu lầm thành cùng một dữ liệu), ...

II. Unordered_set

1. Đặt vấn đề

Tương tự với unordered_mapunordered\_map, ta cũng có kiểu dữ liệu unordered_setunordered\_set. Khác với việc tự sắp xếp thứ tự của setset, unordered_setunordered\_set sử dụng một hàm hashhash, hình thành ánh xạ với các keykey và sắp xếp chúng vào các nhóm khác nhau. Ví dụ:

  • Đối với setset: Input: 1,8,2,5,3,91,8,2,5,3,9 Output:1,2,3,5,8,91,2,3,5,8,9
  • Đối với unordered_setunordered\_set: Input:1,8,2,5,3,91,8,2,5,3,9 Output:9,3,1,8,2,59, 3, 1, 8, 2, 5(thứ tự bị ảnh hưởng bởi hàm hashhash

2. So sánh giữa set và unordered_set

2.1. Sự sắp xếp

Kiểu dữ liệu setset mặc định sẽ sắp xếp các phần tử theo thứ tự tăng dần hoặc theo thứ tự do người sử dụng quy định. Đối với unordered_setunordered\_set, nó sẽ sắp xếp các phần tử theo hàm hashhash (ánh xạ các phần tử vào các nhóm).

2.2. Tìm kiếm phần tử

Độ phức tạp thời gian ở việc tìm kiếm một phần tử trong setsetO(log(n))O(log(n)). Trong khi ở unordered_setunordered\_set, chúng ta có trường hợp tốt nhất là O(1)O(1) và trường hợp xấu nhất là O(n)O(n).

2.3. Thời gian thao tác với các phần tử

mapmap là kiểu dữ liệu tự sắp xếp phần tử, nên thời gian thao tác như insert hoặc delete phần tử bằng log(n)+rebalance_timelog(n) + rebalance\_time, bởi vì sau đó chúng ta cần cân bằng lại các phần tử theo thứ tự sắp xếp. Đối với unordered_setunordered\_set chúng ta cũng có trường hợp tốt nhất và xấu nhất giống như việc tiềm kiếm phần tử, lần lượt là O(1)O(1)O(n)O(n)

3. Sự lựa chọn giữa set và unordered_set

Đối với những bài toán cần chú ý yếu tố thứ tự của phần tử, thao tác phần tử theo thứ tự sắp xếp, hoặc cần để ý đến những phần tử liền kề (phần tử với giá trị lớn hơn phía sau, giá trị nhỏ hơn phía trước) thì chúng ta nên sử dụng kiểu dữ liệu setset. Ngược lại, đối với những bài toán chưa yêu cầu sự sắp xếp, ưu tiên thao tác với phần tử mà không ảnh hưởng đến các phần tử khác thì chúng ta có thể sử dụng unordered_setunordered\_set. Ngoài ra việc vận dụng linh hoạt hai kiểu dữ liệu trên có thể khiến lời giải trở nên gọn gàng và dễ hiểu.

III. Tài liệu tham khảo


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.