SparseArray vs HashMap

SparseArray là một cấu trúc tương tự như HashMap nhưng sử dụng ít bộ nhớ hơn. Mục đích của nó là map giữa primitive integers (kiểu dữ liệu nguyên thủy int) với 1 Object.

Cấu trúc của HashMap cũng là map giữa một key và Object, tuy nhiên key ở HashMap yêu cầu cũng phải là một Object. Kiểu dữ liệu nguyên thủy sử dụng ít bộ nhớ hơn Object, do đó nếu chương trình cần map giữa integers và một Object có thể giảm bớt gánh nặng về bộ nhớ bằng cách sử dụng SparseArray thay thế cho HashMap.

Nếu bạn nhìn vào cách sử dụng code ở SparseArray và HashMap, thì thấy rằng có thể sử dụng cả 2 đều có thể sử dụng int làm key. Tuy nhiên thực tế là cấu trúc ở tầng dưới của HashMap không sử dụng kiểu dữ liệu nguyên thủy, vì vậy Java compiler phải autoboxing giá trị int mà ta truyền vào.

HashMap – Autoboxing & Unboxing

Autoboxing là quá trình tự động chuyển đổi giữa kiểu dữ liệu nguyên thủy và kiểu Object wrapper của nó. Như đã nói ở trên, HashMap yêu cầu key của nó là kiểu Object. Xem xét ví dụ bên dưới:

HashMap<Integer, String> hashMap = new HashMap<Integer, String>();
hashMap.put(42, "Banana");
String fruit = hashMap.get(42);

Ở đây trình biên dịch đã autoboxing kiểu dữ liệu nguyên thủy với giá trị là 42. Đoạn code bên dưới này sẽ mô tả một đoạn chương trình tương đương với đoạn code bên trên, chú ý là ở đây, giá trị 42 sẽ được convert sang Integer Object

HashMap<Integer, String> hashMap = new HashMap<Integer, String>();
hashMap.put(Integer.valueOf(42), "Banana");
String fruit = hashMap.get(Integer.valueOf(42));

Cũng chú ý là get() method ở HashMap cũng autoboxing như vậy.

Unboxing là một cơ chế của trình biên dịch tự động convert một Object thành kiểu dữ liệu nguyên thủy tương ứng

SparseArray

Khởi tạo một Object sẽ tiêu tốn nhiều bộ nhớ và tài nguyên CPU. Vì lý do này, SparseArray có thể giúp cải thiện hiệu năng với việc giảm bộ nhớ cần sử dụng.

Hãy xem đoạn code demo cách sử dụng SparseArray. Nhớ rằng SparseArray được định nghĩa để map giữa primitive values với Object, vì vậy đoạn code mẫu bên dưới sẽ lấy một ví dụ đơn giản là map int – String Object

SparseArray<String> sparseArray = new SparseArray<String>();
sparseArray.put(42, "banana");
sparseArray.get(42);

Không có autoboxing và unboxing khi thực hiện đoạn code này. Tổng bộ nhớ tiết kiệm được tùy thuộc vào JVM và platform, nhưng một ví dụ đối với kiến trúc 32bit thì:

Primitive int value: 4 bytes

Integer Object size: ~ 16 bytes

Kiến trúc của SparseArray SparseArray giữ việc mapping bằng mảng, và sử dụng thuật toán tìm kiếm nhị phân để tìm kiếm key, cấu trúc mảng cho phép các kiểu dữ liệu nguyên thủy có thể được lưu như là chỉ số, nhưng không giống như mảng thông thường, những khoảng trống giữa các chỉ số được cho phép.

Cần lưu ý

Thông thường, HashMaps sẽ rất nhanh trong việc tìm kiếm phần tử, độ phức tạp của nó là O(1). Thuật toán tìm kiếm nhị phân, được sử dụng trong SparseArray có độ phức tạp là O(log n). Điều này có nghĩa là việc tìm kiếm ở SparseArray sẽ kém hiệu quả hơn ở HashMap kể cả tính đến việc autoboxing.

Hiệu năng của quá trình insert và delete phần tử cần được xem xét nếu cấu trúc data thường xuyên thay đổi, việc thay đổi cấu trúc đối với SparseArray sẽ phải bỏ nhiều công sức hơn so với sử dụng HashMap.

Nguồn tham khảo

http://jeffcardillo.com/blog/2015/01/22/sparsearray-vs-hashmap/

Trong bài viết này chưa đề cập chi tiết đến cấu trúc cụ thể (ví dụ dùng 2 mảng mKeys[] và mValues[]...) của SparseArray, cũng như những trường hợp cụ thể, so sánh hiệu năng với một số test thực tế, các bạn có thể tham khảo thêm ở một số bài viết sau:

https://www.javacodegeeks.com/2012/07/android-performance-tweaking-parsearray.html

http://gunhansancar.com/sparsearray-vs-hashmap/