Tìm hiểu cấu trúc dữ liệu ArrayMap trong Android

Bài viết được sự cho phép của tác giả Sơn Dương

Trong bài viết này, mình sẽ chỉ cho bạn tại sao và khi nào sử dụng loại dữ liệu ArrayMap để tối ưu hóa hiệu suất ứng dụng Android một cách hiệu quả.

Bất cứ khi nào bạn cần lưu trữ dữ liệu dạng Key => Value, có lẽ HashMap là kiểu dữ liệu đầu tiên bạn nghĩ tới phải không?

Với cấu trúc dữ liệu kiểu HashMap khá là linh hoạt, sử dụng được ở mọi nơi mà chúng ta lại không cần bận tâm quá nhiều về những “tác dụng phụ” của nó.

Nhưng bạn có để ý là mỗi khi sử dụng HashMap, Android Studio lại đưa ra gợi ý rằng bạn nên sử dụng ArrayMap để thay thế Hashmap. Bạn có biết tại sao không? Mình cũng không biết Vậy thì cùng nhau tìm hiểu nhé!

Tối ưu hóa việc sử dụng ArrayMap và SparseArray

Phần này, mình sẽ chỉ cho bạn biết khi nào chúng ta nên sử dụng ArrayMap và cách thức hoạt động của hai kiểu cấu trúc dữ liệu này.

Giới thiệu HashMap và ArrayMap

HashMap nằm trong gói java.utils.HashMap, trong khi ArrayMap nằm trong gói android.support.v4.util.ArrayMap. Do ArrayMap nằm trong gói support.v4 nên nó cũng được hỗ trợ trên các phiên bản Android cũ.

ArrayMap là kiểu dữ liệu cấu trúc dạng generic key => value được thiết kế để tối ưu hóa bộ nhớ hơn so với HashMap truyền thống.

ArrayMap giữ ánh xạ của nó trọng một cấu trúc mảng dữ liệu (là 1 mảng số nguyên là mã băm của mỗi item) và một mảng đối tượng của key -> value. Điều này tránh yêu cầu phải tạo ra thêm Object mỗi khi thêm một entry vào mảng. ArrayMap cũng kiểm soát kích thước của mảng nhanh gọn hơn. Vì chúng ta chỉ cần sao chép các entry trong mảng mà không phải xây dựng lại bảng mã băm.

Lưu ý: không dùng ArrayMap cho cấu trúc dữ liệu có số lượng phần tử lớn. Nhìn chung, nó chậm hơn HashMap truyền thống. Vì ArrayMap dùng thuật toán binary search để tìm kiếm. Thêm mới và xóa phần tử đều yêu cầu phải chèn và xóa các mảng entry.

Với các mảng lưu trữ lên đến hàng trăm phần tử thì sự chênh lệch về hiệu suất dưới 50%. Theo cá nhân mình thì con số này không đáng kể.

  Top 3 phần mềm giả lập Java trên Android tốt nhất

  Android Jetpack là gì? Tại sao nên dùng Android Jetpack?

So tài HashMap với ArrayMap

HashMap

Về cơ bản, Hashmap là một mảng của HashMap.Entry (Entry là lớp bên trong của Hashmap).

Nếu nhìn tổng quan thì một instance của lớp Entry là:

  • 1 non-primitive key
  • 1 non-primitive value
  • Hashcode của một Object
  • trỏ đến Entry tiếp theo

Vậy điều gì sẽ xảy ra khi key => value được chèn vào một HashMap?

  • Mã băm (hashcode) được tính toán và gán giá trị đó cho biến hashCode của EntryClass.
  • Sau đó, sử dụng hashCode để lẩy được index của bucket nơi mà nó lưu trữ.
  • Nếu bucket tồn tại, phần lưu trữ mới sẽ được chèn vào vị trí cuối cùng và được chỉ tới 1 bucket mới tạo thành một danh sách bucket liên kết.
P/s: Bucket là nơi lưu trữ các key có hash gần như nhau. bucket được lưu trong một array nên chi phí truy xuất chỉ là O(1).

bucket

Bây giờ, khi bạn truy xuất HashMap để tìm giá trị của 1 key thì chi phí truy xuất là O(1). Nhưng quan trọng nhất là bộ nhớ càng nhiều, chi phí càng cao.

Tham khảo việc làm Java hấp dẫn trên TopDev

Nhược điểm của HashMap:

  • Autoboxing có nghĩa là mỗi lần chèn sẽ tạo ra đối tượng thừa. Điều này ảnh hưởng đến việc sử dụng bộ nhớ, cũng như thu gom rác.
  • Bản thân HashMap.Entry lại có thêm 1 lớp các đối tượng được tạo ra và thu gom rác (Garbage Collection).
  • Các Buckets được sắp xếp lại mỗi lần HashMap xóa hoặc thêm phần tử. Hoạt động này rất tốn kém tài nguyên, đặc biệt khi số lượng phần tử lớn.

Trong Android, khi nói đến ứng dụng responsive (ứng dụng hiểu thị tương thích với mọi loại màn hình từ phone đến tablet) thì bộ nhớ rất quan trọng. Việc phân bổ và giải phóng bộ nhớ liên tục cùng với việc thu gom rác (Garbage Collection) sẽ làm chậm ứng dụng Android của bạn đáng kể.

Hãy nhớ rằng – trình thu gom rác (Garbage Collection – GC) cũng phải tiêu tốn tài nguyên nhất định.

Khi GC hoạt động, ứng dụng của bạn không thể chạy, dẫn đến ứng dụng bị giật, lag…

ArrayMap

Vậy để tối ưu hóa ứng dụng android thì ArrayMap có gì khác?

ArrayMap sử dụng 2 mảng. Nó sử dụng Object [] mArray để lưu trữ các đối tượng , còn int [] mHashes để lưu trữ mã băm (hashcode).

Khi một cặp key -> value được chèn vào mảng thì:

  • key -> value được autoboxed.
  • Key của đối tượng đựo chèn vào vị trí khả dụng kế tiếp trong mArray[ ].
  • Value của đối tượng được chèn ngay sau vị trí key trong mArray[ ].
  • hashCode của key được tính toán và đặt tại mHashes[ ] tại vị trí tiếp theo.

Khi cần lấy giá trị theo key, bạn cần:

  • Tính mã băm (hashCode) của key.
  • Dùng Binary search để tìm mã hashcode
  • Khi gặp 1 danh sách hash, chúng ta suy ra vị trí của key là 2*index trong mArray và vị trí của value là 2*index+1.

Tại đây, độ phức tạp từ O(1) đã lên tới O(logN).

Một số đề xuất sử dụng cấu trúc dữ liệu thay thế:

  • ArrayMap<K,V> thay cho HashMap<K,V>
  • ArraySet<K,V> thay cho HashSet<K,V>
  • SparseArray<V> thay cho HashMap<Integer,V>
  • SparseBooleanArray thay cho HashMap<Integer,Boolean>
  • SparseIntArray thay cho HashMap<Integer,Integer>
  • SparseLongArray thay cho HashMap<Integer,Long>
  • LongSparseArray<V> thay cho HashMap<Long,V>

Hy vọng qua bài viết trên, bạn có thể áp dụng ngay tối ưu hóa ứng dụng Android một cách thành công. Có điều gì thắc mắc hoặc góp ý thì comment ngay bên dưới nhé!

Bài viết gốc được đăng tải tại vntalking.com

Xem thêm:

Tìm việc làm IT mọi cấp độ tại TopDev