Thread safe multitons in Java

Question

Given the following multiton:

public class Multiton 
{
    private static final Multiton[] instances = new Multiton[...];

    private Multiton(...) 
    {
        //...
    }

    public static Multiton getInstance(int which) 
    {
        if(instances[which] == null) 
        {
            instances[which] = new Multiton(...);
        }

        return instances[which];
    }
}

How can we keep it thread safe and lazy without the expensive synchronization of the getInstance() method and the controversy of double-checked locking? An effective way for singletons is mentioned here but that doesn't seem to extend to multitons.

Answer 1

UPDATE: with Java 8, it can be even simpler:

public class Multiton {
    private static final ConcurrentMap<String, Multiton> multitons = new ConcurrentHashMap<>();

    private final String key;
    private Multiton(String key) { this.key = key; }

    public static Multiton getInstance(final String key) {
        return multitons.computeIfAbsent(key, Multiton::new);
    }
}

Mmm that's good!

---

ORIGINAL ANSWER

This is a solution which builds on the Memoizer pattern as described in JCiP. It uses a ConcurrentHashMap like one of the other answers, but instead of storing the Multiton instances directly, which can lead to creating unused instances, it stores the computation that leads to the creation of the Multiton. That additional layer solves the problem of unused instances.

public class Multiton {

    private static final ConcurrentMap<Integer, Future<Multiton>> multitons = new ConcurrentHashMap<>();
    private static final Callable<Multiton> creator = new Callable<Multiton>() {
        public Multiton call() { return new Multiton(); }
    };

    private Multiton(Strnig key) {}

    public static Multiton getInstance(final Integer key) throws InterruptedException, ExecutionException {
        Future<Multiton> f = multitons.get(key);
        if (f == null) {
            FutureTask<Multiton> ft = new FutureTask<>(creator);
            f = multitons.putIfAbsent(key, ft);
            if (f == null) {
                f = ft;
                ft.run();
            }
        }
        return f.get();
    }
}

Answer 2

This will provide you a threadsafe storage mechanism for your Multitons. The only downside is that it is possible to create a Multiton that will not be used in the putIfAbsent() call. The possibility is small but it does exist. Of course on the remote chance it does happen, it still causes no harm.

On the plus side, there is no preallocation or initialization required and no predefined size restrictions.

private static ConcurrentHashMap<Integer, Multiton> instances = new ConcurrentHashMap<Integer, Multiton>();

public static Multiton getInstance(int which) 
{
    Multiton result = instances.get(which);

    if (result == null) 
    {
        Multiton m = new Multiton(...);
        result = instances.putIfAbsent(which, m);

        if (result == null)
            result = m;
    }

    return result;
}

Answer 3

You could use an array of locks, to at least be able to get different instances concurrently:

private static final Multiton[] instances = new Multiton[...];
private static final Object[] locks = new Object[instances.length];

static {
    for (int i = 0; i < locks.length; i++) {
        locks[i] = new Object();
    }
}

private Multiton(...) {
    //...
}

public static Multiton getInstance(int which) {
    synchronized(locks[which]) {
        if(instances[which] == null) {
            instances[which] = new Multiton(...);
        }
        return instances[which];
    }
}

Answer 4

With the advent of Java 8 and some improvements in ConcurrentMap and lambdas it is now possible to implement a Multiton (and probably even a Singleton) in a much tidier fashion:

public class Multiton {
  // Map from the index to the item.
  private static final ConcurrentMap<Integer, Multiton> multitons = new ConcurrentHashMap<>();

  private Multiton() {
    // Possibly heavy construction.
  }

  // Get the instance associated with the specified key.
  public static Multiton getInstance(final Integer key) throws InterruptedException, ExecutionException {
    // Already made?
    Multiton m = multitons.get(key);
    if (m == null) {
      // Put it in - only create if still necessary.
      m = multitons.computeIfAbsent(key, k -> new Multiton());
    }
    return m;
  }
}

I suspect - although it would make me feel uncomfortable - that getInstance could be further minimised to:

// Get the instance associated with the specified key.
public static Multiton getInstance(final Integer key) throws InterruptedException, ExecutionException {
  // Put it in - only create if still necessary.
  return multitons.computeIfAbsent(key, k -> new Multiton());
}

Answer 5

You're looking for an AtomicReferenceArray.

public class Multiton {
  private static final AtomicReferenceArray<Multiton> instances = new AtomicReferenceArray<Multiton>(1000);

  private Multiton() {
  }

  public static Multiton getInstance(int which) {
    // One there already?
    Multiton it = instances.get(which);
    if (it == null) {
      // Lazy make.
      Multiton newIt = new Multiton();
      // Successful put?
      if ( instances.compareAndSet(which, null, newIt) ) {
        // Yes!
        it = newIt;
      } else {
        // One appeared as if by magic (another thread got there first).
        it = instances.get(which);
      }
    }

    return it;
  }
}