It turned out that CollectionFactory.createMap specifically supports MultiValueMap already but createApproximateMap does not. Also, createMap can easily instantiate common Map implementations directly, along the lines of #28718.