CODEWITHSUNDEEP
javacollectionsjava-9
Vitalii
Vitalii

Reputation: 11071

What is a time complexity for sets and maps created with a factory methods Set.of() and Map.of()?

In Java, when I create a set with Set.of() or a map with Map.of() what is the time complexity of the contains and get operations? Is it O(1)?

Upvotes: 1

Views: 206

Answers (1)

Stuart Marks
Stuart Marks

Reputation: 132390

The Set.of and Map.of APIs return instances of JDK-private implementations. The performance of these implementations is not guaranteed by the specification. However, the APIs do return specific implementations about which performance statements can be made. Thus, the question is reasonable and is distinct from a (hypothetical) question such as "What is the performance of Map.get?" which is a poor question because there are many different Map implementations.

In any case, the implementations behind Set.of (for size greater than two) and Map.of (for size greater than one) use a simple open addressed hashing scheme with linear probing for collision resolution. The Set.contains and Map.get operations are O(1) if the elements' (keys') hashes are reasonably well distributed.

Upvotes: 5

Related Questions