Solved

array vs. hashmap

Posted on 2011-02-28
13
732 Views
Last Modified: 2012-05-11
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
Comment
Question by:Bette Lamore
  • 3
  • 3
  • 2
  • +3
13 Comments
 
LVL 92

Expert Comment

by:objects
ID: 35002221
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
 
LVL 86

Expert Comment

by:CEHJ
ID: 35002253
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
 
LVL 92

Assisted Solution

by:objects
objects earned 125 total points
ID: 35002289
0
 
LVL 7

Accepted Solution

by:
rodness earned 250 total points
ID: 35002403
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
 

Author Comment

by:Bette Lamore
ID: 35002773
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
 
LVL 92

Expert Comment

by:objects
ID: 35003180
a good place to start understanding different collections
http://download.oracle.com/javase/tutorial/collections/index.html
0
Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 1

Assisted Solution

by:Shura85
Shura85 earned 125 total points
ID: 35018193
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
 
LVL 7

Assisted Solution

by:rodness
rodness earned 250 total points
ID: 35018498
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
 
LVL 1

Expert Comment

by:Shura85
ID: 35019438
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
 

Author Comment

by:Bette Lamore
ID: 35021070
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
 

Author Comment

by:Bette Lamore
ID: 35281554
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
 
LVL 53

Expert Comment

by:Dhaest
ID: 35321688
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

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
countHi challenge 25 84
Books that can get me started on JAVA 2 54
countPairs challenge 7 58
countHi2 challenge 7 44
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now