Как добавить новые данные в таблицу?

Метод setMap следует вызывать только в случае если вы только что создали экземпляр @Entity, и ещё не сохраняли его в БД. Если же сущность уже сохранена в БД, или считана из БД, то вместо интерфейса Map, объявленного в классе сущности, подставляется его реализация, связанная с функциями работы с БД. "Движок" JPA (обычно Hibernate) "видя", что на месте Map такая реализация, как бы "знает", что это связанные записи, которые уже сохранены в БД. Если же подменить целиком Map, то это "знание" теряется и начинается непредвиденное поведение.

Для модификации списка, хранимого в Map, следует вызывать методы Map.put и Map.remove:

entity.getMap().put(...);
entity.getMap().remove(child);

Hibernate отследит эти обращения и при сохранении родительской сущности корректно добавит/удалит дочерние объекты.

Можно сделать так же, как создаются "новая папка" "новая папка(1)"... "новая папка(3)"
т.е. добавить проверку, есть ли такой ключ в map, если есть, изменить переданное значение key на key(n), снова проверить нет ли такого ключа, и если есть изменить n на 1, и снова проверить, и если нету, то записать key(2)

з.ы. если вы где-то собираетесь запоминать ключи, то можно из метода setMap сделать return и вернуть "реальный" ключ, тот что получился, после его переименование.