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