Thread-safe Map in Java

Question 1

For tasks of this nature, I highly recommend Guava caching support.

If you can't use that library, here is a compact implementation of a Multiton. Use of the FutureTask was a tip from assylias, here, via OldCurmudgeon.

public abstract class Cache<K, V>
{

  private final ConcurrentMap<K, Future<V>> cache = new ConcurrentHashMap<>();

  public final V get(K key)
    throws InterruptedException, ExecutionException
  {
    Future<V> ref = cache.get(key);
    if (ref == null) {
      FutureTask<V> task = new FutureTask<>(new Factory(key));
      ref = cache.putIfAbsent(key, task);
      if (ref == null) {
        task.run();
        ref = task;
      }
    }
    return ref.get();
  }

  protected abstract V create(K key)
    throws Exception;

  private final class Factory
    implements Callable<V>
  {

    private final K key;

    Factory(K key)
    {
      this.key = key;
    }

    @Override
    public V call()
      throws Exception
    {
      return create(key);
    }

  }

}

Question 2

I think you are looking for a Multiton.

There's a very good Java one here that @assylas posted some time ago.

Question 3

You can loosen the lock at the risk of an occasional doubly compiled stylesheet in race condition.

Object y;

// lock here if needed
y = map.get(x);
if(y == null) {
    y = compileNewY();

    // lock here if needed
    map.put(x, y); // this may happen twice, if put is t.s. one will be ignored
    y = map.get(x); // essential because other thread's y may have been put
}

This requires get and put to be atomic, which is true in the case of ConcurrentHashMap and you can achieve by wrapping individual calls to get and put with a lock in your class. (As I tried to explain with "lock here if needed" comments - the point being you only need to wrap individual calls, not have one big lock).

This is a standard thread safe pattern to use even with ConcurrentHashMap (and putIfAbsent) to minimize the cost of compiling twice. It still needs to be acceptable to compile twice sometimes, but it should be okay even if expensive.

By the way, you can solve that problem. Usually the above pattern isn't used with a heavy function like compileNewY but a lightweight constructor new Y(). e.g. do this:

class PrecompiledY {
    public volatile Y y;
    private final AtomicBoolean compiled = new AtomicBoolean(false);
    public void compile() {
        if(!compiled.getAndSet(true)) {
            y = compile();
        }
    }
}
// ...
ConcurrentMap<X, PrecompiledY> myMap; // alternatively use proper locking

py = map.get(x);
if(py == null) {
    py = new PrecompiledY(); // much cheaper than compiling

    map.put(x, y); // this may happen twice, if put is t.s. one will be ignored
    y = map.get(x); // essential because other thread's y may have been put
    y.compile(); // object that didn't get inserted never gets compiled
}

Also:

Alternatively, I know of the existence of a ConcurrentHashMap but I don't know if that's overkill.

Given that your code is heavily locking, ConcurrentHashMap is almost certainly far faster, so not overkill. (And much more likely to be bug-free. Concurrency bugs are not fun to fix.)

Question 4

Please see Erickson's comment below. Using double-checked locking with Hashmaps is not very smart

The compile method can take a few hundred milliseconds to return. This seems like a long time to have the object locked, but I don't see an alternative.

You can use double-checked locking, and note that you don't need any lock before get since you never remove anything from the map.

if(compiledStylesheets.containsKey(xslt)) {
    exec = compiledStylesheets.get(xslt);
} else {
    synchronized(compiledStylesheets) {
        if(compiledStylesheets.containsKey(xslt)) {
            // another thread might have created it while
            // this thread was waiting for lock
            exec = compiledStylesheets.get(xslt);
        } else {
            exec = compile(s, imports);
            compiledStylesheets.put(xslt, exec);
        }
    }
}

}

Also, it is unnecessary to use Collections.synchronizedMap in addition to the synchronized block, correct?

Correct

This is the only code that hits this object other than initialization/instantiation.

Question 5

First of all, the code as you posted it is race-condition-free because containsKey() result will never change while compile() method is running.

Collections.synchronizedMap() is useless for your case as stated above because it wraps all map methods into a synchronized block using either this as a mutex or another object you provided (for two-argument version).

IMO using ConcurrentHashMap is also not an option because it stripes locks based on key hashCode() result; its concurrent iterators is also useless here.

If you really want compile() out of synchronized block, you may pre-calculate if before checking containsKey(). This may draw the overall performance back, but may be better than calling it in synchronized block. To make a decision, personally I would consider how often key "miss" is happening and so, which option is preferrable - keep the lock for longer times or calculate your stuff always.