Один общий Lock на всю структуру данных - самое простое и самое надёжное решение. Но у него есть цена: если под нагрузкой сотни потоков одновременно хотят обновить разные, никак не связанные между собой записи, все они всё равно выстраиваются в одну общую очередь, потому что блокировка одна на всех. Это называется contention (состязание за блокировку), и именно это чаще всего спрашивают на senior-собеседовании про оптимизацию многопоточного кода.