On Sat, 7 May 2011, Patricia Shanahan wrote:
On 5/7/2011 2:43 AM, Sebastian wrote:
...
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.
...
I'd deal with that sort of problem by having a custom data structure
that uses java.util structures in its implementation.
It's not obvious to me how to make it work correctly with good
concurrency; the ConcurrentHashMap approach is to stripe the locks, so as
to partition the hashtable into independently-locked domains, but to use
the same set of stripes for the reverse mapping, you would need to be able
to tell which stripe a value belongs to - and that can only be done by
looking it up in the very reverse mapping you are worrying about locking!
Can you have a separate set of stripes for the reverse mapping? Do you
need some multi-phase approach, where you determine the stripes without
locking, then acquire the locks to do the actual lookup or insertion? Is
there some lock-free voodoo which could be used? Is there any mileage in
using a union-find structure to collapse the sets of values into a single
representative which could participate in a 1:1 key-value mapping? I am
certainly not any sort of data structure guru, but i don't have answers to
any of those questions. That makes it a problem worth discussing here, in
my book. Does anyone have any ideas on how to do this?
workspace a member of Task and synchronize accesses on Task. Example: