Hash Tables

Frequency Count

Walk a sequence and count occurrences of each value in a map. Classic "get current count, add one, write back" loop.

Algorithm

Canonical input ["fig", "apple", "fig", "pear", "apple", "fig"] produces the final map {fig: 3, apple: 2, pear: 1}.

Basic Implementation

basic.kt 
fun main() {
	val words = arrayOf("fig", "apple", "fig", "pear", "apple", "fig")
	val counts = HashMap<String, Int>()
	val order = mutableListOf<String>()
	for (i in words.indices) {
		val word = words[i]
		if (!counts.containsKey(word)) {
			order.add(word)
			counts[word] = 1
		} else {
			val prev = counts[word]!!
			counts[word] = prev + 1
		}
	}
	print("{")
	for (i in order.indices) {
		if (i > 0) {
			print(", ")
		}
		val key = order[i]
		print("$key: ${counts[key]}")
	}
	println("}")
}

Complexity

  • Time: O(n) average with HashMap<String, Int>.
  • Space: O(k) where k is the number of distinct keys.

Implementation notes

  • Kotlin: val counts = HashMap<String, Int>() is the idiomatic map; the counts.containsKey(word) predicate plus an explicit assignment keeps the lesson on the read-or-default path without hiding it behind getOrDefault or getOrPut.
  • The auxiliary order list preserves first-seen order so the final printout is deterministic — HashMap iteration order is not a contract you can rely on.
  • The replay renders the map as a list of key/value rows in first-seen order and animates the count increment on each frame.
get-or-default A first-time `word` triggers the "default" branch: append to `order` and set `counts[word] = 1`. A repeat read-modify-writes `counts[word] = prev + 1`.
first-seen order Keys are tracked in `order` (a `MutableList<String>`) to keep the printout deterministic; the `HashMap` iteration order is not a contract.