Add comments, and create already locked semaphores in order to reduce further contention opportunities.

LockMap.java

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.Semaphore;

public class LockMap<Key> {

    private final ConcurrentHashMap<Key, Semaphore> map = new ConcurrentHashMap<Key, Semaphore>();

    public void lock(final Key key) throws InterruptedException {
        Semaphore sem = map.get(key);
        while (true) {
            if (sem == null) {
                // Try to create a new, already locked, semaphore for this key
                final Semaphore locked = new Semaphore(0);
                sem = map.putIfAbsent(key, locked);
                if (sem == locked)
                    return;
                // Someone got here before we could, no need to release this unused semaphore
            }
            // Acquire the semaphore, and ensure it is still the one corresponding to the key
            sem.acquire();
            final Semaphore recent = map.get(key);
            if (sem == recent)
                return;
            sem.release();
            sem = recent;
        }
    }

    public void unlock(final Key key) {
        // Release the semaphore and remove it from the map unless someone waits for it
        final Semaphore sem = map.get(key);
        if (!sem.hasQueuedThreads()) {
            map.remove(key);
        }
        sem.release();
    }
}