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.swift 
let words = ["fig", "apple", "fig", "pear", "apple", "fig"]
var counts: [String: Int] = [:]
var order: [String] = []
for i in words.indices {
	let word = words[i]
	if counts[word] == nil {
		order.append(word)
		counts[word] = 1
	} else {
		let prev = counts[word]!
		counts[word] = prev + 1
	}
}
print("{", terminator: "")
for i in order.indices {
	if i > 0 {
		print(", ", terminator: "")
	}
	let key = order[i]
	print("\(key): \(counts[key]!)", terminator: "")
}
print("}")

Complexity

  • Time: O(n) average with [String: Int].
  • Space: O(k) where k is the number of distinct keys.

Implementation notes

  • Swift: var counts: [String: Int] = [:] is the idiomatic map; the counts[word] == nil predicate plus an explicit assignment keeps the lesson on the read-or-default path without hiding it behind counts[word, default: 0] += 1.
  • The auxiliary order list preserves first-seen order so the final printout is deterministic — Dictionary 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 `[String]`) to keep the printout deterministic; the `[String: Int]` iteration order is not a contract.