ArrayList Vs HashMap

Some where Some how, I found code similer to following code

// list is an object of ArrayList for (Iterator iter = list.iterator(); iter.hasNext();) { Customer element = (Customer) iter.next(); if(element.getJ() == ("somevalue")) { System.out.println(element.getI()+" "+element.getJ()); break; } }

Then I thought better way to write it is as following
// here i used hashmap instead of arraylist where element.getJ() is the key and element is the value Customer element=(Customer)hm.get("somevalue");

and ofcourse the performace improved to about 25%... all went well till this question struck me, WHY ???
even in second case JVM will iterate hm (hashmap) to find the key so why so much of difference in performance ?

-P

Hashiiiiiing,

HashMaps as from the name using hashing to locate objects inside them, so when you search for an object, the VM will calculate its hashcode and then search based on that hashcode which would increase performance as much as your hashcode is efficient.

just for a test try returning the same value in the hashcode for all Customer objects, performance should decrease a lot ;)

Let me commend the MIT textbook "Introduction to Algorithms" (McGraw-Hill) to you. Although I have a number of good books on such things, it's one of the best - ranking right up there with Knuth's Art of Computer Programming (and, unlike Knuth, doesn't resort to an "assembly language").

The average retrieval time for an element in an ArrayList is X+N/2, since on average, half the elements in the list will have to be examined. X is the fixed overhead for accessing the list at all and is normally insignificant.

For a simple (perfect) Hash, the average retrieval time is going to be simply O, were O is the overhead for calculating the hash and retrieving the element. Hashtables with colliding elements take somewhat longer, since the overflow has to be scanned as well.

One of the cool things about Java is the public source code.

If you wonder why something works the way it does you can look at the source code and learn something. Heartily recommended.

Bill

Thanks for the inputs guys, very helpful !!!

Hi Praful,
Could you tell me how did you test the performance of an ArrayList and HashMap.Is there any tool for testing performance of a Collection.

Sample code for testing performance of a collection given would be helpful.

--
Deepak Lal

Deepak Lal wrote:Hi Praful,
Could you tell me how did you test the performance of an ArrayList and HashMap.Is there any tool for testing performance of a Collection.

It takes so little time to write this test yourself, I can't imagine there would be a tool. Just create a large collection in a loop and query it a lot of times. If you log the start/end time, you have the performance.