#memoization #merkle-trees #hash-cons


Hash cons'ing for compact representations of shared, immutable data structures

2 releases

0.1.2 Jan 21, 2020
0.1.1 Jul 28, 2018

#834 in Encoding

Download history 4/week @ 2023-06-16 3/week @ 2023-06-23 3/week @ 2023-06-30 1/week @ 2023-07-21 1/week @ 2023-07-28 1/week @ 2023-08-11 3/week @ 2023-08-18 14/week @ 2023-08-25 46/week @ 2023-09-01 99/week @ 2023-09-08 61/week @ 2023-09-15 102/week @ 2023-09-22

309 downloads per month

MPL-2.0 license

239 lines

Hash Cons'ing for Rust

Sometimes, an Rc<T> is insufficient for efficient, compact immmutable structures.

By contrast:

  • A Merkle<T> gives a compact serialization in the presence of sharing.

  • A Hc<T> gives a unique representation in the presence of sharing.


  • The type Merkle<_> is implemented and tested.
  • The type Hc<_> is a minor variation; it remains as future work.


Sometimes, we want a shared instance of some type T that serializes once, not once per reference, as is the case with the Rc type.

Unlike a "bare" Rc<T>, a Merkle<T> enjoys the practical property that, when a structure holding multiple (shared) instances of Merkle<T> is serialized, this serialized output holds only one occurrence of each T's serialized representation; the other occurrences merely consist of the T's unique identifier (the serialization of an Id, single machine word on modern machines).

Implementation summary

A Merkle<T> has a unique ID (computed as a hash) that permits table-based indirection, via temporary storage used by serialization and serialization logic.

By contrast, a bare Rc<T> lacks this indirection, and thus, it lacks a compact serialized representation for structures with abundant sharing. Generally, abundant sharing via many shared Rc<_>s leads to exponential blow up in terms of serialized space and time.


~34K SLoC