Hopscotch - 用 Rust 实现的跳表

如其名。因为它会跳过。

动机

注意这是一个玩具项目，目前不打算用于生产环境...也许吧。其主要用途将是作为数据库内部教学项目的一部分。

详细信息

v1 版本的算法实现与 Pugh 的原始论文中描述的算法基本一致。

使用几何分布来确定新键是否属于某一层（相当于抛硬币）。几何分布默认为 p = 0.25，但这是可配置的。

并发

注意：这里可能存在一些未定义的行为（听起来很糟糕）。除非你真的想尝试一些疯狂的技巧，否则不要使用这个。

通过启用 concurrent 功能，现在有一种跳表版本允许无锁并发读取。这个跳表有几个主要的功能差距

1. 调用者必须在插入之前获取跳表的锁（例如 Mutex 或 RwLock）。

2. 尚未实现删除，因为我的用例不需要删除。

计划随后进行适当的完全并发和几乎无锁跳表的实现。

其他艺术

• 地铁
• rust-skiplist
• crossbeam-skiplist

参考

• 博客 - 跳表笔记和参考
• OpenDSA - 15.1 跳表
• 用完全太多的链表学习 Rust
• 高级生命周期
• std::linked_list
• Rust 中创建迭代器的优秀参考：在 Rust 中创建迭代器