This is the best I could come up with:

http://pastebin.com/ch9ht9Q5

Its big but hopefully avoids synchronization once most indices have been initialized.

I'm done with this, thanks all of you for your suggestions and ideas!

It is not thread safe to access a variable like resolvedMap like that, where some access is synchronized and others are not. Even though some operations are "reads", you cannot guarantee the state is safe to read from if another thread is changing the state. Also, there is multi-processor consistency, to ensure other processors will see the changed value.

ConcurrentHashMap is lock free in the way you appear to be looking for:

However, even though all operations are thread-safe, retrieval operations do not entail locking, and there is not any support for locking the entire table in a way that prevents all access.

It is not thread safe to access a variable like resolvedMap like that, where some access is synchronized and others are not. Even though some operations are "reads", you cannot guarantee the state is safe to read from if another thread is changing the state.

That's the idea, first access isn't supposed to be thread safe at all, is the second access that does the trick. Unless I'm missing something, if a thread changes resolvedMap inside the synchronized block, the change should be visible at least for the next thread that enters the synchronized block right?

Logic is this:

Two threads enter the method, two threads retrieve the index, two threads see its null at the same time.

Now here is the locking, one thread reaches the synchronized fallback method call, the other thread has to wait.

This is the first thing the synchronized block tries to do:

1. Integer i = resolvedMap.get( type );
3. if ( i != null )
4. {
5. return i.intValue();
6. }

It tries to retrieve the same value again. Since it was null before, it will still be null, so the thread will follow the rest of the code and initialize the index, thus finishing executing the synchronized method and releasing the lock.

So far we've added a value to resolvedMap inside the synchronized block.

Now second thread enters the synchronized fallback method, and tries to retrieve the same value again (like the previous thread did before) and this time it isn't null so it has to return.

It doesn't matters if the change is made visible outside the synchronized block in a later time, as long as the change made inside it is visible for the next thread that enters the synchronized fallback method, it will work I think.

The idea is that first time, no matter how many threads try to get the index for the same class, they'll get all blocked, first thread that grabs the lock will initialize the value for the rest, then the others will retrieve that same value again in an orderly fashion.

After that, when the change is visible to other threads in a later time, all further calls for that same index will never reach the synchronized block.

Now the thing is ConcurrentHashMaps solve the access thing, but not the whole other operations I need to do. Say that I remove the synchronization and replace the HashMaps with Concurrent ones:

Two threads enter the same method, two threads ask for the same index, the two will see a null value, so the two threads will try to execute the initialization method, and since it isn't synchronized, they'll overwrite each other. The only advantage is that once a thread reaches the put() call, it will be made visible everywhere else, but that doesn't solves my race condition if other threads already entered the initialization method.

I know what you're trying to do, it is called double checked locking, and unfortunately it is not guaranteed to work in Java. The synchronized keyword is not just a lock, it also inhibits certain optimisations that would be correct in single threaded code but that can cause issues in the presence of concurrency.

In addition, it is explicitly stated that HashMap is unsafe to read while another thread is updating it:

Note that this implementation is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.)

A concurrent hash map has the properties you need.

Now the thing is ConcurrentHashMaps solve the access thing, but not the whole other operations I need to do. Say that I remove the synchronization and replace the HashMaps with Concurrent ones:

You don't remove the synchronized block - you still need that as you correctly point out. However, by using a ConcurrentHashMap with the synchronized block, you can get the lock-free optimisation you are trying to implement, in a way that is guaranteed to work.

I see. So the problem is that, while the next thread will see it as initialized, since the "put()" operation is done inside the synchronized block, the constructor might not be finished in time before the object gets retrieved by the next thread.

So what you're proposing is using a ConcurrentHashMap instead of a HashMap. I'm not seeing how that changes the constructor issue?

The documentation for the java.util.concurrent package states:

Memory Consistency Properties

Chapter 17 of The Java™ Language Specification defines the happens-before relation on memory operations such as reads and writes of shared variables. The results of a write by one thread are guaranteed to be visible to a read by another thread only if the write operation happens-before the read operation. The synchronized andvolatile constructs, as well as the Thread.start() and Thread.join() methods, can form happens-before relationships. In particular:

• Each action in a thread happens-before every action in that thread that comes later in the program's order.
• An unlock (synchronized block or method exit) of a monitor happens-before every subsequent lock (synchronized block or method entry) of that same monitor. And because the happens-before relation is transitive, all actions of a thread prior to unlocking happen-before all actions subsequent to any thread locking that monitor.
• A write to a volatile field happens-before every subsequent read of that same field. Writes and reads of volatile fields have similar memory consistency effects as entering and exiting monitors, but do not entail mutual exclusion locking.
• A call to start on a thread happens-before any action in the started thread.
• All actions in a thread happen-before any other thread successfully returns from a join on that thread.

The methods of all classes in java.util.concurrent and its subpackages extend these guarantees to higher-level synchronization. In particular:

• Actions in a thread prior to placing an object into any concurrent collection happen-before actions subsequent to the access or removal of that element from the collection in another thread.
• Actions in a thread prior to the submission of a Runnable to an Executor happen-before its execution begins. Similarly for Callables submitted to an ExecutorService.
• Actions taken by the asynchronous computation represented by a Future happen-before actions subsequent to the retrieval of the result via Future.get() in another thread.
• Actions prior to "releasing" synchronizer methods such as Lock.unlock, Semaphore.release, and CountDownLatch.countDown happen-before actions subsequent to a successful "acquiring" method such as Lock.lock, Semaphore.acquire, Condition.await, and CountDownLatch.await on the same synchronizer object in another thread.
• For each pair of threads that successfully exchange objects via an Exchanger, actions prior to the exchange() in each thread happen-before those subsequent to the corresponding exchange() in another thread.
• Actions prior to calling CyclicBarrier.await and Phaser.awaitAdvance (as well as its variants) happen-before actions performed by the barrier action, and actions performed by the barrier action happen-before actions subsequent to a successful return from the corresponding await in other threads.

The implementation of ConcurrentHashMap must do whatever it needs under the hood to ensure these properties.

All right then, I replaced the HashMaps with ConcurrentHashMaps. Thanks a lot for the feedback :D