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.scala 
import scala.collection.mutable.{HashMap, ArrayBuffer}

object Main {
	def main(args: Array[String]): Unit = {
		val words = Array("fig", "apple", "fig", "pear", "apple", "fig")
		val counts = HashMap.empty[String, Int]
		val order = ArrayBuffer.empty[String]
		for (i <- words.indices) {
			val word = words(i)
			if (!counts.contains(word)) {
				order += word
				counts(word) = 1
			} else {
				val prev = counts(word)
				counts(word) = prev + 1
			}
		}
		print("{")
		for (i <- order.indices) {
			if (i > 0) {
				print(", ")
			}
			val key = order(i)
			print(s"$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

  • Scala: val counts = HashMap.empty[String, Int] is the idiomatic mutable map; the counts.contains(word) predicate plus an explicit assignment keeps the lesson on the read-or-default path without hiding it behind getOrElse or updateWith.
  • The auxiliary order buffer 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 `ArrayBuffer[String]`) to keep the printout deterministic; the `HashMap` iteration order is not a contract.