跳跳球队列：在标记、有序数据中跳跃和跳过

一个 hopscotch::Queue<K, V> 是一个先进先出的队列，其中队列中的每个 Item<K, V> 具有值

• 类型为 V，
• 一个不可变的标签类型为 K，以及
• 一个唯一的 index 类型为 u64，它在创建队列时按插入顺序分配，从 0 开始。

除了支持 FIFO 队列的普通 push、pop 和 get 方法外，跳跳球队列还支持特殊、优化的方法 after、after_mut、before 和 before_mut。

这些方法查找队列中标签等于给定标签集的任何标签的下一个（或上一个）Item（或 ItemMut）。例如，after 的签名是

pub fn after<'a, Tags>(&self, index: u64, tags: Tags) -> Option<Item<K, V>>
    where
        Tags: IntoIterator<Item = &'a K>,
        K: 'a,

如果我们用 &[K] 作为 Tags，则此签名简化为

pub fn after(&self, index: u64, tags: &[K]) -> Option<Item<K, V>>

这些方法是使用跳跳球队列而不是其他数据结构的真正好处。它们的渐近时间复杂度是

• 与查询的标签数量成线性关系，
• 与队列中不同标签的总数成对数关系，
• 与队列长度成常数关系，以及
• 与具有相同标签的连续项之间的距离成常数关系。

跳跳球队列还提供了灵活的迭代器 Iter(Mut)，以有效地遍历其内容的部分，通过 Iter(Mut)::until 和 Iter(Mut)::after 按索引切片，并使用 Iter(Mut)::matching_only 通过所需的标签集过滤。

我什么时候会使用这个？

该队列在以下情况下表现良好：

• 队列中总标签集较小
• 查询操作的数量大于插入/删除操作的数量
• 可以承受一点额外的内存用于记录

此类结构的一个用例是实现一个有界pub/sub事件缓冲区，其中对特定事件子集感兴趣的客户会重复查询下一个符合其所需子集的事件。这种场景充分发挥了跳转队列的优势，因为每个查询都可以非常快地完成，无论缓冲区的内容或大小如何。

与VecDeque<K, T>的等价操作相比，push和pop操作的速度要慢得多，但代价是几乎可以以恒定时间跳过和跳转到标签集。

在只有几百个标签的场景中，我的机器（较新的MacBook Pro）上的push和pop操作大约需要低个位数的微秒（每秒数百万次操作），而after/before查询大约需要几十纳秒（每秒数千万次操作），具体取决于队列中标签的数量。更详细和科学的基准测试即将到来，请随时贡献！