Tipos Java nativos (
int , float , String , Date , Map, etc) será codificado automaticamente para o tipo BSON correto, para que você possa usar um BasicDBObject para colocar o Map direto para a coleção mongo:// you probably want to be more specific with your generics than Object!
Map<Object,Object> map = new HashMap<Object,Object>();
map.put("1", "Department A");
map.put("2", "Department B");
collection.insert(new BasicDBObject(map));
No entanto, parece que seu
Map na verdade não tem a estrutura que você quer, então você precisa de algum tipo de mapeamento para a estrutura desejada. Use o mapeamento básico embutido no driver java (você está no caminho certo chamando BasicDBObject.put e aqui
há mais algumas idéias), ou use algo como Morphia para mapeamento estendido. 
