Java HashMap<Integer, Integer> vs int[]

Question

I have an integer array of size 10000, which is gradually filled with other integers (context: http://uva.onlinejudge.org/external/1/100.pdf), but it is not large enough. I plan to replace it with a HashMap, and was wondering if this was a better idea than making the array arbitrarily larger (eg. increasing the size to 100000)?

Also, what are the main differences between a HashMap and an integer array?

N.B. In this case, only odd keys are used in the HashMap/array.

A map is a completely different data structure from an array. — Matt Ball
– Matt Ball, Commented Jan 6, 2015 at 0:46
You need an ArrayList. You just put more in it without worry. Why would you only use 1/2 of the memory? — ChiefTwoPencils
– ChiefTwoPencils, Commented Jan 6, 2015 at 0:54
Do you have gaps in the set of keys (i.e. are the keys 1, 3, 5, 7, 9 ... or could they be 1, 13, 27, 33, 59, 1001...)? If there could be gaps I can understand why you might use a HashMap<Integer, Integer>, but if there are no gaps this should definitely be a List<Integer> or an int[]. — Paul Boddington
– Paul Boddington, Commented Jan 6, 2015 at 1:21

Patricia Shanahan · Accepted Answer · 2015-01-07 13:47:55Z

Both, obviously, provide a mapping from a subset of the integers into the integers. There are several differences, but the short answer is that an array is likely to work better for dense keys and a HashMap for sparse keys.

The memory cost per key that you use will be 32 bits for the array, but several times that for the HashMap. The memory cost per key that is in the range but that you don't use is also 32 bits for the array, but can be close to zero for the HashMap.

Array access will be faster than HashMap access.

If you expect to use as many as 50% of the entries, you are much better off with the array. If only odd keys are needed, and the array is large, consider using array index (i-1)/2 to represent the element with key i.

The best way to find which is better for your situation, including finding the density threshold for switching between them, is by testing. This is the procedure I would follow:

Define an interface for the data structure that has methods for the operations you need to be able to do on it.
Write your code, except for the actual creation of the structure, in terms only of that interface.
Define two classes that each implement the interface, one using the array and the other using a HashMap.
Measure using each of the classes. For the HashMap, you can also experiment with the HashMap constructor arguments.

Thanks, one of the things I was wondering was the threshold for which an array would be more optimal.
@Dimpl I've edited my response to add a bit about determining the threshold.

ProgrammingIsAwsome · Accepted Answer · 2015-01-06 01:02:34Z

An array is a list of values. An int array is a list of integers. You access the element by indices.

A map resp. hash map is: key --> value. In a hash map you retrieve values by a key.

public class Book{}

HashMap<String, Book> books = new HashMap<String, Book>(); // mapping from a string(=key) to a Book object(=value)
books.put("Harry Potter", new Book());
// etc.

So if you want to access elements by a key, then a hash map is what you need. The keys have to be immutable (like int or string) So pick what suits you the best.

Collectives™ on Stack Overflow

Java HashMap<Integer, Integer> vs int[]

2 Answers 2

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Related