Currently, all my game objects are stored in an ArrayList. Each frame, the game loop iterate over this ArrayList and do its work to move/update the entities.

I have been thinking lately... an ArrayList may be affecting performance negatively. The get(Object) and remove(Object) are not constant-time operations. In my game, these two functions are often called. HashMap solves that problem, but gives me a new problem, the order of the elements is beyond your control.

ArrayList:

+ Fast to iterate over it

+ Control over the position(index = render priority)

- Slow remove(object) and get(object) functions

HashMap:

+ Constant-time remove(object) and get(object) operations

+ Allows no dublicates

- Slow to iterate through. You have to call values()(every frame, or cache it) which returns a Collection object that you can iterate through

- Unknown order. No way to control render priority.

What should I do?

Well have you thought about using both?

Using the array for the iteration tasks the the hasmap for random access? besides do you really need to completely remove the entry? What is your entity?

From your lists of pros and cons, it seems like you are using the collection of game objects for things it ought not be used for.

Many games have a list of all the objects in the world. A hash map is great for this.

HashMap:
+ Constant-time remove(object) and get(object) operations
+ Allows no dublicates
- Slow to iterate through. You have to call values()(every frame, or cache it) which returns a Collection object that you can iterate through
- Unknown order. No way to control render priority.

Why are you iterating over every object in your game? Unless your game world is quite small you will only ever want to iterate over a tiny subset of the world.
Why do you care about the order of game objects? Game objects could be created and destroyed at any time.

Generally the need to iterate is done based on spatial needs, or based on objects notifying the engine that they need special processing. Game objects should have their locations registered in a spatial tree and queries for their ID made against that. Objects needing processing should have their ID registered in a separate list for processing.

Similarly for render priority, rendering is different than a game object existing. If a game object needs to be rendered it should have the ID placed in a list of renderable objects that includes details including render priority.


There is generally a single collection of all the game objects. If it is a game object, it exists within that giant hash table.

Everything else references the ID of that object, not the object itself. Getting the actual object from the giant hash table is a simple task involving minimal resources. On the grand scheme of things, looking up objects by ID from a hash map is not a performance issue.

You can do both.

When you put something in a list you're putting the reference in there, rather than the object(A reference tends to be 32-64 bits, but the size isn't guaranteed. And references to other parts of the list and management won't hurt you too badly).

If you can only do one it's trivial(though resource intensive) to convert a Hash Table/Map to an Array List with collections.