A sparse array in Java is a data structure which maps keys to values. Same idea as a Map, but different implementation:
- A Map is represented internally as an array of lists, where each element in these lists is a key,value pair. Both the key and value are object instances.
- A sparse array is simply made of two arrays: an arrays of (primitives) keys and an array of (objects) values. There can be gaps in these arrays indices, hence the term “sparse” array. Example source code here.
The main interest of the SparseArray is that it saves memory by using primitives instead of objects as the key. For instance the screenshot below (courtesy of visualVM), shows the memory used when storing 1,000,000 elements in an sparse array of <int, String> vs an HashMap of <Integer,String> :
The difference in size between both structures can be explained by :
– difference in size of the key: an int is 4 bytes while an Integer is typically 16 bytes (JVM-dependent).
– Overhead of a Hashmap entry compared to an array element. ie. a HashMap.Entry instance must keep track of the references for the key, the value and the next entry. Plus it also needs to store the hash of the entry as an int.