数据结构：初始化，插入，缺失，找到一个元件，删除所有元素

提出，其保持从0个元素到n的数据结构 - 1并支持 O（1）时间的所有以下操作：初始化，插入元素，删除元素，查找元素，删除所有元素。

散列表（假设没有碰撞，即最好的情况）将支持O（1）中的插入和搜索。我不确定删除，但...任何想法？

2011-10-02 user7

行我认为，如果N是愤怒内可以只声明N个元素

0)Initialize 
memset(A,0,sizeof(A)) 

1) Insert i 
A[i] = 1 

2) Remove i 
A[i] = 0 

3) Find i 
if(A[i]) 

4) Delete All 
memset(A,0,sizeof(A))

2011-10-02 17:17:40 FUD

bool allDelete = true？ – user7

谢谢你的回答......它是有道理的，但memset是一个O（1）操作？ – user7

我认为我们应该认为memset（）不是O（1）操作。 –

哈希表可以是O（1），用于删除的阵列。

List<Object> hashTableData = new ArrayList<Object>();

编辑：代码是为哈希表存储的数据的可能实现。

2011-10-02 17:18:43 DwB

我不是Java程序员，所以一般来说散列表通常是指向链接列表的指针数组，加上一个非常好的散列函数...所以要从散列表中删除所有元素，必须首先释放每个链表...不是一个O（n）操作 – user7

请注意，您包括“假设没有冲突”。这取决于它是如何实施的。如果你有一些东西，并使用散列函数来获取你想要的东西的索引，并且散列函数不会创建重复项，那么你不需要链接列表，只需要数组。 – DwB

我想你是对的。如果散列函数足够“随机”，则插入，删除和查找应该采用预期的O（1）时间。但即使没有冲突，是否初始化并删除所有元素O（1）？ – user7

非常有趣的问题！

假设内存分配和处理是O（1），那么所有的O（1）都是可能的。

为此，我们使用Hopcroft和Ullman的技巧，它允许我们使用大小为n的数组，而不必花Omega（n）时间来实际初始化它们。

在INSERT，我们只是使用上述阵列并将其设置为1.在搜索，如果发现数组元素未初始化，返回0。删除，我们将其设置为0.

关于全部删除，我们释放数据结构并使用新的。

2011-10-03 06:07:49

当我们不知道搜索值位于哪个索引时，搜索操作将如何O（1）？ –

@cyber_raj：除了我们知道的O（1）时间，如果我们正在访问一个未初始化的元素，在这种情况下，我们可以返回默认的初始化值，这个数组就像其他数组一样。我建议你在上述博客链接的“解决方案”部分阅读第1点。 –

如果在开始的时候，从[]到[]都是未初始化的，它们包含的垃圾数据是否满足声明vec [i]已被设置的必要条件？这是一种罕见的边缘情况，但在技术上不可行吗？ –

回答