Hash Table - Bash DSA

Tally how many times each word appears in a small array using an associative array as a hash table. Track first-seen order so the printout matches the lesson spec rather than the hash's internal layout.

Algorithm

Canonical input words=(fig apple fig pear apple fig) yields three new-key frames and three hit frames.

Basic Implementation

basic.sh

#!/usr/bin/env bash
set -euo pipefail
words=(fig apple fig pear apple fig)
declare -A counts
order=()
i=0
while [ "$i" -lt "${#words[@]}" ]; do
	word=${words[i]}
	if [ -z "${counts[$word]+_}" ]; then
		order+=("$word")
		counts[$word]=1
	else
		prev=${counts[$word]}
		counts[$word]=$((prev + 1))
	fi
	i=$((i + 1))
done
printf '{'
j=0
while [ "$j" -lt "${#order[@]}" ]; do
	if [ "$j" -gt 0 ]; then
		printf ', '
	fi
	key=${order[j]}
	printf '%s: %d' "$key" "${counts[$key]}"
	j=$((j + 1))
done
printf '}\n'

Complexity

Time: O(n)
Space: O(k) for the hash, where k is the number of unique keys

Implementation notes

Bash: declare -A counts allocates a true associative array; the ${counts[$word]+_} parameter-expansion check distinguishes missing keys from keys with the empty-string value, which is the Bash idiom for has_key.
A parallel order=() indexed array preserves insertion order without depending on Bash's associative-array iteration order, which is hash-bucket-dependent and not stable across keys.
The replay surfaces each step's word, the before count, and the full insertion-ordered hash after the step so the viewer sees both the new and hit paths.

get-or-default For each word: if not present in the hash, push it onto an `order` array and set its count to `1`; otherwise increment the existing count.

insertion-ordered output A parallel `order` array records first-seen position so the printout prints `{fig: 3, apple: 2, pear: 1}` deterministically, independent of the associative array's iteration order.