Java APIs

I have a multiple level class heirarchy and I'm storing them in a Map that maps their Class to a Set containing them. The problem is that when I attempt to add to the Set, I can't guarantee that I'm adding members of the same type.
For instance,

abstract class Animal {
....
}


class Dog extends Animal {
...
}

class Terrier extends Dog {
...
}

class Poodle extends Dog {
...
}



class Bird extends Animal {
...
}

class Pigeon extends Bird {
...
}

class Sparrow extends Bird {
...
}

...


final Map<Class, Set<? extends Animal>> map = new HashMap<Class, Set<? extends Animal>>();


Set<? extends Animal> getMembers(Class c) {
    if(!map.containsKey(c)) {
        map.put(c, new HashSet<? extends Animal>()); //How do I make sure that the Set is of type c?
    }
return map.get(c);
}

...

getMembers(Dog.class).add(new Dog()); //this gives me a compile error "cannot find method: add(Dog)". The add method takes type <? extends Animal>, so it should work, right?

I have a feeling that it is impossible because of erasure. If so, how do I work around this?