• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

ArrayList Vs HashMap

 
Ranch Hand
Posts: 645
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Ranch Hand
Posts: 357
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 ;)
 
Saloon Keeper
Posts: 27762
196
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Author and all-around good cowpoke
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 645
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for the inputs guys, very helpful !!!
 
Ranch Hand
Posts: 603
Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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



 
author & internet detective
Posts: 41860
908
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
reply
    Bookmark Topic Watch Topic
  • New Topic