Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 36 ยท Collections and Strings

Tables and Sets: Hash Maps in Nim

Use Nim's std/tables and std/sets: create tables, look up keys safely, count items with CountTable, keep insertion order, and do union and intersection with HashSet.

A table maps keys to values: names to phone numbers, words to counts, IDs to records. In Nim the hash-table type lives in std/tables. Its companion std/sets provides a HashSet, a collection of unique values with fast membership tests. Both are built on hashing, which gives average constant-time lookups.

Nim code is read-only on this page (no compiler on this site). The C stand-ins implement the core idea so you can run it.

Creating a table

NIM
import std/tables

var ages = {"ann": 30, "bo": 25, "cy": 41}.toTable   # from a list of pairs
var empty = initTable[string, int]()                 # empty, typed

The braces-with-pairs syntax builds an array of tuples, and toTable converts it. The type is Table[string, int]. Keys must be hashable and comparable (strings, numbers, characters, tuples of those, and objects with a hash procedure).

Reading and writing

NIM
ages["di"] = 19                    # insert or overwrite
echo ages["ann"]                   # 30
echo ages.len                      # 4

echo ages.getOrDefault("zed")      # 0      (default for int, no error)
echo ages.getOrDefault("zed", -1)  # -1     (your own default)
echo "bo" in ages                  # true   (same as ages.hasKey("bo"))
ages.del("bo")                     # remove a key (no error if absent)

Looking up a missing key with [] raises a KeyError, so use getOrDefault, hasKey or in when a key may be missing:

NIM
if "ann" in ages:
  echo "found ", ages["ann"]

An important idiom updates a value that may not exist yet:

NIM
var counts = initTable[string, int]()
for word in ["a", "b", "a", "c", "a"]:
  counts[word] = counts.getOrDefault(word) + 1

or, shorter, inc counts.mgetOrPut(word, 0), which inserts 0 if missing and returns a mutable reference.

Iterating

NIM
for name, age in ages:
  echo name, " is ", age

for name in ages.keys:
  echo name

for age in ages.values:
  echo age

The order is not specified for a plain Table: it depends on the hash function and table size, and may change between runs or Nim versions. Never rely on it, and sort the keys if you need a stable output:

NIM
import std/algorithm
for name in toSeq(ages.keys).sorted():
  echo name

(toSeq comes from std/sequtils.)

Table variants

Type Keeps insertion order? Values Use when
Table[K, V] no any the default choice
OrderedTable[K, V] yes any output order matters
CountTable[K] no int counts counting occurrences
TableRef[K, V] no any you need reference semantics

CountTable is built for frequency counting:

NIM
let freq = toCountTable("mississippi")
echo freq['s']                 # 4
echo freq.largest.val          # 4  (the highest count; 'i' and 's' tie)

Plain tables are value types, so var b = a copies the whole table; use TableRef (created with newTable) when several variables should share one table.

HashSet

NIM
import std/sets

var seen = initHashSet[int]()
seen.incl 3
seen.incl 5
seen.incl 3                    # duplicates are ignored
echo seen.len                  # 2
echo 5 in seen                 # true
seen.excl 5

let a = [1, 2, 3, 4].toHashSet
let b = [3, 4, 5].toHashSet
echo a + b                     # union: {1, 2, 3, 4, 5}  (order unspecified)
echo a * b                     # intersection: {3, 4}
echo a - b                     # difference: {1, 2}

A HashSet[T] stores any hashable type. For small ordinal types (characters, enums, small ranges) the built-in set[T] from the enums lesson is a bitmask and even faster, but limited to a few thousand values.

flowchart LR
  K["key: \"ann\""] --> H["hash function"]
  H --> I["index in an array<br/>of buckets"]
  I --> V["stored value: 30"]

Caption: hashing turns a key into an array position, which is why lookups are fast.

Stand-in: a tiny hash table

This C stand-in counts characters with a hash table using open addressing (find the next free slot on collision). It shows why average lookups need only a few steps. Real tables also resize when they fill up.

C Stand-in: counting characters with a hash table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The counts m:1 i:4 s:4 p:2 match what toCountTable("mississippi") reports in Nim, and z returns the default 0.

Stand-in: set operations with bitmasks

For small domains a set is just a bitmask, and union, intersection and difference become single bit operations.

C Stand-in: union, intersection, difference

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What happens with ages["missing"] when the key is absent?

    Use getOrDefault, hasKey or in when a key may not exist.
  2. 2. Which type keeps insertion order?

    OrderedTable iterates in insertion order; Table does not guarantee any order.
  3. 3. How do you count the occurrences of each character in a string?

    CountTable is built for frequency counting.
  4. 4. What does the + operator do on two HashSets?

    • is union, * is intersection, - is difference.

Summary

  • Table[K, V] maps keys to values with average O(1) lookup; use getOrDefault, hasKey or in for safe access.
  • Plain tables do not guarantee order; OrderedTable does; CountTable counts occurrences.
  • Tables are value types; TableRef shares.
  • HashSet[T] stores unique values with incl, excl, in and the operators +, *, -.

Next: Tuples and Option