Hash Maps & Sets

The most useful structure in app code

A hash map (also called dictionary, HashMap, or Map) stores key → value pairs and lets you look up a value by its key in O(1) on average. If you learn one structure deeply as a mobile developer, make it this one — it solves a huge range of performance problems.

val userById = HashMap<Int, User>()
userById[1] = User(1, "Anand")
val user = userById[1]          // O(1) lookup
val exists = userById.containsKey(2)   // O(1)

How hashing works (the intuition)

A hash map runs the key through a hash function that turns it into an array index, then stores the value there. Looking up later re-hashes the key to jump straight to the slot — no scanning. When two keys hash to the same slot (a “collision”), the map handles it (e.g. with a small list per slot). This is why lookups are O(1) on average, though O(n) in the rare worst case.

Sets: membership without duplicates

A set is a hash map with keys only — it stores unique values and answers “is X in here?” in O(1). Perfect for deduplication and fast checks.

val seenIds = HashSet<String>()
if (seenIds.add(postId)) {
    // add() returns false if it was already there -> dedupe feeds easily
    show(post)
}

Real mobile use cases

• In-memory cache — map an id to a loaded object so you don’t refetch.
• “Liked / selected” tracking — a set of ids for O(1) checks while scrolling.
• Deduplicating a paginated feed (the same item can arrive twice).
• Counting / grouping — map a key to a count or a list (group items by category).
• Fast joins — index one list by id, then look up matches instead of nested loops.

Replacing a nested loop with a map

// O(n²): for each order, scan users
for (order in orders) {
    val user = users.find { it.id == order.userId }   // O(n) each!
}

// O(n): index users once, then O(1) lookups
val userMap = users.associateBy { it.id }
for (order in orders) {
    val user = userMap[order.userId]                  // O(1)
}

This single pattern — “index by id, then look up” — fixes a large share of mobile performance problems.

Keys must hash and equal correctly

Hash maps rely on keys having proper hashCode/equals (Kotlin data class and Swift Hashable give you these). If you use a custom object as a key without correct equality, lookups silently fail — a subtle bug.

Memory trade-off

Hash maps use more memory than a plain list (extra slots, load factor). On mobile that’s usually a worthwhile trade for speed — but don’t cache unbounded amounts in a map, or you’ll get killed for memory (use an LRU cache, covered next).

Common mistakes

• Scanning a list when a map/set would be O(1).
• Using a mutable or improperly-equalsed object as a key.
• Letting an in-memory map grow without bound (memory pressure).

Summary: Hash maps give O(1) key lookups; sets give O(1) membership and dedupe. Use the “index by id, then look up” pattern to kill nested loops, ensure keys have correct hashing/equality, and bound your in-memory caches.