I am looking for a high-performance, concurrent, MultiMap. I have searched everywhere but I simply cannot find a solution that uses the same approach as ConcurrentHashMap (Only locking a segment of the hash array).
The multimap will be both read, added to and removed from often.
The multimap key will be a String and it's value will be arbitrary.
I need O(1) to find all values for a given key, O(N) is OK for removal, but O(logN) would be preferred.
It is crucial that removal of the last value for a given key will remove the container of values from the key, as to not leak memory.
EDIT: HERE'S THE SOLUTION I BUILT, available under ApacheV2: Index (multimap)