# UNDF: UNDF-2026-000000439
# kafka-0008 — ListDeserializer nullIndexList ArrayList.contains O(S×N) → HashSet O(S)

## Classification

| Field       | Value |
|-------------|-------|
| CWE         | CWE-407 Inefficient Algorithmic Complexity |
| Severity    | HIGH |
| Component   | `clients/src/main/java/org/apache/kafka/common/serialization/ListDeserializer.java` |
| Introduced  | Initial List serialization support |
| Status      | PATCHED (unit test PASS) |

## Defect

In `ListDeserializer.deserialize()`, when the CONSTANT_SIZE serialization strategy is used, a
`nullIndexList` of type `ArrayList<Integer>` is built from the wire-format null-index list.
The deserialization loop then checks `nullIndexList.contains(i)` for every index `i` from 0 to
`size - 1`:

```java
// DEFECTIVE — clients/src/main/java/org/apache/kafka/common/serialization/ListDeserializer.java:180-182
for (int i = 0; i < size; i++) {
    int entrySize = serStrategy == SerializationStrategy.CONSTANT_SIZE ? primitiveSize : dis.readInt();
    if (entrySize == ListSerde.NULL_ENTRY_VALUE || (nullIndexList != null && nullIndexList.contains(i))) {
```

`ArrayList.contains()` is O(N) where N = `nullIndexList.size()`.
The outer loop runs S times (S = total list entries).
Total: **O(S × N)**.

For a serialized list of 10 000 entries where half are null, S=10 000 and N=5 000,
giving ~50 000 000 comparisons instead of 10 000.

## Fix

Convert `nullIndexList` to a `HashSet<Integer>` after deserializing it (or build it as a HashSet
directly). `HashSet.contains()` is O(1), reducing the loop to O(S).

```java
// FIXED — deserializeNullIndexList returns Set<Integer>
private Set<Integer> deserializeNullIndexList(final DataInputStream dis) throws IOException {
    int nullIndexListSize = dis.readInt();
    Set<Integer> nullIndexSet = new HashSet<>(nullIndexListSize * 2);
    while (nullIndexListSize != 0) {
        nullIndexSet.add(dis.readInt());
        nullIndexListSize--;
    }
    return nullIndexSet;
}

// caller changes nullIndexList type to Set<Integer>
// nullIndexList.contains(i) → O(1)
```

## Complexity

| Scenario | Before | After | Ratio |
|----------|--------|-------|-------|
| S=100, N=50 | O(5 000) | O(100) | 50× |
| S=1 000, N=500 | O(500 000) | O(1 000) | 500× |
| S=10 000, N=5 000 | O(50 000 000) | O(10 000) | 5 000× |

## Speedup (measured)

See unit test `KafkaListDeserializerNullIndexTest.java`.
Measured ratio ≥ 5× at N=1 000 (SLOW ArrayList vs FAST HashSet).

## Affected File

```
clients/src/main/java/org/apache/kafka/common/serialization/ListDeserializer.java
  Line 151-158: deserializeNullIndexList — returns ArrayList, should return HashSet
  Line 173:     nullIndexList type should be Set<Integer>
  Line 182:     nullIndexList.contains(i) — O(N) per iteration
```
