Sorting and Filtering Maps Using Generics
Assuming the requirement was to maintain initial map as immutable object -- just a few concerns re those new statements in sorting. They violate SRP, at least. Either accept already created (mutable) to populate with results, or (I prefer) accept a factory to get one. Same apples to collection step in filtering.

If, however, it is given that input map can be mutated during the process, then whole solution should be written with this in mind and, perhaps, stream is not the right choice here.