Using ArrayList or HashMap

Question

Hi I got a question on whether to use an ArrayList or HashMap.

I am trying to build a Paint program. Each drawn object will be assigned a unique object ID.

If I want a fast retrieval speed when I click on an object, should I be using an arraylist or hashmap?

In general hashmap has O(1) while arraylist has O(n) retrieval speed.

However, I think for my case, since when I click on an object, I'll get the ID, hence the index of the array and I can do something like ArraylistObject.get(ithElement); , so in this case this will also be a O(1) retrieval process?

any inputs?

Thanks!

Answer 1

If objects have an ID that can be mapped 1-to-1 to an array than that will be O(1) access as well, and in practice will be slightly faster than a hashmap lookup (you don't have to compute the hash).

However, the issue will be what happens when you delete an object. You will be left with a hole in the list. When creating new objects you can then keep appending to the list and leave it to get slowly more fragmented or try and find a spare slot in which case you'll be doing an O(n) search for a spare space.

In short - a hashmap is probably more appropriate.

Answer 2

On the plus side, you might be able to squeeze out a little extra performance by doing ArrayLists just right. But deleting objects is going to be a royal pain - as Paolo and Anurag said, you'll either have to put an empty placeholder (null ?) or to renumber some other other object to fill the gap. This is likely to result in performance bugs and plain old bugs.

HashMaps, on the other hand. Simple to use, decent performance guaranteed (unless you allocate your ids really badly).

And retrieving objects by id might not turn out to be your application's bottleneck at all. As the saying goes, premature optimization is the root of all evil.

Answer 3

If you can guarantee that the IDs will be in a relatively small numerical range, then you should use a plain array (with the size preinitialized to the maximum ID), rather than an ArrayList. That ensures that you don't accidentally remove entries and shift everything else to fill the gap, with everything ending up at a wrong index. A plain array will also be a bit faster than an ArrayList.

If you can't make such a guarantee, use a HashMap. It's very unlikely that the speed difference would be noticeable, and it will be easier to maintain.