skip to content

What contract must an element type satisfy for a Kotlin Set (or Map key) to deduplicate correctly, and what breaks if you use a mutable object as a key?

level: seniorimportance: must knowfreq 55%

answer

  1. hashCode picks bucket, equals confirms
  2. equal => same hashCode (mandatory)
  3. data class generates both from ctor props
  4. mutate hashed field => lost element
  5. arrays use identity equality

basics

~20 s

Sets and map keys decide 'same element' using equals() and hashCode(). If two objects are equal they must have the same hashCode. If you change a key after inserting it, the set can no longer find it.

solid answer

~40 s

LinkedHashSet/LinkedHashMap are hash tables: an element's hashCode picks a bucket, then equals confirms identity within it. The contract: equal objects (a.equals(b)) MUST return equal hashCodes, hashCode must be stable while the object is in the set, and equals must be reflexive/symmetric/transitive/consistent. Data classes generate both from their properties, so they deduplicate by value — that's why setOf(Point(1,2), Point(1,2)) has size 1. Plain classes use identity (===) unless you override both. Mutating a field that participates in equals/hashCode after insertion corrupts the structure: the element lands in the old bucket, lookups hash to a new bucket, and contains() returns false for an element that's physically present — a 'lost key'. Use immutable keys (val properties), or never mutate equality-relevant fields while in the set.

code

kotlin · 8 lines
kotlin
data class Key(val id: Int)
val m = hashMapOf(Key(1) to "a")
println(m[Key(1)]) // "a" — value equality finds it

class Bad(var id: Int) { override fun hashCode() = id; override fun equals(o: Any?) = (o as? Bad)?.id == id }
val k = Bad(1); val mm = hashMapOf(k to "x")
k.id = 2
println(mm[k]) // null — key was hashed under 1

go deeper

for a junior

Knows sets use equals/hashCode and that data classes deduplicate by value.

for a middle

States the 'equal implies equal hashCode' rule and that overriding one requires the other.

for a senior

Explains the bucket/equals mechanism and diagnoses the mutable-key lost-element bug; knows only ctor props count and arrays use identity.

for a principal

Reasons about contract guarantees across module/serialization boundaries, hashCode stability, collision behavior, and immutable-key design as an invariant.

## How a hash-based Set decides uniqueness A `LinkedHashSet`/`HashSet` stores elements in buckets indexed by `hashCode()`. To check membership or insert: 1. Compute `element.hashCode()` -> pick a bucket. 2. Within that bucket, compare candidates with `equals()`. So **two methods** define identity. The same applies to `Map` **keys**. ## The equals/hashCode contract - If `a == b` (i.e. `a.equals(b)`), then `a.hashCode() == b.hashCode()` — **mandatory**. - `hashCode()` must stay **stable** while the object resides in the set. - `equals` must be reflexive, symmetric, transitive, and consistent. - Unequal objects *may* share a hashCode (a collision — allowed, just slower). Violating 'equal implies equal hash' means equal objects land in different buckets and the set fails to deduplicate. ## Data classes do the right thing ```kotlin data class Point(val x: Int, val y: Int) val s = setOf(Point(1, 2), Point(1, 2)) println(s.size) // 1 -> value equality from generated equals/hashCode ``` `data class` auto-generates `equals`/`hashCode` from the **primary-constructor** properties. A non-data class uses **referential identity** (`===`) unless you override both. ## The mutable-key disaster ```kotlin class MutPoint(var x: Int, var y: Int) { override fun equals(o: Any?) = o is MutPoint && o.x == x && o.y == y override fun hashCode() = 31 * x + y } val set = hashSetOf(MutPoint(1, 1)) val p = set.first() p.x = 99 // mutate a hashed field! println(set.contains(p)) // false — it now hashes to a different bucket ``` The element is still in the set's old bucket, but `contains`/`remove` hash by the **new** value and look in the wrong bucket. Result: a 'leaked' element you can iterate over but can't find or delete. Same hazard for map keys. ## Rules of thumb - Prefer **immutable** keys/elements: `val` properties, ideally `data class`. - If you must use a mutable type, **never mutate equality-relevant fields** while it's a key/element; remove, mutate, re-insert. - Only properties in the **primary constructor** feed a data class's generated methods; properties in the body are ignored. - Beware arrays as keys: `Array.equals`/`hashCode` are identity-based, so `arrayOf(1) != arrayOf(1)` for set purposes.

  • Why does setOf(Point(1,2), Point(1,2)) have size 1 for a data class but size 2 for a plain class?
    A data class generates value-based equals/hashCode, so the two instances are equal. A plain class falls back to identity equality, so two distinct instances are unequal and both are kept.
  • Are properties declared in a data class body included in equals/hashCode?
    No. Only properties in the primary constructor feed the generated equals/hashCode/toString; body-declared properties are excluded.

hashCode is the aisle number, equals is reading the label. Change an item's aisle after shelving it and the store can't find it even though it's right there.

saying these in an interview costs you the question

  • Overriding equals but not hashCode (or vice versa)
  • Thinking a Set dedups by identity for data classes
  • Believing mutating a key is harmless
  • Saying unequal objects must have different hashCodes
  • Using a raw Array as a map key expecting value equality

context

resolving links…