The tables module implements variants of an efficient hash table (also often named dictionary in other programming languages) that is a mapping from keys to values.

There are several different types of hash tables available:

Table is the usual hash table,
OrderedTable is like Table but remembers insertion order,
CountTable is a mapping from a key to its number of occurrences

For consistency with every other data type in Nim these have value semantics, this means that \= performs a copy of the hash table.

For ref semantics use their Ref variants: TableRef, OrderedTableRef, and CountTableRef.

To give an example, when a is a Table, then var b = a gives b as a new independent table. b is initialised with the contents of a. Changing b does not affect a and vice versa:

Example:

import std/tables
var
  a = {1: "one", 2: "two"}.toTable  # creates a Table
  b = a
assert a == b
b[3] = "three"
assert 3 notin a
assert 3 in b
assert a != b

On the other hand, when a is a TableRef instead, then changes to b also affect a. Both a and b ref the same data structure:

Example:

import std/tables
var
  a = {1: "one", 2: "two"}.newTable  # creates a TableRef
  b = a
assert a == b
b[3] = "three"
assert 3 in a
assert 3 in b
assert a == b

Basic usage

Table

Example:

import std/tables
from std/sequtils import zip
let
  names = ["John", "Paul", "George", "Ringo"]
  years = [1940, 1942, 1943, 1940]
var beatles = initTable[string, int]()
for pairs in zip(names, years):
  let (name, birthYear) = pairs
  beatles[name] = birthYear
assert beatles == {"George": 1943, "Ringo": 1940, "Paul": 1942, "John": 1940}.toTable
var beatlesByYear = initTable[int, seq[string]]()
for pairs in zip(years, names):
  let (birthYear, name) = pairs
  if not beatlesByYear.hasKey(birthYear):
    # if a key doesn't exist, we create one with an empty sequence
    # before we can add elements to it
    beatlesByYear[birthYear] = @[]
  beatlesByYear[birthYear].add(name)
assert beatlesByYear == {1940: @["John", "Ringo"], 1942: @["Paul"], 1943: @["George"]}.toTable

OrderedTable

OrderedTable is used when it is important to preserve the insertion order of keys.

Example:

import std/tables
let
  a = [('z', 1), ('y', 2), ('x', 3)]
  ot = a.toOrderedTable  # ordered tables
assert $ot == """{'z': 1, 'y': 2, 'x': 3}"""

CountTable is useful for counting number of items of some container (e.g. string, sequence or array), as it is a mapping where the items are the keys, and their number of occurrences are the values. For that purpose toCountTable proc comes handy:

Example:

import std/tables
let myString = "abracadabra"
let letterFrequencies = toCountTable(myString)
assert $letterFrequencies == "{'a': 5, 'd': 1, 'b': 2, 'r': 2, 'c': 1}"

The same could have been achieved by manually iterating over a container and increasing each key’s value with inc proc:

Example:

import std/tables
let myString = "abracadabra"
var letterFrequencies = initCountTable[char]()
for c in myString:
  letterFrequencies.inc(c)
assert $letterFrequencies == "{'d': 1, 'r': 2, 'c': 1, 'a': 5, 'b': 2}"

Hashing

If you are using simple standard types like int or string for the keys of the table you won’t have any problems, but as soon as you try to use a more complex object as a key you will be greeted by a strange compiler error:

Error: type mismatch: got (Person)
but expected one of:
hashes.hash(x: openArray[A]): Hash
hashes.hash(x: int): Hash
hashes.hash(x: float): Hash
…

What is happening here is that the types used for table keys require to have a hash() proc which will convert them to a Hash value, and the compiler is listing all the hash functions it knows. Additionally there has to be a \== operator that provides the same semantics as its corresponding hash proc.

After you add hash and \== for your custom type everything will work. Currently, however, hash for objects is not defined, whereas system.== for objects does exist and performs a “deep” comparison (every field is compared) which is usually what you want. So in the following example implementing only hash suffices:

Example:

import std/tables
import std/hashes
type
  Person = object
    firstName, lastName: string
proc hash(x: Person): Hash =
  ## Piggyback on the already available string hash proc.
  ##
  ## Without this proc nothing works!
  result = x.firstName.hash !& x.lastName.hash
  result = !$result
var
  salaries = initTable[Person, int]()
  p1, p2: Person
p1.firstName = "Jon"
p1.lastName = "Ross"
salaries[p1] = 30_000
p2.firstName = "소진"
p2.lastName = "박"
salaries[p2] = 45_000

Imports

since, hashes, math, algorithm, outparams

Types

CountTable[A] = object

Hash table that counts the number of each key.

For creating an empty CountTable, use initCountTable proc.