In short: If Client cares about the parameters after the fact, then it should create a defensive deep copy of the map (not only the map, but also of the values). If Service needs to modify the collection, then it should create a defensive copy. But we can do better...
To safely pass the Map (though not to safely pass its contents), Client does not need to copy the map, it can use Collections.unmodifiableMap() to create an unmodifiable view.
If Client cares about the map after the fact, then it probably also cares about the contents of the map. Does Client know how to make a defensive copy of all subclasses of Object that will be included in the map? If the actual Objects being used are immutable types, then Client doesn't need to know how to make a defensive copy of them, and passing the unmodifiable collection is sufficient.
If the actual
Objects being used are mutable types, then Client needs to make a deep copy of them, or needs to send copies (or immutables) of whatever Service is going to do with the map. For example, if Service actually intends to call
.toString() on all Objects in the map, then maybe the contract can be changed such that Service accepts a
Map<String, String>. Maybe Service is a bit more clever, and can also handle
Objects that might implement
Collection, and uses the
.toString() method for non-collections, but iterates over collections and calls the
.toString() on each of those. If that is the case, perhaps Client can contain the logic for getting to that step, and the contract changed to
Map<String, List<String>>; remember to pass unmodifiable views of the collections, and not the collections themselves.
Wherever possible, I prefer to pass unmodifiable views or immutable collections (for example, from the Guava library), containing immutable objects. If Service actually needs to modify the collection it should be making a copy (because it should know that side effects are generally undesirable), deep if necessary. You will find out in testing if Service actually does produce side effects, because it will throw an exception when trying to modify the unmodifiable/immutable collection, in which case Client needs to create a mutable copy of the collection, pass that, and then never use it again.