这里使用什么数据结构

Question

哈希提供了一种极好的机制,可以在几乎O(1)时间内提取与某个给定键相对应的值.但它永远不会保留键插入的顺序.那么有没有任何数据结构可以模拟最好的数组和哈希值,也就是说,及时返回对应于给定键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或类似的模块将无法做到,我有责任从头开始开发它!

Answer 1

现在,这个问题对我来说也很清楚(迟到总比没有好......)这是我的建议:

• 你可以维护两个哈希:一个有键,一个有插入顺序.然而,这在删除和插入之间时非常难以维护.这将提供两种方式访问​​元素所需的相同O(1)时间.
• 您可以为键使用哈希,并为插入顺序维护一个数组.这个比哈希类型好很多,删除仍然不是很快,但我认为仍然比使用两个哈希方法快得多.这也在访问第n个元素时给出了真实的O(1).

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

在Java中,有针对此特定任务的LinkedHashMap.

不过我觉得如果有人找到这个页面,这可能不会完全没用,所以我把它放在这里......

Answer 2

这取决于可以为此数据结构分配多少内存.对于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(log N),同时保留O(1)用于其他操作.但是,如果您同意每次操作的O(log N)时间,则可以.基于二叉搜索树或跳过列表的解决方案允许它.一个选项是订单统计树.您可以使用计数器扩充二叉搜索树的每个节点,在该节点下存储子树中的元素数量; 然后用它来查找第n个节点.其他选项是使用Indexable skiplist.还有一种选择是使用O(M*N ^1/M)解,其中M = log(N).
• 而且我认为你不能在不增加其他操作时间的情况下获得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数组后,您可以通过首先在此2D数组中按位置和当前"状态"进行索引,然后在数组中使用值进行索引来执行此操作.

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

实际上,使用整数位设置索引数组会限制N的指针大小(通常为64),更多的是受可用内存的限制.为了缓解这种情况,我们可以将数组和位集分成大小为N/C的子数组,其中C是一些常量.现在我们可以使用较小的2D数组来查找每个子数组中的第n个元素.为了在整个结构中找到第n个元素,我们需要额外的结构来记录每个子数组中有效元素的数量.这是一个大小为C的结构,因此它上面的每个操作也都是O(1).这个额外的结构可以实现为数组,但最好使用像可索引跳转列表这样的对数时间结构.在此修改之后,每个操作的时间复杂度仍为O(1); 空间复杂度为O(N 2 ^N/C).