Creating the hashmap is easy, you just pass the generic types through - or even use the diamond notation and have it done for you.
M m = new HashMap<>();
The complication is that you want to also be able to select the type of the Map. That can be done in a number of ways:
You could use the Factory pattern and pass in a factory object that creates the maps on demand.
You could generate the Map outside the class and pass it in on the constructor.
Have an abstract method to create the map. When creating an instance of the class people would implement that abstract method and generate the map for it.
For the second question there's no way to know without a lot more detail of what you are doing. That's an architectural decision and would most likely not fit into a stack overflow Q & A. This all seems a bit messy though, you are exposing a lot of the internal behavior of the classes. You would probably be better off thinking more about the behavior you want and the interface to provide that rather than the details of implementation.
For example you could have an enum { UNSORTED, INSERTION_ORDER, etc }
and then instantiate the right Map based on that enum.