• 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
  • Knute Snortum
Sheriffs:
  • Liutauras Vilda
  • Tim Cooke
  • Junilu Lacar
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Joe Ess
  • salvin francis
  • fred rosenberger

ArrayList vs LinkedHashMap

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Performance question. Please read.

Non synchronized.

LinkedHashMap<String, MyObject>

I have a class that currently contains several member variable hashmaps. There will likely be hundreds of instances of this class floating around in memory. Each map will hold some sort of user data. Theoretically there could be hundreds of items in the map... however I expect on average that our users will have ~5 items that will be stored in each map. Each user item must have a unique name (the String).

Find operations (by the key String) will be common. Typically these find operations will only be performed due to user actions (so in CPU time once every long time). Find operations will be much more common than any other operation (add, delete).

So my sort of quandary:

Aside from the fact that the map seems the most logical in terms of what I will be most often doing to the datastructure, I was thinking:
-I believe LinkedHashMap per item (and in general) has a larger memory footprint than ArrayList - though how much I do not know.
-The find O(n) on an ArrayList with an average of ~5 items is basically negligible.
-Computing the hashcode of the String key might actually take more time than to iterate over an ArrayList and do comparisons on the Strings - in which case sadly the ArrayList could be faster at finds. I'm sort of up in the air on this one as it depends on how similar the String keys would be for the String.equals() to return quickly or not.
-Memory usage comparison.

TBH this is just a question I've had for quite a while - and this is a specific scenario that it can be applied to. In general is there a good guideline at how many items you expect to be in a map for you to just use an ArrayList instead?

If the comparison is super close then I'm just sticking with the map as logically it tends to make the most sense in terms of business logic and what to expect. But if there is a massive performance / memory usage difference, then obviously I want to go with the right data structure for the occasion.

Oh and yes ordering is important (thus the linked hash map instead of a regular hash map).
 
Ranch Hand
Posts: 862
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Computing the hashcode of the String key might actually take more time than to iterate over an ArrayList and do comparisons on the Strings - in which case sadly the ArrayList could be faster at finds. I'm sort of up in the air on this one as it depends on how similar the String keys would be for the String.equals() to return quickly or not.



This is making some assumptins about how the String class is implemented. Here are the hashCode and equals method from open jdk 7 http://www.docjar.com/html/api/java/lang/String.java.html. Various jdk's may have diffterent implementations, but in general I suspect the hashCode is only calculated once per String.

String.hashCode


String.equals


 
Saloon Keeper
Posts: 21597
146
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As always, the only true metric is to actually measure. But it's fairly safe to say that virtually all Java implementations are going to implement the hash() method fairly efficiently, since it's key to a lot of Java operations.

In fact, since java.lang.String objects are immutable, you only need to calculate the hash value once. If you were to actually use the object identifier as the hash value, you wouldn't have to run the string at all, and there'd be no actual memory needed to hold the value. Plus, it would be by definition a Perfect Hash value.
 
Onion rings are vegetable donuts. Taste this tiny ad:
Sauce Labs - World's Largest Continuous Testing Cloud for Websites and Mobile Apps
https://coderanch.com/t/722574/Sauce-Labs-World-Largest-Continuous
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!