If you really need to introduce this gradually, you will temporarily have two kind of maps in your program: one
Map<String, Object> type, and one
Map<MyEnum, Object> type. A conversion from the latter to the former is straight-forward, but a conversion from the former to the latter may not be possible as long as
MyEnum does not contain all the required keys.
So I guess your best bet is to identify subsections or classes in your code where you can introduce
Map<MyEnum, Object> in isolation, and where the conversion of
Map<String, Object> into
Map<MyEnum, Object> is not required, whilst the reverse conversion does not result in an unacceptable performance hit. Just call a conversion function at the borders between the already refactored code and the unrefactored parts, as long as the refactoring is not complete.
Since we do not know the structure of your actual code, I guess there is not much more which can be recommended here, and how viable this approach is. Of course, there is always the standard recommendation for such a kind of refactoring - provide enough automated regression tests before you start. Note also that once you change the type of
Map<String, Object> to
Map<MyEnum, Object> for one variable, the compiler will tell you if you forgot to refactor a place in you code where now either
MyEnum is required, or a conversion between those types. So I guess the refactoring is relatively safe and not too error-prone.
You can actually utilize the compiler error messages and unit tests for making different attempts for partial refacorings, and, whenever an attempt fails, undo all changes in source control and start with a different part of the codebase again. Ola Ellnestam and Daniel Brolund made a systematic approach of this refactoring technique and called it "The Mikado Method". I haven't read their book, so I cannot tell you if it is worth the price, but maybe the general idea is sufficient for you case.