HashMap is not a thread safe class. Removing the sync will create potential deadlocks.

https://www.google.ca/search?q=hashmap+deadlock

Can you use a ConcurrentHashMap and make sure that there are no possible ConcurrentModificationException if any of the methods are called in parallel?