Hash Tables

Group by Key

Build buckets keyed by a shared field, preserving the first-seen key order.

Algorithm

Canonical pairs (a,1), (b,2), (a,3), (c,4), (b,5) print {a: [1, 3], b: [2, 5], c: [4]}. The replay uses the same input in every language, so this Kotlin DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.kt 
fun main() {
    val pairs = listOf("a" to 1, "b" to 2, "a" to 3, "c" to 4, "b" to 5)
    val groups = linkedMapOf<String, MutableList<Int>>()
    for ((key, value) in pairs) {
        groups.getOrPut(key) { mutableListOf() }.add(value)
    }
    val parts = groups.map { (key, values) -> "$key: [${values.joinToString(", ")}]" }
    println("{${parts.joinToString(", ")}}")
}

Complexity

  • Time: O(n) average
  • Space: O(k + n) for buckets and values

Implementation notes

  • Keep output formatting deterministic. Do not rely on unordered hash-map printing when the lesson needs cross-language comparison.
  • The trace highlights the hash table state after each write.
bucket map Each key owns a list. A new key creates a bucket; a repeated key appends to the existing bucket.