6

I wanted to create an immutable hashMap inline using the new factory method Map.ofEntries() in Java 9, for example:

Map<Integer, String> map = Map.ofEntries(
    Map.entry(1, "One"),
    Map.entry(2, "Two"),
    Map.entry(3, "Three"));

Then to my surprise, I found I could not create an immutable hashMap the same way! For example, the following code would not work.

HashMap<Integer, String> map = HashMap.ofEntries( //not work
    Map.entry(1, "One"),
    Map.entry(2, "Two"),
    Map.entry(3, "Three"));

Then when I want to check what type of map is returned by the factory method, I found the following note:

Callers should make no assumptions about the identity of the returned instances.

So my question is, is the access time complexity of an immutable map the same as a hashMap which is o(1)? If not, how to create a map that is both immutable and access o(1) at the same time? It would be best if it can be created inline.

Frank Mi
  • 452
  • 3
  • 11
  • related https://stackoverflow.com/questions/9043254/how-to-get-a-immutable-collection-from-java-hashmap – Ryuzaki L Sep 20 '19 at 21:25
  • You expect that `.ofEntries` would return an instance of a concrete class `HashMap` but it returns a (different) implementation of interface `Map`. Sure it won't work. – 9000 Sep 20 '19 at 21:28
  • 4
    Why is it so important to create a HashMap? What’s wrong with a plain Map? – VGR Sep 20 '19 at 21:56
  • One approach for really immutable maps (and not only *unmodifiable* maps) is (ignoring Guava or other third-party libraries): `Map immutableMap = Collections.unmodifiableMap(new LinkedHashMap(realMap));`. Also see https://stackoverflow.com/a/22636750/3182664 – Marco13 Sep 21 '19 at 11:25
  • @VGR The question in your comment, as it is currently phrased, does not make sense, *unless* you already know the answer or what the question is aiming at. But I think the last paragraph from the question makes clear that the point is not to "know" that it **is** a `HashMap`, but only to be sure that the returned map has the same complexity characteristics as a `HashMap` - namely, mainly, O(1) for `get`. – Marco13 Sep 21 '19 at 13:43
  • @Marco13 or `Map immutableMap = Map.copyOf(realMap);` And the time complexity [has been discussed only one month before this question](https://stackoverflow.com/q/57557125/2711488)… – Holger Sep 24 '19 at 16:09
  • @Holger That's right. Although the `LinkedHashMap` approach works for Java `<9`, **and** has the guarantees about the complexity, for that matter... – Marco13 Sep 24 '19 at 23:43
  • @Marco13 well, this is a Java 9 question and I wouldn’t worry about the time complexity, as I suppose, if a JRE vendor decides to use a different implementation, they do it for a good reason. – Holger Sep 25 '19 at 09:52
  • @Holger To be honest: The `of`-methods only accept so few parameters that even returning a "list-based map" (with O(n) for `get`) would rarely make a difference in practice - but there's nothing wrong with asking, of course. – Marco13 Sep 25 '19 at 12:04
  • @Marco13 there’s also the varargs method `Map.ofEntries(…)` and since Java 10, you can use `Map.copyOf(existingMap)` which has no size limit. But indeed, having a fixed size and unspecified implementations implies that the time complexity may become pointless, as it tells, how an implementation scales while constant maps do not need to scale. E.g. `Set.of("foo", "bar")` will return a special implementation which had an `O(n)` lookup time complexity, if it wasn’t limited to at most two elements anyway… – Holger Sep 25 '19 at 12:21

1 Answers1

16

Mutability or immutability are not directly related to the complexity of the access operation in a Map. For instance, a HashMap will always be O(1) for the get() operation, whereas a TreeMap will be O(log n). It's the implementing class of the Map interface that determines the complexity of the operations.

Besides it's always been possible to create unmodifiable maps, because we can make any Map of any concrete type immutable after we put items on it, like this:

Map<Integer, String> immutableMap = Collections.unmodifiableMap(mutableMap);

To be clear, HashMap.ofEntries() won't work because the ofEntries() method is static and defined in the Map interface, not in any of its implementing classes.

And you should not worry about being unable to declare the type of a map as HashMap or some other concrete class, anyway the best practice is to declare the map as being of a Map interface.

Also, if you were using a version older than Java 9 and don't mind using an external library, you can use ImmutableMap from Guava:

Map<Integer, String> immutableMap = ImmutableMap.of(key1, val1, key2, val2);

Perhaps reading this article will clarify things a bit more.

Óscar López
  • 232,561
  • 37
  • 312
  • 386
  • 7
    Just the usual reminder: `immutableMap` is itself immutable, but can be altered, when someone alters `mutableMap`. – Tom Sep 20 '19 at 21:30
  • Is it possible to know what is the class type of the implementing object returned by the factory method `Map.ofEntries()`? If so, I can have an idea of its time complexity. – Frank Mi Sep 20 '19 at 21:36
  • @FrankMi Just look into the implementation. Your IDE should allow you to do so. That method `AbstractImmutableMap` defined in `java.util.ImmutableCollections` – Tom Sep 20 '19 at 21:38
  • 3
    Sure, just print the result of `.getClass()` on the object. But as it says in the documentation, it's an _implementation detail_ and it can change at any moment. That's why we should assign the result of `Map.ofEntries()` to a `Map` interface, not a concrete implementation class. – Óscar López Sep 20 '19 at 21:38
  • @ÓscarLópez it returns `class java.util.ImmutableCollections$MapN` which is beyond my knowledge... Do you how to get its complexity? But I agree with you and I will not depend on its returning type. – Frank Mi Sep 20 '19 at 21:48
  • 1
    It's reasonable to assume that it's `O(1)` for the `get()` operation, any decent implementation of a non-sorted map should be `O(1)`. If it weren't, it'd say so in the documentation. – Óscar López Sep 20 '19 at 21:51
  • @Tom Sorry, I didn't get it. What do you mean my IDE should allow me to do? – Frank Mi Sep 20 '19 at 21:54
  • @ÓscarLópez Thank you. It helps me a lot! – Frank Mi Sep 20 '19 at 21:57
  • @FrankMi An IDE allows you to jump into the implementation of methods/classes, usally by left click why you hold CTRL key. There you then can see the implementation. – Tom Sep 20 '19 at 22:18
  • What Tom pointed out in the first comment is also detailed (with an example) in https://stackoverflow.com/a/22636750/3182664 – Marco13 Sep 21 '19 at 11:24
  • @Holger I didn't mention any "advantages" in my answer, it's just an alternative, in case someone is wondering how to do this pre-Java 9 – Óscar López Sep 24 '19 at 16:23
  • @Óscar López At least in Java 11, looking at the code, Map.ofEntries is O(n). – Jonathan Rosenne Feb 28 '21 at 21:55