This week's giveaway is in the Threads forum.
We're giving away four copies of Java Concurrency Live Lessons and have Doug Schmidt on-line!
See this thread for details.
Win a copy of Java Concurrency Live Lessons this week in the Threads forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

ArrayList vs LinkedHashMap  RSS feed

 
Kali Aurora
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).
 
steve souza
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


 
Tim Holloway
Bartender
Posts: 18531
61
Android Eclipse IDE 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.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!