6

O(1)哈希提供了一种极好的机制，可以在几乎时间内提取与某个给定键对应的值。但它从不保留插入键的顺序。那么有没有什么数据结构可以模拟最好的数组和hash，即及时返回给定key对应的值O(1)，以及及时返回nth插入的值O(1)呢？应该保持顺序，即，如果散列是{a:1,b:2,c:3}，并且类似的事情del hash[b]已经完成，nth(2)应该返回{c,3}。

例子：

hash = {};
hash[a] = 1;
hash[b] = 2;
hash[c] = 3;
nth(2); //should return 2
hash[d] = 4;
del hash[c];
nth(3); //should return 4, as 'd' has been shifted up

使用类似TIE::Hash或类似的模块是行不通的，我有责任从头开始开发它！

4

4 回答 4

8

现在，这个问题对我来说也很清楚（迟到总比没有好......）这是我的建议：

  • 您可以维护两个散列：一个带有键，一个带有插入顺序。然而，这在删除和插入时非常难看且维护缓慢。这将给以两种方式访问​​元素所需的几乎相同的 O(1) 时间。
  • 您可以对键使用哈希，并为插入顺序维护一个数组。这个比散列类型好很多，删除仍然不是很快，但我认为仍然比使用两个散列方法快很多。这在访问第 n 个元素时也给出了真正的 O(1)。

起初，我误解了这个问题，并给出了一个解决方案，它给出了 O(1) 键查找和 O(n) 查找第 n 个元素：

在 Java 中，有用于此特定任务的LinkedHashMap。

但是我认为如果有人找到这个页面，这可能不是完全没用的，所以我把它留在这里......

于 2012-10-19T08:59:12.637 回答
8

这取决于可以为此数据结构分配多少内存。对于 O(N) 空间，有几种选择：

  • 很容易获得每个操作的 O(1) 时间的数据结构：“按键获取值”、“插入第 n 个值”、“插入”——但仅当“删除”时间为 O(N) 时。只需使用哈希映射和数组的组合，如 ppeterka 所述。
  • 不太明显，但仍然简单的是“删除”的 O(sqrt N) 和所有其他操作的 O(1)。
  • 稍微复杂一点的是在 O(N 1/4 )、O(N 1/6 ) 或一般情况下在 O(M*N 1/M ) 时间内“删除”。
  • 在为其他操作保留 O(1) 的同时，将“删除”时间减少到 O(log N) 很可能是不可能的。但是，如果您同意每个操作的 O(log N) 时间，这是可能的。基于二叉搜索树或跳过列表的解决方案允许它。一种选择是订单统计树。您可以使用计数器扩充二叉搜索树的每个节点，存储该节点下子树中元素的数量；然后用它找到第n个节点。其他选项是使用Indexable skiplist。另一种选择是使用 M=log(N) 的 O(M*N 1/M ) 解决方案。
  • 而且我认为你不能在不增加其他操作时间的情况下获得 O(1)“删除”。

如果有无限空间可用，您可以在 O(1) 时间内完成所有操作。

O(sqrt N) “删除”

您可以使用两种数据结构的组合来按键查找值并按插入顺序查找值。第一个是哈希映射（将键映射到值和其他结构中的位置）。第二个是分层向量，它将位置映射到值和键。

分层向量是一种比较简单的数据结构，它可以很容易地从零开始开发。主要思想是将数组拆分为 sqrt(N) 个较小的数组，每个数组的大小为 sqrt(N)。每个小数组在删除后只需要 O(sqrt N) 时间来移动值。而且由于每个小数组都实现为循环缓冲区, 小数组可以在 O(1) 时间内交换单个元素，这允许在 O(sqrt N) 时间内完成“删除”操作（每个子数组在删除值和第一个/最后一个子数组之间进行这样的交换） . 分层向量也允许在 O(sqrt N) 中插入到中间，但是这个问题不需要它，所以我们可以在 O(1) 的时间内在末尾追加一个新元素。要通过位置访问元素，我们需要确定子数组的循环缓冲区的起始位置，该位置存储元素，然后从循环缓冲区中获取该元素；这也需要 O(1) 时间。

由于散列图会记住其每个键在分层向量中的位置，因此当分层向量中的任何元素更改位置时（O(sqrt N) 散列图更新每个“删除”），它应该被更新。

O(M*N 1/M ) “删除”

要进一步优化“删除”操作，您可以使用此答案中描述的方法。它懒惰地删除元素并使用 trie 调整元素的位置，同时考虑到已删除的元素。

O(1) 对于每个操作

您可以使用三种数据结构的组合来执行此操作。第一个是哈希映射（将键映射到数组中的值和位置）。第二个是一个数组，它将位置映射到值和键。第三个是一个位集，数组的每个元素一个位。

“插入”操作只是在数组的末尾再添加一个元素并将其插入到哈希映射中。

“删除”操作只是取消设置位集中的相应位（每个位 = 1 初始化）。它还从哈希映射中删除相应的条目。（它不会移动数组或位集的元素）。如果在“删除”后，位集删除的元素比例超过某个恒定比例（如 10%），则应从头开始重新创建整个数据结构（这允许 O(1) 摊销时间）。

“按键查找”是微不足道的，这里只使用哈希映射。

“按位置查找”需要一些预处理。准备一个二维数组。一个索引是我们搜索的位置。其他索引是我们数据结构的当前状态，位集，重新解释为索引。计算每个可能的位集的每个前缀的人口计数并存储前缀长度，由人口计数和位集本身索引。准备好这个 2D 数组后，您可以通过首先按此 2D 数组中的位置和当前“状态”进行索引，然后在数组中使用值进行索引来执行此操作。

每个操作的时间复杂度是 O(1)（对于插入/删除，它是 O(1) 摊销的）。空间复杂度为 O(N 2 N )。

在实践中，使用整数集来索引数组会限制指针大小（通常为 64）允许的 N 值，甚至更多地受到可用内存的限制。为了缓解这种情况，我们可以将数组和位集拆分为大小为 N/C 的子数组，其中 C 是某个常数。现在我们可以使用一个较小的二维数组来查找每个子数组中的第 n 个元素。为了在整个结构中找到第 n 个元素，我们需要额外的结构来记录每个子数组中有效元素的数量。这是一个恒定大小 C 的结构，因此对其的每个操作也是 O(1)。我可以将这个附加结构实现为一个数组，但最好使用一些对数时间结构，如可索引的跳过列表。修改后，每个操作的时间复杂度仍然是O(1)；空间复杂度为 O(N 2 N/C )。

于 2012-10-22T14:48:21.363 回答
3

您引用的所有内容在 O(1) 中都没有数据结构。特别是在中间具有随机动态插入/删除和排序/索引访问的任何数据结构的维护时间都不能低于 O(log N)，要维护这样一个动态集合，您必须使用运算符“小于”(二进制因此 O(log2 N)) 或一些计算组织（典型的 O(sqrt N)，通过使用 sqrt(N) 子数组）。注意 O(sqrt N)>O(log N)。

所以不行。

您可能会在所有事情上达到 O(1)，包括使用链表 + 哈希映射保持顺序，如果访问主要是顺序的，您可以缓存 nth(x)，以在 O(1) 中访问 nth(x+/-1)。

于 2012-10-27T10:08:17.500 回答
0

我想只有一个普通数组会给你 O(1)，最好的变体是寻找在最坏情况下给出 O(n) 的解决方案。您还可以使用一种非常糟糕的方法 - 使用键作为普通数组中的索引。我想有一种方法可以将任何键转换为普通数组中的索引。

std::string memoryMap[0x10000];
int key = 100;
std::string value = "Hello, World!";
memoryMap[key] = value;
于 2012-10-19T19:10:32.167 回答