CODEWITHSUNDEEP
javadata-structures
Lahiru Chandima
Lahiru Chandima

Reputation: 24068

Is it OK to use a HashMap to keep indices of list elements?

I have a list of objects.

List<MyObject> myList;

This list is populated in the beginning and no update is done after that.

The order of objects in the list is significant because I need to iterate over this list in that order later.

During execution of my program, I frequently need to find the index of a given MyObject in myList;

I know that I can use myList.indexOf(object) but I am worried about the performance. So I am going to use a HashMap to map each MyObject in myList to its index in myList so that I can find the index much efficiently.

But I am not sure whether I am missing something trivial and I am going to use two containers with redundant data where I could get this done much easily using a different container.

So, can anybody see a better way to do this?

Upvotes: 0

Views: 556

Answers (4)

kajacx
kajacx

Reputation: 12939

With ArrayList<MyObject> myList; it takes O(n) to find index by myList.indexOf(object) (I don't know about other implementations of List) so I wouldn't use it unless you can guarantee that the list will be small.

One alternative would be to use LinkedHashMap<MyObject, Integer> which indeed would preserve the order of elements in which you inserted them to the map, however you would lose the ability to get object from index easily.

You could use LinkedHashMap<MyObject, Integer> in addition to your original List<MyObject> myList; so you can both get index from object and vise versa, as well as iterate through the object in the order you added them, however now the LinkedHashMap<MyObject, Integer> can be replaced by normal HashMap<MyObject, Integer> as you suggested in the first place.

There is also BiMap from Google's Guava so you can have a look into that.

Upvotes: 0

justAbit
justAbit

Reputation: 4256

You can use LinkedHashMap instead of List which will solve all your problems. Initially you can initialize you Map like this:

Map<MyObject, Integer> map = new LinkedHashMap<>();
//...
map.put(myObject1, map.size()); //saves myObject1 and index as 0
map.put(myObject2, map.size()); //saves myObject2 and index as 1
map.put(myObject3, map.size()); //saves myObject3 and index as 2
//...

If MyObject.hashCode() method implementation is good, map.get(myObject) will give you good performance and will save you from creating additional collection.

Upvotes: 0

Krycke
Krycke

Reputation: 3186

Using hashMap has a time complexity of O(1) for lookup, and accessing an array with a known index also has O(1), which means that finding and accessing an object will result in O(1). You can't do it faster then that.

When it comes to space you are off course doubling your space while having two structures, and a HashMap will even take more space as it needs to fill a whole hash range, but it's still only in O(n).

I think this is a OK approach, but as have been said already LinkedHashMap will do this automatically for you.

Upvotes: 0

npinti
npinti

Reputation: 52185

You can use a LinkedHashMap to contain your MyObject instances.

Map<String, MyObject> map = new LinkedHashMap<String, MyObject>();

Hash table and linked list implementation of the Map interface, with predictable iteration order.

This will allow you have 1 collection which does both.

Upvotes: 3

Related Questions