Hash Tables

Frequency Count

Walk a sequence and count occurrences of each value. Classic "get current count, add one, write back" loop. The canonical lesson for the get-or-default pattern.

Algorithm

Canonical input ["fig", "apple", "fig", "pear", "apple", "fig"] produces the final (key, count) table {fig: 3, apple: 2, pear: 1}.

Basic Implementation

basic.f90 
program freq_count
    implicit none
    character(len=5) :: words(6) = ['fig  ', 'apple', 'fig  ', 'pear ', 'apple', 'fig  ']
    character(len=5) :: keys(6)
    integer :: counts(6)
    integer :: nkeys, i, j
    logical :: found

    nkeys = 0
    do i = 1, 6
        found = .false.
        do j = 1, nkeys
            if (keys(j) == words(i)) then
                counts(j) = counts(j) + 1
                found = .true.
                exit
            end if
        end do
        if (.not. found) then
            nkeys = nkeys + 1
            keys(nkeys) = words(i)
            counts(nkeys) = 1
        end if
    end do
    do i = 1, nkeys
        print '(A,A,I0)', trim(keys(i)), ': ', counts(i)
    end do
end program freq_count

Complexity

  • Time: O(n * k) for k distinct keys (linear scan per word; fine for the lesson-size input). A true hash table would be O(n) average.
  • Space: O(k)

Implementation notes

  • Fortran: standard Fortran has no built-in hash map, so the lesson uses parallel character(len=5) :: keys(6) / integer :: counts(6) arrays and a linear scan. This keeps the get-or-default pattern explicit and visible in the replay.
  • The replay shows the current word, its count before the update, and the full table state after the write, matching the lesson spec. The first-seen ordering (fig, apple, pear) is preserved by appending new keys at nkeys + 1.
get or default On a miss, append a new `(key, 1)` pair; on a hit, increment the existing count by one.