Re: Concurrent bidirectional one-to-many map?
Am 06.05.2011 22:45, schrieb markspace:
On 5/6/2011 1:07 PM, Sebastian wrote:
Does anyone know of a concurrent bidirectional one-to-many
map implementation?
By bidirectional I mean that I can lookup keys by values, by
one-to-many I mean that the value end of the map is a list or
set, and by concurrent I mean that I do not need to synchronize
externally and get performance comparable to that of
java.util.concurrent.ConcurrentHashMap in both directions.
If this beast doesn't exist, how would I go about inventing it?
I must say that I am by no means any sort of concurrency guru...
-- Sebastian
Can you just put both keys and values in as the key? Something like:
Map<Key,Key> myMap = new ConcurrentHashMap();
// add key k and value v
Key holder = new Key( k, v, KEY );
myMap.put( holder, holder );
holder = new Key( v, k, VALUE )
myMap.put( holder, holder );
...
public class Key<K,V> {
public enum KeyValue {KEY,VALUE};
private k key;
private V value;
private KeyValue keyOrValue;
public Key( K key, V value, KeyValue keyOrValue ) {
this.key = key;
this.value = value;
this.keyOrValue = keyOrValue;
}
// must also override hashcode and equals...
}
This way when you add something, it gets added as both key and value.
You might want to override "put" to do that automatically. When you look
up either a key or a value, you'll find both.
There may be better ways of doing this, it's just the first thing that I
thought of. Also the code above is meant more as a sketch than a
rigorous code example.
Thanks for the idea. I do not yet see how to deal with the
one-to-many aspect of my problem.
To give an example, I'm trying to solve a problem like this:
Associate tasks with workspaces, where a workspace may hold many
tasks,but a task may be associate with at most one workspace.
Idea:
private ConcurrentMap<Item, Workspace> wsMap =
new ConcurrentHashMap<Item, Workspace>();
public boolean isAssigned( Item item ) {
return wsMap.containsKey( item );
}
public void assign( Item item, Workspace ws ) {
wsMap.putIfAbsent( item, ws );
if( !ws.equals( wsMap.get( item) ) ) {
throw new NotAssignableException();
}
}
Now I want to be able to close a workspace, releasing all tasks
to be assignable again to other workspaces.
public void closeWorkspace( Workspace ws ) {
// how do this efficiently? iterate over all
// entries (holding a write lock) and remove it
// when the value equals ws?
}
-- Sebastian