# Introduction to TON TL-B (Part 3, Dictionary)

[TL-B](https://docs.ton.org/v3/documentation/data-formats/tlb/tl-b-language) (short for Type Language - Binary) is the [IDL](https://en.wikipedia.org/wiki/Interface_description_language) of [TON](https://ton.org/). If you are learning or using TON Blockchain, you will inevitably come into contact with the TL-B language. TL-B is very suitable for describing the structure and format of types (such as blocks or transactions). However, interestingly, TL-B does not serialize an instance of a type directly into a byte array, but serializes it into so-called Cells.


The purpose of this series of articles is to help readers understand the TL-B language. In [the first article](https://hackmd.io/@sp1derca7/ton-tlb-1) of the series, I introduced the basic syntax of TL-B and, with practical examples, most of its built-in types and some advanced types. In [the second article](https://hackmd.io/@sp1derca7/ton-tlb-2), I discussed another fundamental concept of TL-B: the Cell, along with its own serialization format: BoC (short for Bag of Cells).

This article is the third in the series, in which I will specifically introduce an advanced TL-B type: [Dictionary](https://docs.ton.org/v3/documentation/data-formats/tlb/tl-b-types#hashmap). I will explain what a Dictionary is, its presence in [TVM](https://docs.ton.org/v3/documentation/tvm/tvm-overview) and TON contract programming languages like [FunC](https://docs.ton.org/v3/documentation/smart-contracts/func/overview) and [Tact](https://tact-lang.org/), as well as in TON [SDKs](https://docs.ton.org/develop/dapps/apis/sdk) like [ton-core](https://github.com/ton-org/ton-core), and provide a detailed explanation of its TL-B Schema with examples. After reading this article, readers will have a thorough understanding of TON's Dictionary.

## Basic Idea

We already know that in TON and TL-B, a Cell actually represents a [Tree](https://en.wikipedia.org/wiki/Tree_(abstract_data_type)). Each Cell can carry up to 1023 bits (approximately 128 bytes) of data and up to 4 subtrees (reference to other cells), as shown in the figure below. If you haven't grasped TL-B and Cells yet, it's advisable to begin with our earlier articles.


Specifically, a Cell is a type of [4-ary tree](https://en.wikipedia.org/wiki/M-ary_tree). This structure of a Cell is particularly well-suited for implementing a special kind of tree: [Trie](https://en.wikipedia.org/wiki/Trie) (also known as Prefix Tree). Tries can be used to implement [Dictionaries](https://en.wikipedia.org/wiki/Hash_table) (also called Maps, Hash Maps, Hash Tables, etc.). In fact, the Dictionary in TON and TL-B is indeed implemented using the Trie capability of Cells, utilizing only two-out-of-four branches. Let's illustrate this with a pseudocode example:

function testBasicIdea() {
  let dict = new Dictionary<uint16, uint32>();
  dict.set(0x0766, 0x1111);
  dict.set(0x07EE, 0x2222);
  dict.set(0x0B66, 0x3333);
  dict.set(0x0BEE, 0x4444);
  console.log(dict);
}

In the example above, `dict` stores 4 key-value pairs. These 4 keys share a common prefix `0x0`, so `0x0` can be stored in the Root Node. Similarly, `0x7` and `0xB` can be stored in their respective Internal Nodes. Finally, the remaining keys and values can be stored in their respective Leaf Nodes. In computer science, Trees are typically drawn with the root at the top, as shown in the following figure for the example above:


This outlines the fundamental approach to implementing the TL-B Dictionary. However, our example is intentionally simplistic, leaving room for enhancements. To achieve greater data density, the TL-B Dictionary incorporates some optimizations on this foundation, which will be explored in detail in subsequent sections.

## Dictionary API

Before analyzing the TL-B schema of the dictionary, let's take a galance at its presence in the TVM, TON contract programming languages, and TON SDKs.

### Dictionary in SDK

The Dictionary is so crucial that TON SDKs typically include built-in support for it. Taking the [TypeScript SDK](https://github.com/ton-org/ton-core) as an example, let's rewrite the previous pseudocode using `@ton/core`:

import assert from 'node:assert';
import { beginCell, Dictionary, } from '@ton/core'

function testBasicIdea() {
  let dict = Dictionary.empty(
    Dictionary.Keys.Uint(16),
    Dictionary.Values.Uint(32),
  );
  dict.set(0x0766, 0x1111);
  dict.set(0x07EE, 0x2222);
  dict.set(0x0B66, 0x3333);
  dict.set(0x0BEE, 0x4444);
  let cell = beginCell().storeDict(dict).endCell();
  assert.equal(cell.toString(), `x{C_}
 x{C4}
  x{E7_}
   x{BE600001111}
   x{BEE00002222}
  x{73}
   x{BE600003333}
   x{BEE00004444}`);
}

The code above is straightforward, and in the following sections, we will use TypeScript Library to write more tests that will aid our understanding of the Dictionary type.

### Dictionary in TVM

The TVM natively supports Dictionaries, with numerous [instructions](https://docs.ton.org/v3/documentation/tvm/instructions#quick-search) specifically designed for Dictionary operations. Thanks to TVM's support, TON's contract programming languages, such as [FunC](https://docs.ton.org/v3/documentation/smart-contracts/func/docs/stdlib#dictionaries-primitives), [Tolk](https://docs.ton.org/v3/documentation/smart-contracts/tolk/tolk-vs-func/stdlib), and [Tact](https://docs.tact-lang.org/book/maps/), inherently offer direct support for Dictionaries. The following table summarizes the basic APIs for Dictionaries in Func, Tact languages, and the TypeScript SDK:

| | Func | Tact | TypeScript SDK |
| ----------- | --------------------- | --------------- | ------------------ |
| Type Name | `Dictionary` | `map<K, V>` | `Dictionary<K, V>` |
| Main API | `new_dict()` | `emptyMap()` | `empty()` |
| | `dict_set(k, v)` | `set(k, v)` | `set(k, v)` |
| | `dict_add(k, v)` | | |
| | `dict_replace?(k, v)` | `replace(k, v)` | |
| | `dict_delete?(k)` | `del(k)` | `delete(k)` |
| | `dict_get?(k)` | `get(k)` | `get(k)` |
| | | `exists(k)` | `has(k)` |
| | `dict_empty?()` | `isEmpty()` | |
| | | | `clear()` |
| Builder API | `store_dict(x)` | | `storeDict(x)` |
| Slice API | `load_dict()` | | `loadDict()` |

## Dictionary Serialization

Next, I will introduce and thoroughly analyze the [TL-B Schema](https://github.com/ton-blockchain/ton/blob/v2024.10/crypto/tl/hashmap.tlb#L5) for Dictionaries. Below is its definition.

// ordinary Hashmap / HashmapE, with fixed length keys
//
hm_edge#_ {n:#} {X:Type} {l:#} {m:#} label:(HmLabel ~l n) 
          {n = (~m) + l} node:(HashmapNode m X) = Hashmap n X;

hmn_leaf#_ {X:Type} value:X = HashmapNode 0 X;
hmn_fork#_ {n:#} {X:Type} left:^(Hashmap n X) 
           right:^(Hashmap n X) = HashmapNode (n + 1) X;

hml_short$0 {m:#} {n:#} len:(Unary ~n) {n <= m} s:(n * Bit) = HmLabel ~n m;
hml_long$10 {m:#} n:(#<= m) s:(n * Bit) = HmLabel ~n m;
hml_same$11 {m:#} v:Bit n:(#<= m) = HmLabel ~n m;

unary_zero$0 = Unary ~0;
unary_succ$1 {n:#} x:(Unary ~n) = Unary ~(n + 1);

hme_empty$0 {n:#} {X:Type} = HashmapE n X;
hme_root$1 {n:#} {X:Type} root:^(Hashmap n X) = HashmapE n X;

Alright, the name "Hashmap" for the Dictionary might be somewhat misleading, but let's overlook this minor imperfection. This Schema appears to be somewhat intricate; if you are not yet well-versed in the basic syntax of TL-B, its built-in types, and advanced types, you may want to start by reading the first article in this series. Below, I will analyze this Schema bit by bit, in conjunction with practical examples.

### HashmapE

Let's first take a look at the entry point for the Dictionary type, `HashmapE`:

// HashmapE<n, X>
hme_empty$0 {n:#} {X:Type}                     = HashmapE n X;
hme_root$1  {n:#} {X:Type} root:^(Hashmap n X) = HashmapE n X;

As can be seen, `HashmapE` is a [parameterized type](https://docs.ton.org/v3/documentation/data-formats/tlb/tl-b-language#parametrized-types), where `n` denotes the number of bits occupied by the key, and `X` denotes the type of the value. For instance, `HashmapE 16 uint32` signifies a Dictionary with 16-bit keys and values of type `uint32`.

Clearly, if serializing an empty Dictionary, only a single Cell with the data `0` is produced. Otherwise, a Cell with the data `1` is produced, followed by another Cell containing the actual Dictionary data. We will use `@ton/core` to write some tests to verify our understanding is correct. The following test demonstrates that an empty Dictionary is indeed serialized as we analyzed. I will provide the code for the `cellToJSON()` function at the end of the article.

function testEmptyDict() {
  let dict = Dictionary.empty(
    Dictionary.Keys.Uint(16),
    Dictionary.Values.Uint(32),
  );
  let cell = beginCell().storeDict(dict).endCell();
  assert.equal(cellToJSON(cell), '{data: "0b0"}');
  //                                      ^^^
}

Let's look at a test for a non-empty Dictionary:

function testNonEmptyDict() {
  let dict = Dictionary.empty(
    Dictionary.Keys.Uint(16),
    Dictionary.Values.Uint(32),
  );
  dict.set(0x1234, 0x5678);
  let cell = beginCell().storeDict(dict).endCell();
  assert.equal(cellToJSON(cell),
    '{data: "0b1", refs: [{data: "0b101_0x0123400005678"}]}');
  //         ^^^
}

Our understanding is also correct; the root cell itself only stores data `1`, and the actual data is stored in the leaf cells, that is, within the `Hashmap`. These two situations are shown in the following figure:


### Hashmap

Below is the definition of the `Hashmap` type, which I have reformatted for easier readability:

// HmEdge<n, X, l, m>
hm_edge#_ {n:#} {X:Type} {l:#} {m:#} 
  label:(HmLabel ~l n) {n = (~m) + l}
  node:(HashmapNode m X)
= Hashmap n X;

`Hashmap` is also a parameterized type, consisting of four parameters:

* `n`: The number of bits occupied by the **Key**.
* `X`: The type of the **Value**.
* `l`: Indicates how many bits of the key are stored in this cell, that is, the length of the **Key Prefix**.
* `m`: Indicates how many bits of the key remain after excluding the prefix. Clearly: `l + m = n`.

`Hashmap` contains two parts of data:

* `label`: Of type `HmLabel`, storing the key prefix.
* `node`: Of type `HashmapNode`, storing the subtree after branching.

If you don't understand this part, don't worry, because we must first understand `HmLabel` and `HashmapNode` to fully grasp the `Hashmap` type. Keep reading, and then you can come back to review this section later.

### HmLabel

Next, we look at the definition of `HmLabel`. For ease of reading, I have adjusted the format:

hml_short$0 {m:#} {n:#} len:(Unary ~n) {n <= m} s:(n * Bit) = HmLabel ~n m;
hml_long$10 {m:#} n:(#<= m)                     s:(n * Bit) = HmLabel ~n m;
hml_same$11 {m:#} v:Bit n:(#<= m)                           = HmLabel ~n m;

We already know that `HmLabel` stores the prefix of the key. `HmLabel` is also a parameterized type with two Uint parameters: `m` and `n`. The first parameter `m` represents the total number of bits in the key, and the second parameter `n` represents the number of bits in the prefix stored by that Label. Please note that `m` does not need to be serialized in practice, and it is obvious that `n <= m`. To make the serialized data as compact as possible, `HmLabel` handles three cases separately: short prefix, long prefix, and prefixes that are all zeros or all ones. Let's take a closer look at these three cases.

#### hml_short

hml_short$0 {m:#} {n:#}
  len:(Unary ~n) {n <= m}
  s:(n * Bit)
= HmLabel ~n m;

If the key prefix is particularly short, then the first serialization method will be used: `hml_short`. In this case, the `Unary` type is used to store the length `n` of the prefix, followed by the storage of the prefix (`n` bits). Let's look at the definition of the `Unary`type:

unary_zero$0 = Unary ~0;
unary_succ$1 {n:#} x:(Unary ~n) = Unary ~(n + 1);

`Unary` is a recursive type, for more details about it, refer to the information [here](https://docs.ton.org/develop/data-formats/tl-b-types#unary). In short, to represent a particularly small positive integer `N`, `Unary` serializes N `1`s followed by a single `0`. For instance, `2` can be represented as `0b110`, and `3` can be represented as `0b1110`. Let's look at an example of `hml_short`:

function testLabelShort() {
  let dict = Dictionary.empty(
    Dictionary.Keys.Uint(16),
    Dictionary.Values.Uint(32),
  );
  dict.set(0xE123, 0x4567); // key: 0b11_10_000100100011
  dict.set(0xD123, 0x4567); // key: 0b11_01_000100100011
  let cell = beginCell().storeDict(dict).endCell();
  assert.equal(cellToJSON(cell),
    '{data: "0b1", refs: [{data: "0b01_0xB", refs: [{data: "0b101_0xB12300004567"}, {data: "0b101_0xA12300004567"}]}]}');
  //                              ^^^^^^^^
}

Please pay attention to cell data `0b01_0xB` (I have added comments), which is also `0b0_110_11` in Binary. The first bit is `0`, indicating that this is indeed a short key prefix. The next three bits are `0b110`, it represents `2` according to the definition of `Unary` type, so the length of the key prefix is 2 bits. The following two bits are the actual prefix data: `0b11`. We don't care about other data for now. The entire example is shown in the figure below:


#### hml_long

hml_long$10 {m:#}
  n:(#<= m)
  s:(n * Bit)
= HmLabel ~n m;

If the key prefix is relatively long and not all zeros or all ones, then `hml_long` will be used. This case is relatively easy to understand, which is to first store the length `n` of the prefix with the minimum number of bits, and then store the prefix itself: `n` bits. Let's look at an example:

function testLabelLong() {
  let dict = Dictionary.empty(
    Dictionary.Keys.Uint(16),
    Dictionary.Values.Uint(32),
  );
  dict.set(0xABCD, 0x1234);
  dict.set(0xABCE, 0x4568);
  let cell = beginCell().storeDict(dict).endCell();
  assert.equal(cellToJSON(cell),
    '{data: "0b1", refs: [{data: "0b1_0x3AAF3", refs: [{data: "0x500001234"}, {data: "0x400004568"}]}]}');
  //                              ^^^^^^^^^^^
}

Note the cell data `0b1_0x3AAF3`, which is `0b10_01110_1010_1011_1100_11` in Binary. Since the first two bits are `0b10`, it can be confirmed that this is a `hml_long`. In our example dictionary, the key length is 16 bits, so it requires 5 bits to store `n`, which is `0b01110`, or `14` in Decimal. Next comes exactly 14 bits, `0b1010_1011_1100_11`, which is `0xABC_0b11` in Hex_Binary. We don't care about other data for now. The entire example is shown in the figure below:


#### hml_same

hml_same$11 {m:#}
  v:Bit
  n:(#<= m)
= HmLabel ~n m;

If the key prefix is relatively long and is all zeros or all ones, then `hml_same` will be used. In this case, a single bit is first used to record whether it is all zeros or all ones, and then the length `n` of the key prefix is recorded. Let's look at an example:

function testLabelSame() {
  let dict = Dictionary.empty(
    Dictionary.Keys.Uint(16),
    Dictionary.Values.Uint(32),
  );
  dict.set(0xFFFF, 0x1234);
  dict.set(0xFFF0, 0x5678);
  let cell = beginCell().storeDict(dict).endCell();
  assert.equal(cellToJSON(cell),
    '{data: "0b1", refs: [{data: "0xEC", refs: [{data: "0b1_0xB00005678"}, {data: "0b1_0xF00001234"}]}]}');
  //                              ^^^^
}

Note the cell data `0xEC`, which is `0b11_1_01100` in Binary. The first two bits are `0b11`, so it can be confirmed that this is an `hml_same`. The next bit is `1`, so this is a prefix of all `1`s. In our example dictionary, the key length is 16 bits, so it requires 5 bits to store `n`, which is `0b01100`, or `12` in Decimal. So the actual key prefix is `0b1111_1111_1111`, or `0xFFF`. We will explain the remaining data in the following sections. The entire example is shown in the figure below:


### HashmapNode

Finally, let's take a look at `HashmapNode`. Below is its definition. For ease of reading, I have adjusted the format:

hmn_leaf#_ {X:Type} 
  value:X
= HashmapNode 0 X;

hmn_fork#_ {n:#} {X:Type}
  left:^(Hashmap n X) 
  right:^(Hashmap n X)
= HashmapNode (n + 1) X;

Since the keys of the Dictionary are of fixed length, `HashmapNode` is divided into two cases: `hmn_leaf` or `hmn_fork`. `HashmapNode` is also a parameterized type with two parameters: `n` and `X`. Param `n` represents the remaining number of bits of the key, and `X` is the type of the value. Let's first look at `hmn_fork`.

#### hmn_fork

hmn_fork#_ {n:#} {X:Type}
  left:^(Hashmap n X) 
  right:^(Hashmap n X)
= HashmapNode (n + 1) X;

When a fork is needed, `hmn_fork` stores the left and right subtrees in their own respective Cells. It should be noted that the parameter `n` is entirely derived from the previous situation. In fact, all three examples in the previous `HmLabel` have resulted in `hmn_fork`. Let's take the `testLabelSame()` test as an example:

  let dict = Dictionary.empty(
    Dictionary.Keys.Uint(16),
    Dictionary.Values.Uint(32),
  );
  dict.set(0xFFFF, 0x1234);
  dict.set(0xFFF0, 0x5678);

Let's substitute `n = 16` and `X = uint32` into the `Hashmap n X` type, which gives us:

hm_edge#_ {n:16} {X:uint32} {l:#} {m:#} 
  label:(HmLabel ~l 16) {16 = (~m) + l}
  node:(HashmapNode m uint32)
= Hashmap 16 uint32;

Additionally, based on the previous analysis, we know that `l = 12`, `m = 16 - 12 = 4`. After substituting `l` and `m`, we get:

hm_edge#_ {n:16} {X:uint32} {l:12} {m:4} 
  label:(HmLabel 12 16) {16 = 4 + 12}
  node:(HashmapNode 4 uint32)
= Hashmap 16 uint32;

Since `m`, the remaining key, is greater than zero, we know that we need a `hmn_fork`:

hmn_fork#_ {n:3} {X:uint32}
  left:^(Hashmap 3 uint32) 
  right:^(Hashmap 3 uint32)
= HashmapNode (3 + 1) uint32;

Our key is 16 bits long, and the prefix is 12 bits long (`0xFFF`), so there are still 4 bits left to process. However, since we only have two branches, we can save one bit: the left branch represents `0`, and the right branch represents `1`. After removing this bit, we get two subtrees, left and right, with a key length of 3 bits. By recursively continuing to analyze the `HashmapNode`, we can unfold all the data, as shown in the figure below:


#### hmn_leaf

hmn_leaf#_ {X:Type} value:X = HashmapNode 0 X;

Leaf nodes only need to save the value. Let's continue analyzing the above example. By substituting `n = 3` and `X = uint16` into `HashmapNode`, we get:

hm_edge#_ {n:3} {X:uint32} {l:#} {m:#} 
  label:(HmLabel ~l 3) {3 = (~m) + l}
  node:(HashmapNode m uint32)
= Hashmap 3 uint32;

Taking the left subtree as an example, the cell data is `0b11_011_0x00005678`. Based on the first two bits (`0b11`), we know that this is an `hml_same`. Then there is a bit `0`, followed by two bits of `0b11`, so we know that the key prefix is three zeros: `0b000`. Thus, we can deduce that `l = 3`, `m = 0`. Therefore, we have:

hmn_leaf#_ {X:uint32} value:uint32 = HashmapNode 0 uint32;

The remaining data is exactly the 32-bit value: `0x00005678`. As shown in the figure below:


Congratulations🎉! You now fully understand the TL-B Schema for the TON Dictionary type! Let's summarize the entire `HashmapE` type, as shown in the figure below:


## Summary

In this article, I first briefly introduced the basic concepts of data structures such as Tree, Trie, and Dictionary. Then I introduced the basic API and usage of the Dictionary type in TVM, TON contract programming languages like FunC and Tact, as well as in the TypeScript Library. Lastly, I combined examples to introduce and thoroughly analyze the serialization format of the Dictionary, namely its TL-B Schema. After reading this article, I believe readers will have a clear understanding of TON Dictionary. See you in the next article!

Buy me a cup of coffee if this article has been helpful to you:

* EVM: `0x8f7BEE940b9F27E8d12F6a4046b9EC57c940c0FA`
* TON: `UQBk1flhLnRsAebsYFnvt8HUwI4s_dbG7w3AzpyH5SbIHq_S`

## Appendix

Here is the complete code for the `cellToJSON()` helper function:

import { BitString, Cell } from '@ton/core'

export function cellToJSON(cell: Cell) {
  let str = '{data: "' + bitsToStr(cell.bits) + '"';
  if (cell.refs.length > 0) {
    str += ', refs: [';
    for (let i = 0; i < cell.refs.length; i++) {
      if (i > 0) {
        str += ', ';
      }
      str += cellToJSON(cell.refs[i]);
    }
    str += ']';
  }
  str += '}';
  return str;
}

function bitsToStr(bits: BitString) {
  const n = bits.length;
  const x = n % 4;
  if (x == 0) {
    return '0x' + bits.toString();
  } else {
    let bin = '0b';
    for (let i = 0; i < x; i++) {
      bin += bits.at(i) ? '1' : '0';
    }
    if (n == x) {
      return bin;
    } else {
      const hex = '0x' + bits.substring(x, n - x).toString();
      return bin + '_' + hex;
    }
  }
}