таблицы

Модуль tables реализует варианты эффективной хеш-таблицы (также часто называемой словарем в других языках программирования), которая представляет собой отображение ключей на значения.

Доступно несколько разных типов хеш-таблиц:

Таблица — обычная хеш-таблица,
Отсортированная таблица — подобна Table, но запоминает порядок вставки,
Таблица подсчёта — отображение ключа на его количество вхождений

Для согласованности со всеми другими типами данных в Nim у них есть семантика значения, это означает, что = выполняет копирование хеш-таблицы.

Для семантики ссылок используйте их варианты Ref: TableRef, OrderedTableRef и CountTableRef.

Например, когда a является Table, тогда var b = a создаёт новую независимую таблицу b. b инициализируется содержимым a. Изменение b не влияет на a и наоборот:

import tables

var
  a = {1: "one", 2: "two"}.toTable  # creates a Table
  b = a

echo a, b  # output: {1: one, 2: two}{1: one, 2: two}

b[3] = "three"
echo a, b  # output: {1: one, 2: two}{1: one, 2: two, 3: three}
echo a == b  # output: false

С другой стороны, когда a является TableRef, тогда изменения в b также влияют на a. Обе a и b ссылаются на одну и ту же структуру данных:

import tables

var
  a = {1: "one", 2: "two"}.newTable  # creates a TableRef
  b = a

echo a, b  # output: {1: one, 2: two}{1: one, 2: two}

b[3] = "three"
echo a, b  # output: {1: one, 2: two, 3: three}{1: one, 2: two, 3: three}
echo a == b  # output: true

Основное использование

Таблица

import tables
from 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

echo beatles
# {"George": 1943, "Ringo": 1940, "Paul": 1942, "John": 1940}


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)

echo beatlesByYear
# {1940: @["John", "Ringo"], 1942: @["Paul"], 1943: @["George"]}

Отсортированная таблица

Отсортированная таблица используется, когда важно сохранить порядок вставки ключей.

import tables

let
  a = [('z', 1), ('y', 2), ('x', 3)]
  t = a.toTable          # regular table
  ot = a.toOrderedTable  # ordered tables

echo t   # {'x': 3, 'y': 2, 'z': 1}
echo ot  # {'z': 1, 'y': 2, 'x': 3}

Таблица подсчёта

Таблица подсчёта полезна для подсчёта количества элементов некоторого контейнера (например, строки, последовательности или массива), поскольку она представляет собой отображение, где элементы являются ключами, а их количество вхождений — значениями. Для этой цели удобна процедура toCountTable:

import tables

let myString = "abracadabra"
let letterFrequencies = toCountTable(myString)
echo letterFrequencies
# output: {'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2}

Того же можно было достичь, вручную перебирая контейнер и увеличивая значение каждого ключа с помощью процедуры inc:

import tables

let myString = "abracadabra"
var letterFrequencies = initCountTable[char]()
for c in myString:
  letterFrequencies.inc(c)
echo letterFrequencies
# output: {'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2}

Хеширование

Если вы используете простые стандартные типы, такие как int или string для ключей таблицы, у вас не будет проблем, но как только вы попытаетесь использовать более сложный объект в качестве ключа, вас ждёт странная ошибка компилятора:

Ошибка: несовпадение типов: получен (Person), ожидался один из: hashes.hash(x: openArray[A]): Hash hashes.hash(x: int): Hash hashes.hash(x: float): Hash …

Здесь дело в том, что типы, используемые для ключей таблицы, должны иметь процедуру hash(), которая преобразует их в значение типа Hash, и компилятор перечисляет все известные ему хеш-функции. Кроме того, должен быть оператор ==, который обеспечивает ту же семантику, что и соответствующая ему процедура hash.

После добавления hash и == для вашего пользовательского типа всё будет работать. Однако в настоящее время hash для объектов не определён, в то время как system.== для объектов существует и выполняет "глубокое" сравнение (сравниваются все поля), что обычно и требуется. Таким образом, в следующем примере достаточно реализовать только hash.

import tables, 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

См. также

модуль json для структуры данных, похожей на таблицу, которая допускает разнородные члены
модуль sharedtables для поддержки совместного использования хеш-таблиц
модуль strtabs для эффективных хеш-таблиц, отображающих строки на строки
модуль hashes для вспомогательных функций хеширования

Импорты

since, hashes, math, algorithm

Типы

Table[A; B] = object data: KeyValuePairSeq[A, B] counter: int

Обобщённая хеш-таблица, состоящая из пары "ключ-значение".

data и counter — внутренние детали реализации, к которым нельзя получить доступ.

Для создания пустой Таблицы используйте процедуру initTable.

таблицы

Основное использование

Таблица

Отсортированная таблица

Таблица подсчёта

Хеширование

См. также

Импорты

Типы

Константы

Процедуры

Итераторы

Шаблоны