 <p>As far as I understand, you don't need to use <code>Semaphore</code> here. Instead, you should use <code>ReentrantReadWriteLock</code>. Additionally, the <code>test</code> method is not thread safe. </p> <p>The sample below is the implementation of your logic using RWL</p> <pre><code>private ConcurrentMap&lt;String, ReadWriteLock&gt; map = null; void test() { String hash = null; ReadWriteLock rwl = new ReentrantReadWriteLock(false); ReadWriteLock lock = map.putIfAbsent(hash, rwl); if (lock == null) { lock = rwl; } if (lock.writeLock().tryLock()) { try { compute(); map.remove(hash); } finally { lock.writeLock().unlock(); } } else { lock.readLock().lock(); try { compute(); } finally { lock.readLock().unlock(); } } } </code></pre> <p>In this code, the first successful thread would acquire <code>WriteLock</code> while other <code>Thread</code>s would wait for release of write lock. After release of a <code>WriteLock</code> all <code>Thread</code>s waiting for release would proceed concurrently.</p>