Performance question

[Diancecht]

Hi all.

I have a little doubt on a performance issue, and I was wondering if any of you had experience on this.

My doubt comes from a "Mortal Kombat" HashMap vs ArrayList doing a "contains" operation. To be more exact, ArrayList.contains vs HashMap.containsKey.

I've had a look at source code for both, but I've not managed to calculate O for HashMap. I've also searched the web, but no one seems to care about this, what makes me think that the difference will be really small.

Anyway, if any of you have any comments on this, they will be wellcome.

Cheers.

Dian

 

[idarke]

Since ArrayList isn't indexed, it would have to do a brute force search through every element in the collection until it found the one it's looking for. The HashMap only needs to look in it's index, so it would be faster.

To test this, I wrote a small app that loaded 10000 objects in an ArrayList and a HashMap and then did a "contains" on each of the 10000 elements.

The ArrayList required 12 seconds. The HashMap required 0.01 seconds.

If your application is only doing one or two "contains" calls, however,the difference would be small, and you'd have to balance it against the time required to build the collection, which is higher for the HashMap.

 

[Diancecht]

Thank you, idarke.

I think I'll do some performance testing. I'm curious about this thingie. I've found more points about this, because a HashMap needs more memory to get allocated and, at least in old JDKs, if keys were Strings, hascode performance was very poor.

I guess it will be, as always, dependent of each case.

Cheers.

Dian

 

[meadandale]

This is datastructures and algorithms 101.

A hashtable is guaranteed O(1) lookup.

A list is O(N).

While you might be able to find an item in a list quickly, as N grows, so does your worst case performance (e.g. you are looking for something that is at the end of the list). A hashtables speed has nothing to do with the size of the dataset (it is not tied to N).

Could you use a list for lookups? Of course. But as your dataset grows, the performance of your application will suffer.

As with all other things, you should use the right tool for the job. YOu can hammer nails with a crecent wrench but you are better off just using a hammer.

 

[Diancecht]

Thank you, meadandale.

I guess I'd have to separate my data tables between those that holds a lot of data with no many accesses (ArryList) and those with less data and more accesses (HashMap).

I'm curious also about the actual performance improvement doing this. I'm not sure it will be appreciated by the end user.

Anyway, I'll try to post the results, as soon as I have spare time to do somre performance testing.

Cheers,

Dian