有这样一种数据结构——“带样本的链表”吗？

Question

有这样的数据结构吗：

1. 有一种缓慢的列表数据结构，如链表或保存在磁盘上的数据。
2. 有一个相对较小的指向“缓慢列表”中某些元素的指针数组，希望它们均匀分布。

然后当您进行搜索时，首先检查数组，然后执行正常搜索（链表搜索或磁盘数据的二进制搜索）。

这看起来非常类似于跳跃搜索、采样搜索和跳跃表，但我认为是不同的算法。

请注意，我以链接列表或文件在磁盘上作为示例，因为它们是缓慢的结构。

- Nick

---

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Tim Biegeleisen

Answer 1

我不知道这个算法是否有一个名字（尽管我认为它不值得一个名字，但如果没有的话，它可以用我的名字命名 :）），但是10年前我为了面试实现了类似的东西。 您可以拥有一个指向列表元素的指针数组。一个固定大小的数组，比如256个指针。当您构建列表或第一次遍历它时，您将指向其元素的指针存储在数组中。因此，对于256个或更少元素的列表，您将拥有每个元素的指针。 随着列表增长超过256个元素，您通过将128个偶数指针移动到数组的开头来删除每个奇数编号的指针。当指针数组再次填满时，您重复该过程。在每个这样的点上，您将在指针数组中结束的列表元素之间的步骤加倍。最初，您会在那里放置每个元素的地址，然后放置每个其他元素的地址，然后放置每四个元素中的一个元素的地址，以此类推。 最终，您将获得一个指向离列表长度/ 256间隔的列表元素的指针数组。

如果列表是单向链表，则从开头或结尾定位第i个元素可缩小到在1/256的列表中搜索。 如果列表已排序，则可以在数组上执行二进制搜索以定位bin（列表的1/256部分），从而进一步查找。

- Alexey Frunze