ADDITIONAL SYSTEM INFORMATION :
JDK 21,23 (OpenJDK, Oracle, Amazon)
Linux AMD64

A DESCRIPTION OF THE PROBLEM :
Set<Integer>::contains of an unmodifiable Set (java.utils.ImmutableCollections.SetN) shows seriously degraded performance (factor 10⁴-10⁵) compared to HashSet under certain unclear conditions, presumably when searching a set of small values for a large value.

In the code example, searchSet is searched 100,000 times for searchVal, taking as much time as a modifiable HashSet would take for about 1,000,000,000 times (O(10⁰) seconds).

Case II is special in the following way:
if setMin = 0x16, performance is even 2 times worse than case I,
but if setMin = 0, performance miraculously is in the range of a modifiable HashSet,
also, if searchVal is within [setMin..setMax]

Generally, the runtime of Set::contains appears non-const and to be related to searchVal.


---------- BEGIN SOURCE ----------
import java.util.stream.Collectors;
import java.util.stream.IntStream;
…
// prepare Set to search in
        final int searchVal = 0x21ffff;
        final int setMin = 0x0;
        final int setMax = 0xffff;
        final var searchSet = IntStream.concat(
                IntStream.rangeClosed(setMin, setMax),
                IntStream.of(searchVal))
                .boxed().collect(Collectors.toUnmodifiableSet()); // <--- or Collectors.toSet()

// search (end - start) times in searchSet for searchVal
// take System.nanoTime();
        final int start = 2_200_000;
        final int end = 2_300_000;
        IntStream.range(start, end).forEach((val) -> {
// case I
            if (searchSet.contains(val)) {
                System.out.println("---> found (case I)");
            }
// case II
/* if (searchSet.contains(searchVal)) {
                if (val == searchVal) {
                    System.out.println("---> found (case II)");
                }
            }
*/
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
using a modifiable Set (HashSet, Collectors.toSet() )

FREQUENCY : always