@clp: ieri sera prima di uscire dall'ufficio avrei voluto scriverti io praticamente le stesse cose ... magari solo un pochino più gentilmente. Ma poi non ne ho avuto tempo.
Il problema spero ti sia ben chiaro: HashMap, TreeMap e altre collezioni non sincronizzate, NON sono thread safe. Se vuoi usarle in modo concorrente, l'accesso allora va protetto con un lock. Se si usa il lock intrinseco di un oggetto si ha una "serializzazione" totale degli accessi (un solo thread per volta, indipendentemente da cosa voglia fare se lettura o modifica).
Si può fare di meglio con un lock "esplicito" (fornito dal framework) che fornisce "spezzati" i lock di lettura e di scrittura. Più thread possono accedere insieme in lettura ma la scrittura è comunque ancora esclusiva.
Detto questo, non è chiaro il motivo della tua richiesta iniziale. Per scopi "didattici"? Per altro? Il locking per chiave, forse hai capito, ha poco senso se "sotto" c'è la necessità di esclusività in scrittura. Potrebbe avere un pelino più senso solo se mi dicessi che vuoi proteggere e rendere "atomiche" delle operazioni di read-modify-write su una certa chiave, che andrebbero fatte in modo concettualmente similare al compute() di ConcurrentHashMap.