CODEWITHSUNDEEP
javaarrayshashmapkey-value
Harish Kayarohanam
Harish Kayarohanam

Reputation: 4014

Why would someone use Array over HashMap if the situation allows for HashMap?

I was reading a solution here (https://leetcode.com/problems/longest-substring-without-repeating-characters/solution/).They say that in normal cases when there is no idea about key's (character's) range we use hashmap.

And there is another solution which says that when we are particular about the character set we can use array instead.

The previous implements all have no assumption on the charset of the string s.

If we know that the charset is rather small, we can replace the Map with an integer array as direct access table.

Commonly used tables are:

int[26] for Letters 'a' - 'z' or 'A' - 'Z'
int[128] for ASCII
int[256] for Extended ASCII

Not only here, but also in several locations in Cracking the Coding interview book they use an array where the characters are keys by representing a character by the equivalent integer and storing the value at a corresponding location in that array.

Why would we struggle with array's when we have hashmap at our hand ? Is there any reason ?

Upvotes: 1

Views: 1793

Answers (1)

Andy Turner
Andy Turner

Reputation: 140299

Why would we struggle with array's when we have hashmap at our hand

Just don't struggle with them, they're not hard :)

I mean, which is harder:

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < 26; ++i) {
  map.put(i, 0);
}
// Or, if you want to use Streams:
// IntStream.range(0, 26).boxed().collect(Collectors.toMap(i -> i, i -> 0));

or

int[] array = new int[26];
// No need to initialize anything, Java sets elements to zero by default.

The thing about a HashMap is that you have to store keys as well as the values. In particular, a Java HashMap has to store reference-typed keys, so you have to box your keys before putting them in there. So, you're losing twice, both in storing the keys, and having to store them inefficiently.

An array T[] is logically a fixed-sized Map<int, T> with dense, contiguous keys. You don't need to store keys, because they're implicit in the notion of an element index. It has very fast access to a particular element, both for getting and setting.

It's an optimization: if all you're doing is getting/setting elements, you don't need all the other gubbins that comes along with a full-fat Map implementation. But with that optimization (as with all optimizations) you have downsides, for example not being able to readily generalize to much larger key spaces.

Upvotes: 4

Related Questions