SparseArray vs HashMap

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> :

Screen Shot 2013-05-01 at 21.16.50

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.

Advertisements

One thought on “SparseArray vs HashMap

  1. peyxhvxnsz@gmail.com

    Aw, this was a really good post. Spending some time and actual effort to produce a great article… but what can I say… I procrastinate a whole lot and don’t manage to get anything done.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s