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

Question

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 ?

@TimothyTruckle or they've measured, and found it takes less time and space. An array T[] is logically a Map<int, T>; it has about as little overhead as you can get away with in Java. — Andy Turner
– Andy Turner, Commented Feb 1, 2018 at 8:24
@AndyTurner usually the space saved does not matter because the app did not suffer from low memory and the time spend to code (and test) the array based solution usually exceed the time saved at runtime during life time of the app by magnitudes... However, taking over C++ best practices (like manual memory management in this case) to Java is usually not a good idea.... — Timothy Truckle
– Timothy Truckle, Commented Feb 1, 2018 at 8:28

Andy Turner · Accepted Answer · 2018-02-01 08:29:20Z

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.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related