Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 782
  • Last Modified:

array vs. hashmap

I had the question posed to me: "I need to store and retrieve some integers in my Java code. I don't exactly know how many integers at compile time. But I know it will be around 5,000 and definitely less than 5,500. This storage will be accessed frequently and I need a fast turn around time. Should I use: array, arraylist, vector, or hashmap? "
Based on my understanding, I selected hashmap, yet array was the correct answer. Why? I had always been told that hashmaps are faster.
Thanks for any clarification
Bette
0
Bette Lamore
Asked:
Bette Lamore
  • 3
  • 3
  • 2
  • +3
4 Solutions
 
objectsCommented:
depends on how you want to access them, if just by index then use an array
if you need to lookup based on a key then use a map
0
 
CEHJCommented:
Your question says nothing about HOW these integers are to be accessed. Assuming the fastest scenario, using Integer[] a in an array where a[n] is either a[n] ==n or a[n] == null, then yes, an array will be very slightly faster than a Map
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
rodnessCommented:
This is something of a handwaving explanation, but I'm doing my best to keep it simple:

An array will be fastest to access, because it's not a class.  It's a native built-in structure.  When you ask for array[ 50 ], for example, all the JVM has to do is calculate the address of the array, plus (50 * size of an array element), and there's the memory address of the element you want.  Super easy.
And since you know it will be between 5000-5500 entries, you can just preallocate 5500, with guaranteed less than 10% waste, and don't have to worry about resizing it.

ArrayList and Vector are very similar.  They are both (essentially) arrays that will dynamically grow as necessary as you add elements.  However, growing the arrays means reallocating and copying, and is slower than preallocating one big array.  Additionally, Vector adds built-in method synchronization to make it safe for use in multithreaded environments, which also slows it down a little bit (the trade off is that multithreaded code using Vector is simpler than ArrayList).

HashMap is a different kind of beast altogether.  It lets you define key-value pairs, where you will hash key values to obtain the memory locations of the values.  This is slower to access than just an array index (although faster than having to search lists), but also doesn't make sense to use this unless you have key-value pairs.  If it's just integers, you don't have a pair of values, so it's simply not approriate, regardless of speed.
0
 
Bette LamoreAuthor Commented:
Thank you all for your input, particularly rodness who took the time to explain it to me. I have had only one semester of Java and we never got into hashmaps.
0
 
objectsCommented:
a good place to start understanding different collections
http://download.oracle.com/javase/tutorial/collections/index.html
0
 
Shura85Commented:
One thing to consider is how the integers will be stored: as ints or as Integer objects.   All of the collections you mentioned (arraylist, vector, and hashmap) require the things they store to be objects.  To use the collections, they would have to be Integers, whereas the array can hold either ints or Integers.

Like Rodness said hashmaps require a pair of values - so if you don't have a key, it won't work.  Also its really not the best idea for the key to be an integer.   Also with hashmaps, the key is used as part of a calculation for the memory location, while an array just goes to the specified location, so time is lost in calculating the memory location.  
0
 
rodnessCommented:
One thing to consider is how the integers will be stored: as ints or as Integer objects.   All of the collections you mentioned (arraylist, vector, and hashmap) require the things they store to be objects.  To use the collections, they would have to be Integers, whereas the array can hold either ints or Integers.

This is a true, but not complete, statement.

While ArrayList does require an object, int primitive values can be 'autoboxed' to Integer objects automatically:

ArrayList<Integer> list = new ArrayList<Integer>();  // you have to create the array list as using Integer
list.add( 42 );  // adding an int is legal
int value = list.get( 0 );  // retrieving a value into an int is also legal

Open in new window

The point is, use what makes sense.  If you have int values but you need a more complex data structure than an array, use Integer for the structure type and let java convert between int and Integer types for you.  (The same goes for float/Float, double/Double, and all the other primitive types which have Object equivalents.)

Like Rodness said hashmaps require a pair of values - so if you don't have a key, it won't work.  Also its really not the best idea for the key to be an integer.

The same point applies.  If using an int for a key makes sense, just use Integer and let java handle it.  

I use integers as hash keys all the time... suppose you want to map four zip codes to city names.  Zip codes are 5 digits... are you really going to create a 100,000 element int array just to make sure you can fit the integer value of a zip code into the array?  No... you're going to use a HashMap and store just the four values you need.

String[ 100000 ] zipcodes = new String[ 100000 ];
zipcodes[ 92101 ] = "San Diego";
zipcodes[ 92102 ] = "San Diego";
zipcodes[ 92103 ] = "San Diego";
zipcodes[ 92104 ] = "San Diego";

Open in new window


This will work, but it is a huge waste of memory.  We have allocated 999,996 elements in an array that are unused.

If we use a HashMap:

HashMap<Integer,String> zipcodes = new HashMap<Integer,String>();
zipcodes.put( 92101, "San Diego" );
zipcodes.put( 92102, "San Diego" );
zipcodes.put( 92103, "San Diego" );
zipcodes.put( 92104, "San Diego" );

Open in new window


This allocates four type-value pairs.  No more, no less.  Your tradeoff is that it will take slightly longer to retrieve values since it's not a simple array index, but hashing is still pretty damn fast.  Oh, and it saves you 400k of memory over the previous example.  (4 bytes per int * 100000).


I will reiterate my point again:  

If you have int values, just let Java autobox them for you, it's why they implemented autoboxing:  So you don't have to worry about it.

Don't get hung up on primitive vs object types, or whether you should or shouldn't use particular collections.  In the real world (e.g. outside of the arbitrary confines of school projects), just do what makes sense.  
0
 
Shura85Commented:
That's a good point - i hadn't thought of that.  However, it does seem to be overkill to use a hashmap to store just integers (in one form or another), when an array would suffice just fine.  
0
 
Bette LamoreAuthor Commented:
Wish I had more points left to give -- thank you soooo very much for your expanded explanation, rodness, and for your additional comments, objects and Shura85!
A very grateful Bette
0
 
Bette LamoreAuthor Commented:
It wasn't abandoned -- I accepted the solutions and awarded the points by clicking button above with my last post. I guess it did not connect so I will try again. Once again, thanks to you all!
Bette
0
 
DhaestCommented:
This question has been classified as abandoned and is being closed as part of the Cleanup Program. See my comment at the end of the question for more details.
0

Featured Post

Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

  • 3
  • 3
  • 2
  • +3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now