In my code I have a map that is used heavily, several thousand times in a few seconds. Originally I had a TreeMap, but when testing with 9,000 entries I watched my old processor melt. And this needs to scale. So I moved to a HashMap and performance was excellent.
Now I am changing my design and am looking for a MultiMap. However I'm afraid of the performance impact on the get() side, as it must iterate over said large map picking out the matching keys, and when called many many times even synchronized it seems like it would be slow.
Is there a good MultiMap that can handle such large values with great performance? Performance is critical in this application, as there could be many large separate maps handling a very large workload, making "small" performance losses very big issues.
Bonus points if it can be extracted to work alone without any dependencies.
The one that was recommended to me in one of my questions was the Apache Commons MultiMap: http://commons.apache.org/collections/api-3.2.1/org/apache/commons/collections/MultiHashMap.html
It's free software, so you can at least get the source to look at it, and depending on your license situation, you can modify it or use it standalone.
It uses an ArrayList internally, but I imagine you can probably change it to use a HashSet or something. I would look at the createCollection(Collection coll) method.
UPDATE: Actually, Guava's HashMultiMap appears to already be what I was talking about: https://github.com/google/guava/blob/master/guava/src/com/google/common/collect/Multimap.java
I looked at the source and it seems that each collection of values is in fact backed by a HashSet.