I'm writing a simple IDictionary abstraction in C# that wraps a Dictionary<K, ICollection<V>>. Basically, it maps multiple values to one key. I can't decide whether to remove a key and its empty list when the last item in a values list is removed, or leave it (to avoid instantiating a new collection if the key is reused) and do checks on a key's values' Count when determining whether a key exists.
I would remove the collections so that your MultiMap has consistent behavior. If I used your MultiMap I would be very surprised (and unhappy) to find that a missing key behaves differently depending on whether a key was previously in the MultiMap or not.
Does Clear() remove the the Collections?
You may also create an unintended memory leak if you do not remove the collections. A developer may add many items, then remove them. Memory usage (after GC) should return to the same amount as before those items were added.
I would not worry about the cost of creating Collections. I would worry about the contract you create for your MultiMap. If after profiling your application you find that to be a concerned, you could modify or create a special MultiMap for that behavior. Don't fall into the trap of premature optimization.