Using ArrayList or HashMap

Question

Hi, I have a question about whether to use ArrayList or HashMap .

I am trying to create a Paint program. Each depicted object is assigned a unique object ID .

If I want to quickly get speed when I click on an object, should I use ArrayList or HashMap ?

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

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

any inputs?

Thanks!

Answer 1

If the objects have an identifier that can be mapped 1-to-1 to an array, then this will also access O (1), and in practice it will be slightly faster than searching for a hashmap (you do not need to calculate the hash).

However, the problem will be that you are deleting the object. You will still have a hole in the list. When creating new objects, you can continue to add to the list and leave it more slowly fragmented or try to find a spare slot, in this case you will search for O (n) free space.

In short, a hash file is perhaps more preferable.

Answer 2

On the plus side, you can compress a little extra performance by making ArrayLists just right. But deleting objects will be a royal pain, as Paolo and Anurag said, you either have to put an empty placeholder (zero?), Or renumber another other object to fill in the gap. This will likely lead to performance errors and simple old errors.

HashMaps, on the other hand. Easy to use, decent performance is guaranteed (unless you select your identifiers very poorly).

And retrieving objects by ID may not be your application’s bottleneck at all. As they say, premature optimization is the root of all evil.

Answer 3

If you can guarantee that the identifiers will be in a relatively small number range, then you should use a simple array (with preinitialized size to the maximum ID), and not with an ArrayList . This ensures that you do not accidentally delete entries and do not transfer everything else to fill in the gap, and everything ends with the wrong index. A simple array will also be slightly faster than an ArrayList.

If you cannot make such a guarantee, use the HashMap. It is very unlikely that the difference in speed will be noticeable, and it will be easier to maintain.