skip to content

How do `contains`/`in`, `indexOf`, and `indexOfFirst { }` work in Kotlin collections? What are the performance and equality considerations across List, Set, and Map?

level: seniorimportance: should knowfreq 55%

answer

  1. in → contains; !in negates
  2. indexOf / indexOfFirst return -1 when absent
  3. List contains is O(n); HashSet/HashMap O(1)
  4. key in map == containsKey
  5. mutating hashCode fields after insert breaks Set/Map lookups

basics

~20 s

x in list (or list.contains(x)) checks if an element is present. indexOf(x) returns its position or -1 if absent. indexOfFirst { } finds the position of the first element matching a condition, or -1. Sets and maps check membership much faster than lists.

solid answer

~40 s

The `in` operator desugars to `contains(element)`, returning a `Boolean`. On a `List` it is O(n) (linear scan using `equals`); on a `HashSet` it is amortized O(1) via `hashCode`/`equals`; `key in map` calls `containsKey` (O(1) for `HashMap`). `indexOf(element)` returns the first index whose element `equals` the argument, or `-1` if absent (`lastIndexOf` scans from the end). `indexOfFirst { p }` / `indexOfLast { p }` return the index of the first/last element satisfying a predicate, or `-1`. Equality uses structural `equals`/`hashCode`, so custom `data class`es work out of the box but mutable elements whose hash changes after insertion break `HashSet`/`HashMap` lookups. Because `in`/`indexOf` on a `List` are linear, repeated membership checks should use a `Set`. Ranges also support `in` (`x in 1..10`) via `contains`, and `!in` is the negation.

code

kotlin · 6 lines
kotlin
val names = listOf("amy", "bob", "cy", "bob")
val banned = setOf("bob")            // O(1) membership
val flagged = names.filter { it in banned }   // [bob, bob]
val firstBob = names.indexOf("bob")           // 1
val lastBob  = names.lastIndexOf("bob")       // 3
val firstLong = names.indexOfFirst { it.length > 2 } // 0

go deeper

for a junior

Uses x in list and indexOf, and knows -1 means not found.

for a middle

Maps in to contains/containsKey and uses indexOfFirst/indexOfLast for predicate positions.

for a senior

Reasons about O(n) List vs O(1) Set/Map, the equals/hashCode contract, and converting to a Set for repeated checks.

for a principal

Spots O(n·m) membership traps in reviews, guards against mutable-hash-key bugs, and chooses the collection type by access pattern.

## The in operator and contains `x in collection` is syntactic sugar for `collection.contains(x)`; `x !in collection` negates it. `contains` returns a `Boolean` and is defined on `Iterable`/`Collection`, `Set`, `Map` (as `containsKey`/`containsValue`), `CharSequence`, ranges, and arrays. ```kotlin val list = listOf("a", "b", "c") "b" in list // true == list.contains("b") "z" !in list // true val set = hashSetOf(1, 2, 3) 2 in set // true (O(1)) val map = mapOf(1 to "x") 1 in map // true == map.containsKey(1) 5 in 1..10 // true (IntRange.contains) ``` ## Finding positions - **`indexOf(element)`** → first index where `element == that` by structural `equals`, else `-1`. - **`lastIndexOf(element)`** → last such index, else `-1`. - **`indexOfFirst { predicate }`** → first index satisfying `predicate`, else `-1`. - **`indexOfLast { predicate }`** → last such index, else `-1`. ```kotlin val xs = listOf(10, 20, 30, 20) xs.indexOf(20) // 1 xs.lastIndexOf(20) // 3 xs.indexOfFirst { it > 15 } // 1 xs.indexOf(99) // -1 ``` `-1` is the universal 'not found' sentinel — guard with `if (i >= 0)` before using it as an index, or prefer `find`/`firstOrNull` when you want the element rather than its position. ## Equality & hashing Membership relies on `equals`/`hashCode`: - `List.contains`/`indexOf` use `equals` linearly. - `HashSet`/`HashMap` use `hashCode` to bucket, then `equals` to confirm — O(1) average. - A `data class` auto-generates correct `equals`/`hashCode`, so value-equal instances are found. - **Pitfall:** if you mutate a field that participates in `hashCode` after putting an object in a `HashSet`/`HashMap`, the bucket no longer matches and `in`/lookup can return false for an element that is physically present. ## Performance and choosing the right type | Operation | List | HashSet / HashMap | Sequence | |---|---|---|---| | `x in c` / contains | O(n) | O(1) avg | O(n), lazy scan | | `indexOf` / `indexOfFirst` | O(n) | n/a (no positions) | n/a | Repeated membership tests over a `List` are a classic O(n·m) trap — convert to a `Set` first (`val seen = list.toHashSet()`), then test with `in`. `Set`/`Map` have no positional `indexOf` because they are unordered. ## Sequences and ranges On a `Sequence`, `contains` is a terminal operation that short-circuits on the first match. Ranges implement an optimized `contains` (e.g. `IntRange` does a numeric comparison, not iteration), so `n in 1..1_000_000` is O(1).

  • Why prefer a Set over a List for repeated 'in' checks?
    List.contains is O(n) per check, so m checks are O(n·m); HashSet membership is O(1) average, making the whole loop O(n+m).
  • What does indexOf return when the element is absent, and why is that risky?
    It returns -1. Using that as an index throws IndexOutOfBoundsException, so you must guard with i >= 0 first.
  • How can an element be 'in' a HashSet by ==, yet fail a lookup?
    If a field used in hashCode is mutated after insertion, the element lands in the wrong bucket, so contains can return false even though it's present — never mutate hash-relevant fields of stored keys.

Searching a List with in is reading every name on a guest list; a HashSet is a hostess who knows instantly whether you're invited.

saying these in an interview costs you the question

  • Saying HashSet.contains is O(n) like List
  • Claiming indexOf returns null (it returns -1)
  • Thinking Set has indexOf / positional access
  • Ignoring equals/hashCode when discussing membership
  • Using a List for hot repeated membership checks

context

resolving links…