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).
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.
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.
Being persecuted doesn't in any way prove your righteousness or your beliefs. Many people get persecuted because they are repugnant or annoying. Or just because they can be.
Onion rings are vegetable donuts. Taste this tiny ad:
Sauce Labs - World's Largest Continuous Testing Cloud for Websites and Mobile Apps