Using HashMap with Integers ( indices ) as keys vs using an ArrayList

Question

So I'm currently making my own version of Pokemon replicated in Java. I've only gotten familiar with more advanced data structures very recently and I'm still not sure when one should be more appropriate than the other.

Basically, I want to store a Pokedex ( the database of Pokemon ) and HashMap seems like it would make the best fit. The key would be a Pokemon's pokedex # , and the value would be the Pokemon object in question. Due to the nature of the pokedex though, that means each Pokemon's pokedex # would just be their respective index in the pokedex.

My question is does it make sense to use a HashMap when the keys are just index values, or would it make more sense to store the Pokedex as an ArrayList ( or array even ) where each Pokemon is stored at its respective index?

Obviously if I haven't created definitions for every Pokemon yet, then the ArrayList will be memory inefficient since we will have to reserve space for every pokemon, but as far as I understand keys in hashmaps are supposed to be used to create hash values rather than being direct indices right? Or would it be appropriate regardless?

• Kartik: would just be their respective index - if this may change in future, use a HashMap, else use an ArrayList.
• Carcigenicate: If the keys will always be 0, 1, 2... use a list. If the keys are irregular though, use a hashmap. Honestly though, in most cases, you could just use hashmap and not run into any problems. It's pretty fast to do lookups with unless you have a lot of key collisions.

Answer 1

This really depends. A map gives you a higher degree of freedom, whereas lists/arrays might force you into the consequences of using such linear/sequential data structures.

Then, it depends on how "sparse" your array will be populated. If the "keys" run 0 to 1000, with few or no unused slots, a list is fine. If the keys go 0 to 10 million, and most slots empty: use a map. Or a data structure optimized for sparse matrices.

Beyond that, keep in mind that an array doesn't contain the memory for the objects themselves, just for the references pointing to them. So the memory footprint of an array is the same, no matter if the slots are null or pointing somewhere.

Answer 2

Your first instinct to use the Hashmap is correct. Although an array is more efficient, that efficiency is pointless in your case. Looking up the pokemon in the pokedex is going to be one of the least time consuming things your program does; optimizing it would be pointless, and might even unintentionally introduce bugs (e.g. off-by-one errors)

• Jason: "The three hardest things in software engineering are naming things and off-by-one errors".