راه اول که یک map کاملا sync است استفاده از SyncronizedMap است که همانطور که خود شما اشاره کردید در هر لحظه تنها یک thrad امکان کار با آن map را دارد. ولی همانطور که واضح است این نوع ساختمان داده ها اشکال performance دارند. یعنی در محیط های چند نخی، امن و کند هستند.
برای اینکه این مشکل کمی بهتر شود می توانید از کلاس java.util.concurrent.ConcurrentHashMap استفاده کنید. این کلاس به جای اینکه یک آبجکت lock به ازای همه عناصر map ایجاد کند، عناصر map را به 16 بخش تقسیم می کند و برای هر کدام ازین بخش ها یک آبجکت lock در نظر می گیرد. بنابر این در بهترین حالت 16 thread به صورت همزمان می توانند با این map به طور thread safe کار کنند. تا جایی که یادم میاد می شه این تقسیم بندی رو بهینه تر هم کرد.