📈 Benchmark 005: Set vs List .contains()

📘 Preface

The .contains() method is frequently used in both List and Set, or in any Collection. However, it behaves very differently internally. While Set offers near-constant-time O(1) lookups via hashing, List performs a linear search which is O(n). But do these big O time complexities mean anything in the real world...?

🔬 Test Case

@State(Scope.Thread)
@BenchmarkMode(Mode.AverageTime)
@Fork(1)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
public class BM_005_Contains {

  private static final List<String> WORDS =
      List.of(
          "apple",
          "banana",
          "orange",
          "grape",
          "kiwi",
          "mango",
          "peach",
          "pear",
          "pineapple",
          "strawberry",
          "watermelon",
          "blueberry",
          "raspberry",
          "blackberry",
          "cantaloupe",
          "honeydew",
          "papaya",
          "passionfruit",
          "pomegranate",
          "tangerine");

  @Param({"1", "4", "8"})
  private int amount;

  private List<String> integersList;
  private Set<String> integersSet;

  @Setup
  public void setup() {
    List<String> copy = new ArrayList<>(WORDS);
    Collections.shuffle(copy);
    copy = copy.subList(0, amount);

    this.integersList = List.copyOf(copy);
    this.integersSet = Set.copyOf(copy);
  }

  @Benchmark
  public void listContains(Blackhole bh) {
    for (var word : WORDS) {
      bh.consume(this.integersList.contains(word));
    }
  }

  @Benchmark
  public void setContains(Blackhole bh) {
    for (var word : WORDS) {
      bh.consume(this.integersSet.contains(word));
    }
  }
}

✅ Results

Benchmark                     (amount)  Mode  Cnt    Score   Error  Units
BM_005_Contains.listContains         1  avgt    5   23.898 ± 0.625  ns/op
BM_005_Contains.listContains         4  avgt    5  145.979 ± 2.757  ns/op
BM_005_Contains.listContains         8  avgt    5  210.008 ± 1.873  ns/op
BM_005_Contains.setContains          1  avgt    5   24.585 ± 0.347  ns/op
BM_005_Contains.setContains          4  avgt    5  140.540 ± 0.971  ns/op
BM_005_Contains.setContains          8  avgt    5  171.424 ± 1.643  ns/op

🔎 Findings

Turns out big O complexity isn't all there is, List.contains() easily matches Set.contains() when values are small, but once there are more elements, the benefits of hashing for Set becomes clearer.