title: High-performance Concurrent MultiMap Java/Scala
body: <p>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).</p>
  
  <p>The multimap will be both read, added to and removed from often.</p>
  
  <p>The multimap key will be a String and it's value will be arbitrary.</p>
  
  <p>I need O(1) to find all values for a given key, O(N) is OK for removal, but O(logN) would be preferred.</p>
  
  <p>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.</p>
  
  <p>EDIT: HERE'S THE SOLUTION I BUILT, available under ApacheV2:
  <a href="https://github.com/akka/akka/blob/release-1.3.1/akka-actor/src/main/scala/akka/actor/ActorRegistry.scala#L281" rel="nofollow noreferrer">Index (multimap)</a></p>