I just implemented an solution with reference counting. It works like this: each shared record number object got a reference count. This count is increased before lockRecord and decreased after method completes. The unlock method also increases the count and decreases it after completion. The decrease in unlock check for the possiblitiy that the ref. count is zero. If it is, the shared lock object is removed. I think the complexity is rather low, LockManager class is 250 LOC (with extensive commenting).
In code it looks like:
The lockRecord(p_recNo, t_lockRec) method is implemented as "usual", but synchronize on the t_lockRec instance instead of a shared HashMap (to name one possibility).
The unlock method is very similar to the code above.
I've tested this code with 30+ concurrent threads performing lock/unlock. It seems to perform nicely. The "growing issue" is solved.
Regards,
Henrik