Win a copy of Functional Reactive Programming this week in the Other Languages forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

ArrayList Vs HashMap

 
Praful Thakare
Ranch Hand
Posts: 642
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Omar Al Kababji
Ranch Hand
Posts: 357
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ;)
 
Tim Holloway
Saloon Keeper
Posts: 18303
56
Android Eclipse IDE Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
William Brogden
Author and all-around good cowpoke
Rancher
Posts: 13074
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Praful Thakare
Ranch Hand
Posts: 642
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the inputs guys, very helpful !!!
 
Deepak Lal
Ranch Hand
Posts: 561
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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



 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34973
379
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic