Associative Arrays

Part II · Module 6 · Chapter 6.1 · Associative Arrays

1. Why This Matters

Chapter 5.1 gave you a variable that survives between records. That is enough for a total, a count and a worst case — one of each.

It is not enough for per-category anything. Counting failures by error signature means one counter per signature, and you do not know the signatures until you have read the file. With single variables you would have to name them in advance, which means knowing the answer before you start.

An array solves it, and awk's arrays have two properties worth stating immediately:

• The index is a string, not a number. n["TIMEOUT"] is as natural as n[3].
• An entry springs into existence when you use it. No declaration, no sizing, no allocation.

That second property is what makes the counting idiom in Chapter 6.2 a single character of code. It is also the source of the bug in section 6, which is the most important thing in this chapter and the reason it is rated critical.

2. One Data Structure

awk has arrays. It does not have lists, hashes, dictionaries, sets, structs, or objects — and it does not need separate names for them, because the one array type does all those jobs.

awk 'BEGIN { a["alu"] = 95; a["fifo"] = 72; print a["alu"], a["fifo"] }'

95 72

Two entries, created by being assigned to. Nothing was declared and no size was given.

Used with string keys it is a dictionary. Used with values you ignore it is a set. Used with consecutive integer keys it is a list — which is what col[i] in Chapter 5.5 was doing, and that chapter deliberately did not say the word "array" because the index happened to be a number.

3. Keys Are Strings

Every subscript is converted to a string before use, which has a consequence people trip over:

awk 'BEGIN { a[1] = "one"; a["1"] = "ONE"; n = 0; for (k in a) n++; print "entries:", n, "and a[1] is", a[1] }'

entries: 1 and a[1] is ONE

One entry, not two. a[1] and a["1"] are the same element — the number 1 became the string "1", and the second assignment overwrote the first.

This is usually convenient and occasionally a trap. The trap arrives with values that are numerically equal and textually different:

awk 'BEGIN { a[1] = "x"; a["01"] = "y"; a[1.0] = "z"; for (k in a) print "key [" k "]  value [" a[k] "]" }'

key [01]  value [y]
key [1]  value [z]

Two entries. 1 and 1.0 collapsed to the same key "1" — so a[1.0] = "z" overwrote a[1] = "x" — while "01" stayed separate, because as text it is a different string.

So if your keys come from a report column, a value written 01 in one row and 1 in another lands in two different buckets. That is the Chapter 5.3 conversion rule arriving as a grouping bug, and it is why a key extracted from input is worth normalising deliberately — Chapter 6.3 returns to this when grouping real reports.

Conversion of a numeric subscript uses CONVFMT (Chapter 5.2, section 12), so a key derived from a computed float can round. Keys that matter should be strings you control, not arithmetic results.

4. Creating and Reading

Assignment creates:

TIMEOUT uart
ASSERT alu
TIMEOUT fifo
ASSERT alu
TIMEOUT spi
XCHECK ddr

awk '{ sig[$1] = $2 } END { for (k in sig) print k, "last seen on", sig[k] }' errors.txt

XCHECK last seen on ddr
TIMEOUT last seen on spi
ASSERT last seen on alu

Three entries from six records, because each repeated signature overwrote its own entry — the Chapter 5.1 "remember a record" pattern, now one slot per key instead of one slot total.

An element you never assigned reads as the empty string and zero, exactly like an unset scalar (Chapter 5.1, section 3):

awk 'BEGIN { a["alu"] = 95; print "[" a["nope"] "]", a["nope"] + 0 }'

[] 0

That is convenient — it is why n[k]++ works on a key's first appearance without initialisation. And it is the setup for the next section.

5. Reading an Element Creates It

Here is the fact that earns this chapter its critical rating.

awk 'BEGIN { a["x"] = 1
  if ("y" in a) print "y is present before"; else print "y is absent before"
  junk = a["y"]
  if ("y" in a) print "y is PRESENT after a mere read"; else print "y is still absent" }'

y is absent before
y is PRESENT after a mere read

junk = a["y"] created a["y"]. Nothing was assigned to the array. The element was only read, and it now exists — holding the empty string.

It is worse than that, because a test is also a read:

awk 'BEGIN { a["x"] = 1
  if ("z" in a) print "z in a"; else print "z NOT in a"
  if (a["z"] != "") print "a[z] is non-empty"; else print "a[z] is empty"
  if ("z" in a) print "z is NOW in a"; else print "z is still not in a" }'

z NOT in a
a[z] is empty
z is NOW in a

The middle line is a membership test written the obvious way — does this array have anything under key z? — and asking the question made the answer yes for every future asker.

6. The in Operator

key in array yields 1 if the entry exists and 0 if it does not, and creates nothing:

awk 'BEGIN { a["alu"] = 95; print ("alu" in a), ("fifo" in a) }'

1 0

As a condition it reads naturally:

awk 'FNR==NR { want[$1]; next } $1 in want' want.txt all.txt

alu PASS
fifo FAIL
uart PASS

Two things in that command are worth naming. want[$1] with no assignment is the idiomatic way to add a key to a set — it creates the entry (section 5's rule, used deliberately this time) with an empty value, because only the key matters. And $1 in want as a bare pattern with no action prints matching records, which is Chapter 4.1's rule.

The negated form needs parentheses:

awk 'FNR==NR { want[$1]; next } !($1 in want)' want.txt all.txt

spi PASS
ddr FAIL

The two tests not in the list. Note !($1 in want) and not !$1 in want — the latter parses as (!$1) in want, which asks whether the string "0" or "1" is a key, and is almost never what you meant:

awk 'FNR==NR { want[$1]; next } { print $1, ($1 in want), (!($1 in want)), (!$1 in want) }' want.txt all.txt

alu 1 0 0
fifo 1 0 0
uart 1 0 0
spi 0 1 0
ddr 0 1 0

The last column is 0 for every record — (!$1) is 0 for a non-empty field, and 0 in want is false because no key is "0". A test that is always false, with no error.

7. Iterating with for (key in array)

A second form of for walks the keys:

awk '{ n[$1]++ } END { for (sig in n) print sig, n[sig] }' errors.txt

XCHECK 1
TIMEOUT 3
ASSERT 2

sig takes each key in turn. The value is n[sig] — note that the loop gives you keys, not values, and not pairs.

This is the only way to enumerate an array. There is no "first key", no index-by-position, and no way to ask how many entries there are without counting them (section 12).

A deliberate subtlety: inside this loop, modifying the array you are iterating is unsafe. Adding keys during iteration has undefined results, and section 5's rule means a careless read inside the loop body is an addition. Build a list, then walk it.

8. Deleting

delete array[key] removes one entry:

awk 'BEGIN { a["x"]=1; a["y"]=2; delete a["x"]; for (k in a) print "remains:", k }'

remains: y

delete array removes every entry:

awk 'BEGIN { a["x"]=1; a["y"]=2; delete a; n=0; for (k in a) n++; print "entries after delete a:", n }'

entries after delete a: 0

An older, widely-portable idiom does the same by splitting an empty string into the array:

awk 'BEGIN { a["x"]=1; a["y"]=2; split("", a); n=0; for (k in a) n++; print "entries after split(\"\", a):", n }'

entries after split("", a): 0

delete array is in POSIX and is clearer; split("", a) predates it and still appears in older scripts, which is the only reason to recognise it.

Deletion is also the correct repair for section 5's phantoms when you cannot restructure the test — though fixing the test is better than cleaning up after it.

9. Counting Occurrences

The idiom this module is built around, stated here and developed in Chapter 6.2:

awk '{ n[$1]++ } END { for (sig in n) print n[sig], sig }' errors.txt

1 XCHECK
3 TIMEOUT
2 ASSERT

n[$1]++ is the whole thing. On a signature's first appearance the element does not exist, reads as 0, and becomes 1. On every later appearance it increments. No initialisation, no list of expected signatures, no second pass.

Three signatures across six records, and the program never knew the signatures existed.

10. Iteration Order Is Undefined

The output above is not sorted, and it is not insertion order either. Eight keys inserted in sequence:

awk 'BEGIN { for (i = 1; i <= 8; i++) a["key" i] = i; for (k in a) { printf "%s%s", sep, k; sep = " " }; print "" }'

key3 key4 key5 key6 key7 key8 key1 key2

Inserted key1 through key8; iterated starting at key3, running to key8, then wrapping to key1 and key2.

That is not a rule to learn — it is the internal hash order of this particular awk with these particular keys, and it is genuinely unspecified by POSIX. A different awk, a different number of keys, or different key names can all produce a different order. Do not infer "it rotates" or "it starts a third of the way in" from this one output; infer only that you cannot predict it.

11. Multidimensional Arrays

awk simulates a multidimensional array by joining the subscripts into one string with a separator held in SUBSEP:

awk 'BEGIN { a["x","y"] = 7; print a["x","y"], (("x","y") in a) }'

7 1

a["x","y"] is really a["x" SUBSEP "y"] — a single key built from two parts. SUBSEP defaults to character code 1, a control character chosen because real data almost never contains it:

awk 'BEGIN { printf "SUBSEP is character code %d\n", index(SUBSEP SUBSEP, SUBSEP) }'

SUBSEP is character code 1

Iterating gives you the joined key, which you split back apart:

u_alu comb 1820
u_regfile seq 2410
u_alu comb 640
u_io pad 300
u_regfile seq 1100

awk '{ t[$1,$2] += $3 } END { for (k in t) { split(k, p, SUBSEP); printf "%-12s %-6s %5d\n", p[1], p[2], t[k] } }' area.rpt | sort

u_alu        comb    2460
u_io         pad      300
u_regfile    seq     3510

Grouped by instance and kind in one pass. split() is Module 8's function, used here because recovering the parts is unavoidable.

The honest caveat: this is one-dimensional storage with a naming convention on top. ("x","y") in a works, but there is no way to ask "every key whose first part is x" without iterating everything and splitting. When that is the question you need, a different key layout — or a different tool — is usually better than fighting this one.

12. Counting Entries, and Portability

awk has no portable way to ask an array's size. On this awk, length() answers:

awk 'BEGIN { a[1]=1; a[2]=2; a[3]=3; print length(a) }'

3

That works here and length() on an array is a gawk extension, not POSIX. Chapter 8.6 covers the portability question properly; the rule for now is that a script which must run on an unknown awk should count instead:

awk '{ n[$1]++ } END { c = 0; for (k in n) c++; printf "%d distinct signatures over %d records\n", c, NR }' errors.txt

3 distinct signatures over 6 records

Three lines instead of one, and it runs anywhere. It also prints the denominator, which Chapter 5.3 established as the habit that makes a count auditable — 3 distinct alone does not tell a reader whether that was out of six records or six hundred.

13. Common Mistakes

Testing membership with array[key] != "". Creates the element. Use key in array — section 5.

Writing !$1 in want. Parses as (!$1) in want and is always false. Parenthesise: !($1 in want).

Expecting a[1] and a["1"] to differ. Subscripts are strings; they are the same element. And 01 is a different key from 1.

Assuming for (k in a) has an order. It has none. Pipe to sort or keep an index array.

Adding keys while iterating the same array. Undefined — and a careless read inside the loop is an addition.

Using length(a) in a portable script. A gawk extension. Count with a loop.

Expecting a way to query part of a multidimensional key. There is none; you iterate and split.

Forgetting that an unset element is 0 and "". It is why n[k]++ needs no initialisation, and why n[k] == 0 is true both for a missing key and for a real count of zero.

14. Exercises

Exercise 1 — Predict the output

awk 'BEGIN { a["x"] = 1; a["y"] = 2; delete a["z"]; n = 0; for (k in a) n++; print n }'

2

Deleting a key that does not exist is not an error and does not create one — delete is the one operation that touches a missing key harmlessly.

Exercise 2 — Build a set

Print the distinct test names in the error log, one per line, in sorted order.

TIMEOUT uart
ASSERT alu
TIMEOUT fifo
ASSERT alu
TIMEOUT spi
XCHECK ddr

awk '{ seen[$2] } END { for (t in seen) print t | "sort" }' errors.txt

alu
ddr
fifo
spi
uart

seen[$2] with no assignment adds the key — the set idiom from section 6. Five distinct tests from six records, because alu appears twice.

Exercise 3 — Membership, both ways

Predict both outputs before running, paying attention to the final key count.

awk 'BEGIN { a["x"] = 1; if (a["q"] == "") q_was_empty = 1; n = 0; for (k in a) n++; print "q_was_empty =", q_was_empty, "and a has", n, "keys" }'

q_was_empty = 1 and a has 2 keys

awk 'BEGIN { a["x"] = 1; if (!("q" in a)) q_absent = 1; n = 0; for (k in a) n++; print "q_absent =", q_absent, "and a has", n, "keys" }'

q_absent = 1 and a has 1 keys

Both correctly determined that q was missing. Only the second left the array alone.

Exercise 4 — Debug a wrong distinct count

A script is supposed to report how many of a watchlist's tests appeared in a log. It reports 5 against a watchlist of 3.

alu
fifo
uart

alu PASS
fifo FAIL
uart PASS
spi PASS
ddr FAIL

awk 'FNR==NR { want[$1]=1; next } { if (want[$1] != "") hits++ } END { c=0; for (k in want) c++; printf "%d hits against a watchlist of %d\n", hits+0, c }' want.txt all.txt

3 hits against a watchlist of 5

The hit count is right and the watchlist size is wrong. want[$1] != "" was evaluated for spi and ddr, creating both as empty entries, so the watchlist grew by exactly the number of unwanted records.

awk 'FNR==NR { want[$1]=1; next } { if ($1 in want) hits++ } END { c=0; for (k in want) c++; printf "%d hits against a watchlist of %d\n", hits+0, c }' want.txt all.txt

3 hits against a watchlist of 3

Note the shape of the original bug: the number a reader would check — the hit count — was correct, and the one that was wrong looked like a fact about the input file rather than a result.

Exercise 5 — Two-level grouping

Total the cell counts per instance and logic kind, in one pass.

u_alu comb 1820
u_regfile seq 2410
u_alu comb 640
u_io pad 300
u_regfile seq 1100

awk '{ t[$1,$2] += $3; c[$1,$2]++ } END { for (k in t) { split(k, p, SUBSEP); printf "%-12s %-6s %5d over %d rows\n", p[1], p[2], t[k], c[k] } }' area.rpt | sort

u_alu        comb    2460 over 2 rows
u_io         pad      300 over 1 rows
u_regfile    seq     3510 over 2 rows

The row count beside each total is Chapter 5.3's denominator habit: a group built from one row and one built from fifty should not look identical in a report.

The engineering caveat Chapter 1.2 established still applies — 2460 is the sum of two rows naming u_alu, which is the instance's total only if the report lists each instance's cells once and does not also list a parent containing them.

Exercise 6 — Engineering application

Produce a triage table: each error signature, its count, its share of all errors, and the number of distinct tests it affected — ordered most frequent first.

awk '{ n[$1]++; if (!(($1,$2) in pair)) { pair[$1,$2]; tests[$1]++ } } END { for (s in n) printf "%-8s %3d  %5.1f%%  %d test(s)\n", s, n[s], 100*n[s]/NR, tests[s] | "sort -k2 -rn" }' errors.txt

TIMEOUT    3   50.0%  3 test(s)
ASSERT     2   33.3%  1 test(s)
XCHECK     1   16.7%  1 test(s)

The last column is the one that changes a decision. ASSERT fired twice and both times on alu, so it is probably one bug. TIMEOUT fired three times across three different tests, which looks like something environmental rather than a single RTL defect.

That distinction is only available because the script counted distinct (signature, test) pairs rather than records — using in to test the pair, which section 5's rule makes mandatory here: pair[$1,$2] != "" would create every pair it checked and make tests[] count every record.

And the caveat: these are counts of error records, not of bugs. One root cause can emit many records, and Chapter 9.3 is where this gets treated properly.

Exercise 7 — Challenge: reproducible output order

for (k in a) has no defined order, so two runs may print rows in different sequences. Produce the triage table in a fixed order without piping to an external command.

awk '!($1 in n) { order[++seq] = $1 } { n[$1]++ } END { for (i = 1; i <= seq; i++) printf "%-8s %d\n", order[i], n[order[i]] }' errors.txt

TIMEOUT  3
ASSERT   2
XCHECK   1

First-appearance order, which is reproducible for a given input on any awk.

The mechanism: !($1 in n) is true exactly once per signature — on its first record, before n[$1]++ has created the entry — so order[] gets each key once, numbered by ++seq. Then a counting for loop walks order[] by position, which does have a defined order, and uses each value as the key into n[].

Rule ordering matters and is Chapter 2.3's lesson: the !($1 in n) rule must come before the counting rule. Reversed, n[$1]++ creates the entry first and the membership test is never true:

awk '{ n[$1]++ } !($1 in n) { order[++seq] = $1 } END { printf "order[] captured %d keys\n", seq + 0 }' errors.txt

order[] captured 0 keys

Zero. The index array is empty and a loop over it prints nothing at all — a report with no rows and no error.

15. Summary

• awk has one data structure: an array indexed by strings. It serves as dictionary, set and list.
• Entries are created by use. No declaration, no sizing — which is what makes n[k]++ work on first sight.
• Subscripts are strings. a[1] and a["1"] are one element; "01" and "1" are two.
• Reading an element creates it — including inside a test. array[key] != "" grows the array it is asking about, without changing the answer you are looking at.
• Use key in array for membership, and parenthesise the negation: !($1 in want).
• array[key] with no assignment adds a key to a set — the same rule, used deliberately.
• for (key in array) enumerates keys, not values, and is the only way to walk an array.
• Iteration order is unspecified. Pipe to sort, or keep an index array and walk it by position.
• delete array[key] removes one entry, delete array removes all. Deleting a missing key is harmless.
• a[i,j] joins subscripts with SUBSEP into a single key, recovered with split().
• length(array) is a gawk extension. Count with a loop in a portable script, and print the denominator.

You can now hold one value per distinct key, which is the foundation of every summary in the rest of this track.

Chapter 6.2 — Frequency Counting takes the one idiom this chapter introduced and makes it the subject: counting failures per test, records per signature and cells per type, including the difference between counting records and counting distinct things, and why the most frequent key is rarely the most important one.