Fastest data structure for access/modification in Java

Question

Hi there Stackoverflowers!

I was coding a project when I wondered which is the fastest data structure that allows me the best performance if I have to access/edit a lot that data?

Let me explain with an example. I have a class called User and a class Event. A User can have many events. Until now, I have implemented this situation with an ArrayList:

public class User{
    ArrayList<Event> events;
    public void process(){
    }
    ...
}
public class Event{
    event data like event time etc.
}

Since I have a lot of users(millions), every user can have potentially thousands of events, and, moreover, I have to access every event of a user with process() method, I think that using structures like HashMaps etc. would not be helpful(If am wrong please tell me). However, it is obvious that with this number of elements, good performance is a need.

So, what do you think the fastest data structure to handle the events is?

Thank you very much,

Marco.

Solution 1

This sounds like a job better suited for a database, especially if you want persistence and/or your data may not fit in the main memory of your computer.

If, however, you insist on doing this in your own code, you might want to have a look at the LinkedHashMap class. It allows direct access to its elements with constant (i.e. O(1)) complexity, while also combining an internal linked list to allow fast iteration over all elements.

Of course, whether a HashMap structure is helpful depends on what you want to do. If, for example, you want to search events based on some kind of identifier, then a HashMap is ideal.

On the other hand, if you only need to access events based on their insertion order, then you cannot do much better than ArrayList, since it supports indexed access to its contents with a constant complexity. If you just need to process them in a queue or stack, Java has several implementations of the Deque interface that might interest you.

Lastly, if you want to insert your keys randomly and have the underlying structure sort them itself, you might find the TreeMap class useful.

Solution 2

There are two things:

1- in current scenario, if concurrent users are not a concern then you can easily go for arraylist as its faster simpler data structure else if concurrent users are the concern then you can easily go for vector to store your events.

2- you can use queue DS, which will help you in dynamic operations like insertion/deletion which is faster then arraylist and vecotr as it uses iterator.

I hope it helps.