HashSeq

适用于无权限网络和无限协作者数量的拜占庭容错（BFT）序列 CRDT。

当前复杂度

这仍然是 WIP，我认为我们可以通过一些巧妙的索引策略大幅度提高这些指标

设计

每个插入操作都会产生一个包含值、左邻节点的哈希值和右邻节点的 Node。

struct Node<V> {
   value: V,
   lefts: Set<Hash>,
   rights: Set<Hash>,
}

例如。

按顺序插入 'a'、'b'、'c' 产生以下图

 a <- b <- c

在 'a' 和 'b' 之间插入 'd'

a <- d -> b <- c
   \_____/

我们通过执行有偏拓扑排序来线性化这些哈希图。

在有多个线性化满足左右约束的情况下，偏置用于决定规范排序。

例如。

            s - a - m
           /         \
h - i - ' '           ! - !
           \         /
            d - a - n

上面的哈希图可以序列化为 hi samdan!! 或 hi dansam 或任何 sam/dan 的交错：hi sdaamn，hi sdanam，... 。我们需要一个规范排序来保留一些语义信息（即不允许并发运行的交错）

我们的选择是：在分叉中，我们选择起始元素哈希值较小的分支，然后为了避免并发运行的交错，我们的拓扑排序是深度优先而不是传统的广度优先。

所以在这个例子中，假设 hash(s) < hash(d)，我们会得到：hi samdan!!。

优化

如果我们检测到哈希链，我们可以将其合并为第一个左哈希值和右哈希值

struct Run<T> {
   run: Vec<T>
   lefts: Set<Hash>
   rights: Set<Hash>
}

即第一个例子中，a、b、c 是顺序的，它们都有一个共同的右手边（空集合），并且它们的左手边是序列中的前一个元素。

所以我们可以这样表示

// a <- b <- c == RUN("abc")

Run {
  run: "abc",
  lefts: {},
  rights: {}
}

插入 'd' 分裂了运行

a <- d -> RUN("bc")
   \_____/

还有分叉示例

           RUN("sam")
          /          \
RUN("hi ")            RUN("!!")
          \          /
           RUN("dan")

这样我们只在分叉处存储哈希值，其余的可以在需要时重新计算。