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.rb 
words = ["fig", "apple", "fig", "pear", "apple", "fig"]
counts = {}
order = []
i = 0
while i < words.length
	word = words[i]
	if !counts.key?(word)
		order << word
		counts[word] = 1
	else
		prev = counts[word]
		counts[word] = prev + 1
	end
	i = i + 1
end
print "{"
j = 0
while j < order.length
	if j > 0
		print ", "
	end
	key = order[j]
	print "#{key}: #{counts[key]}"
	j = j + 1
end
puts "}"

Complexity

  • Time: O(n) average with Hash.
  • Space: O(k) where k is the number of distinct keys.

Implementation notes

  • Ruby: counts = {} is the idiomatic mutable hash; the counts.key?(word) predicate plus an explicit assignment keeps the lesson on the read-or-default path without hiding it behind Hash.new(0) (which would auto-default the count and collapse the branch) or counts.tally (which would hide the entire loop).
  • The auxiliary order array preserves first-seen order so the final printout is deterministic across languages — even though Ruby's Hash happens to preserve insertion order, the language-neutral spec does not depend on it.
  • 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 plain `Array` of strings) to keep the printout deterministic; relying on `Hash` iteration order across languages is not a contract you should encode in a lesson spec.