Java中Set.of()、Map.of()创建的集合的时间复杂度及操作性能问询

Great question! Let's break down the time complexity details for Java's Set.of() and Map.of() clearly, since there's a common misconception around their lookup performance.

1. Creation Phase Time Complexity #

For both Set.of(...) and Map.of(...), the time complexity of creating the collection is O(n), where n is the number of elements (or key-value pairs) you pass in. Here's why:

• The implementation needs to iterate over every input element to initialize the underlying storage.
• For Set.of(), there's an extra check for duplicate elements during iteration—each new element is compared to existing ones to enforce uniqueness, which adds another linear-time step.
• Even when using the fixed-parameter overloads (like Set.of(a, b, c)), the logic still processes n elements, so the linear time complexity holds.

2. contains() (Set) & get() (Map) Operation Time Complexity #

This is where many developers get tripped up: these immutable collections do NOT offer O(1) lookup performance in most cases. The complexity depends on the size of the collection:

• Empty or singleton collections: Operations are O(1). There's no need to iterate—we can immediately confirm an element doesn't exist (empty set) or return the only element/value (singleton).
• Collections with 2–10 elements: The underlying storage is a simple array. contains() and get() work by iterating through the array and comparing elements/keys using equals(), so time complexity is O(n).
• Collections with 10+ elements: Even for larger sets/maps created via varargs or Set.copyOf()/Map.copyOf(), the implementation still uses an array under the hood. Lookups require a full linear scan, so complexity remains O(n).

The design priority here is memory efficiency and fast creation, not optimized lookup speed. If you need O(1) lookup performance for immutable collections, consider using implementations like Guava's ImmutableSet/ImmutableMap, or wrap a HashSet/HashMap with Collections.unmodifiableSet()/Collections.unmodifiableMap().

内容的提问来源于stack exchange，提问作者Vitalii