This week's book giveaway is in the Java 8 forum.
We're giving away four copies of Java 8 in Action and have Raoul-Gabriel Urma, Mario Fusco, and Alan Mycroft on-line!
See this thread for details.
The moose likes Performance and the fly likes ArrayList Vs HashMap Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Java » Performance
Bookmark "ArrayList Vs HashMap" Watch "ArrayList Vs HashMap" New topic
Author

ArrayList Vs HashMap

Praful Thakare
Ranch Hand

Joined: Feb 10, 2001
Posts: 613
Some where Some how, I found code similer to following code



Then I thought better way to write it is as following


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


All desirable things in life are either illegal, banned, expensive or married to someone else !!!
Omar Al Kababji
Ranch Hand

Joined: Jan 13, 2009
Posts: 357
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 ;)


Omar Al Kababji - Electrical & Computer Engineer
[SCJP - 90% - Story] [SCWCD - 94% - Story] [SCBCD - 80% - Story] | My Blog
Tim Holloway
Saloon Keeper

Joined: Jun 25, 2001
Posts: 15665
    
  15

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.


Customer surveys are for companies who didn't pay proper attention to begin with.
William Brogden
Author and all-around good cowpoke
Rancher

Joined: Mar 22, 2000
Posts: 12682
    
    5
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


Java Resources at www.wbrogden.com
Praful Thakare
Ranch Hand

Joined: Feb 10, 2001
Posts: 613
Thanks for the inputs guys, very helpful !!!
Deepak Lal
Ranch Hand

Joined: Jul 01, 2008
Posts: 507

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




When The Going Gets Tougher,The Tougher gets Going
Jeanne Boyarsky
internet detective
Marshal

Joined: May 26, 2003
Posts: 29287
    
140

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.


[Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
 
Don't get me started about those stupid light bulbs.
 
subject: ArrayList Vs HashMap
 
Similar Threads
cuncurrency problems with class Properties
Casting Doubt
I need help, with logic:iterate in HashMap
reading input from a file into a array
display dynamically