CODEWITHSUNDEEP
javaarrayshashmap
Dimpl
Dimpl

Reputation: 942

Java HashMap<Integer, Integer> vs int[]

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.

Upvotes: 0

Views: 2094

Answers (2)

Patricia Shanahan
Patricia Shanahan

Reputation: 26175

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:

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

Upvotes: 3

ProgrammingIsAwsome
ProgrammingIsAwsome

Reputation: 1129

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.

Upvotes: 0

Related Questions