O(1)额外空间查找数据结构

Question

我想知道是否有一种简单的数据结构，支持摊销O(log n)的查找和插入操作，就像自平衡二叉搜索树一样，但是内存开销为常量。（我不太在意删除元素。）

我的一个想法是将所有元素存储在一个连续的内存块中，分成两个连续的块：一个S部分，其中所有元素都已排序，还有一个未排序的U部分。

要执行插入操作，我们可以将一个元素添加到U中，如果U的大小超过了log（S的大小），则对整个连续数组进行排序（将S和U都视为一个连续的数组），以便在排序之后，所有内容都在S中，而U为空。

要执行查找操作，请在S上运行二进制搜索，并查看所有U中的内容。

然而，我在计算我的算法的摊销插入时间时遇到了麻烦。

最终，我只需要一些具有所需属性的相当简单的算法/数据结构，并保证它以摊销时间运行得相当快。

谢谢！

- math4tots

---

你已经有一个不错的数据想法了。我猜插入成本分摊的问题在于当你插入并必须按排序顺序合并S和U时，这至少是线性成本？而且它发生的频率比你想象的要高？这听起来有点像如果你在向数组中插入元素时增加常量数量所遇到的问题（除了这里似乎不适用将数组大小加倍的解决方案）。 - TooTone

@TooTone 当我发帖时，其实并不确定我的想法是否足够好。但是读了axel22的帖子后，似乎我的想法可能还不够好。此外，我并没有打算进行原地合并，因为正如axel22所指出的那样，原地合并很困难。我只是打算用N*log(N)的时间复杂度对其进行排序。 - math4tots

我从axel22的帖子中学到了一些东西。关于合并，由于|U| << |S|，如果你准备好制作一个U的临时副本，那么也许你仍然可以原地合并？因此，您可以通过覆盖距离S最远的U元素来开始合并（因此，每次进行合并时，S和U的顺序都必须切换）。如果您有足够大的缓冲区，您甚至可能会有多余的空间。 - TooTone

如果你还没有这样做，那么请彻底检查一下对象中是否有任何重复/不必要/可压缩的数据。这通常比尝试设计一个特定于问题的数据结构更好（尽管这可能在过去导致了一些数据结构的发现）。 - Bernhard Barker

Answer 1

如果您所说的“恒定内存开销”是指对于数据结构中存储的N个元素，空间消耗应为O（N），那么任何“平衡树”都可以胜任——实际上，任何外部叶子中存储元素的n叉树都具有此属性，其中n>1且每个外部树都包含一个元素。

这是因为任何具有N个节点的树图都有N-1条边。

如果您所说的“恒定内存开销”是指对于N个元素，空间消耗应为N + O（1），则平衡树和哈希表都没有此属性——两者都将使用k * N的内存，其中k>1是由于树的额外节点指针和哈希表的负载因子。

我认为你的方法很有趣，但是即使您只对U进行排序，然后在线性时间内合并两个集合，我也不认为它会起作用。您需要在每次logN更新之后进行排序（O(logN * log(logN))操作），然后合并S和U的O(n)操作（请注意，到目前为止，nobody actually knows how to do this in linear time这样做就可以了，也就是说，不需要额外的数组）。

平摊插入时间将为O(n / logN)。但是，如果允许U的大小增长到S的平方根，则可能使用您的方法实现接近O(√n)的结果。

- axel22

---

实际上我的意思是不要使用比存储对象所需更多的内存。我之所以问这个问题是因为我正在进行一些科学计算，我的程序只使用了将近8GB。此外，我喜欢将所有项目保存在一个连续的数组中的想法。 - math4tots

我一开始误解了你的意思 - 我修改了我的答案。 - axel22

@axel22 直觉上，我不确定在满足 O(1) 存储和 O(logN) 搜索及插入的情况下 OP 的问题是否有解，而且我认为你的答案表明了没有这样的解决方案。需要补充的一点是，如果您允许 U 增长到 S 的平方根，您将获得 O(√n) 的插入时间，但搜索时间将从 O(logN) 下降到 O(√n)，因为 U 是一个无序数组。可以通过放宽 O(1) 存储限制并仅针对 U 使用平衡树来解决这个问题。无论如何，似乎存在权衡。 - TooTone

Answer 2

任何哈希表都可以做到这一点。唯一棘手的部分是如何解决冲突 - 有几种方法可以做到这一点，另一个棘手的部分是正确的哈希计算。

See: http://en.wikipedia.org/wiki/Hash_table

- Adrian

---

我实际上想避免使用哈希表，因为1）我认为哈希表本身需要比我的数据集成比例更大（因此我需要超过O（1）的额外内存），2）编写良好的哈希函数很棘手。 - math4tots

如果您不想使用哈希表，那么唯一合理的选择就是平衡树。至于哈希表 - 这完全取决于您使用的技术。大多数编程语言都支持哈希表并将其包含在库中，这同样适用于哈希函数。如果您的对象由几个其他对象组成，您可以为它创建一个哈希值，使其成为其中一个对象，就像在数据库字段中一样，其中一些字段可能用作ID，并使用此字段的哈希函数作为整个对象的哈希函数。 - Adrian

@Adrian 我认为你忘记了他对常量内存开销的要求。这意味着不能向每个对象添加指针。这也意味着您不能使用哈希表，因为据我所知，没有哈希表实现实际上使用恒定的额外空间。它们中的大多数实际上使用所需空间的1.75倍。如果不这样做，那么会有很多冲突。由于冲突是通过开放寻址或分离链接处理的，因此（对我来说）运行时间仍然无法保证...也无法保证内存。 - rliu