Java LinkedHashSet从末尾删除一些元素

我正在处理一个问题，我需要存储具有无复制和维护顺序的需求的元素。我选择了LinkedHashSet因为它满足了我的要求。Java LinkedHashSet从末尾删除一些元素

比方说，我有这样的代码：

LinkedHashSet hs = new LinkedHashSet(); 
    hs.add("B"); 
    hs.add("A"); 
    hs.add("D"); 
    hs.add("E"); 
    hs.add("C"); 
    hs.add("F"); 
    if(hs.contains("D")){ 
     //do something to remove elements added after"D" i-e remove "E", "C" and "F" 
     //maybe hs.removeAll(Collection<?>c) ?? 
    }

任何人都可以请指导我的逻辑删除这些元素呢？

我使用了错误的数据结构吗？如果是这样，那么更好的选择是什么？

来源

2013-04-08 Jazib

因此，在尝试了上面提到的几件事之后，我选择了实现不同的数据结构。因为我没有与O（N），对于这个问题的任何问题（如我的数据是非常小的）

我用图形，该库进来非常方便：http://jgrapht.org/

什么我做的是加入所有元素作为顶点到DirectedGraph也创建它们之间的边缘（边缘帮助我解决了另一个不相关的问题）。而当它的时间来消除我用递归函数的元素与下面的伪代码：

removeElements(element) { 

tempEdge = graph.getOutgoingEdgeFrom(element) 
if(tempEdge !=null) 
    return; 
tempVertex = graph.getTargetVertex(tempEdge) 
removeElements(tempVertex) 
graph.remove(tempVertex) 

}

我同意，图DS不利于这些类型的问题，但我的条件下，这个工程完美..干杯！

来源

2013-07-25 17:46:08 Jazib

我想你可能需要使用迭代器去除如果你正在使用LinkedHashSet。也就是说找到元素，然后继续移除，直到到达尾部。这将是O（n），但即使您编写了自己的LinkedHashSet（带有双向链接列表和哈希集），您也可以访问原始链接结构，以便可以切断O（1）中的链接列表，但是您仍然需要删除刚刚从HashSet中的链接列表中删除的所有元素，这是O（n）成本再次出现的位置。

因此，总之，删除元素，然后保持该元素的迭代器，并继续沿着删除元素走下去，直到到达结尾。我不确定LinkedHashSet是否暴露了所需的调用，但是你可以弄清楚。

来源

2013-04-08 22:49:41

+1 - 分析发现。这些元素必须单独从哈希表中删除，并且这使得O（N）...无论您如何处理“链接”或“排序”要求。 – 2013-04-08 22:55:03

其实我对O（n）没有问题，因为我的数据并不是那么大的担心。我面临的真正问题是LinkedHashSet没有实现get（index）函数。它也没有告诉我哪个是最后一个元素。所以，我不能像你说的那样真正地遍历列表。 – Jazib 2013-04-09 16:08:28

编写你自己的包装哈希集和链表数据结构的类可能是最容易的，这样你就可以准确地公开你想要在底层数据结构上使用什么方法。 – 2013-04-10 14:24:52

这里的基本问题是您必须维护两个数据结构，一个表示键/值映射的“映射”，另一个表示插入顺序的“列表”。

有“地图”和“列表”组织提供给定点后快速删除元素;例如排序的各种树以及基于数组和链表的列表（以查找点的成本为模）。

但是，似乎不可能从两个数据结构中移除N个元素的效果好于O(N)。您必须访问所有要移除的元素才能将其从第二个数据结构中移除。（实际上，我怀疑可以用数学证明......）

简而言之，没有数据结构比您当前使用的复杂性更好。

可以提高性能的区域（使用自定义集合类！）避免显式使用迭代器。使用迭代器和标准迭代器API，数据结构中的元素总数的成本为O(N)。如果哈希入口节点也具有序列的next/prev链接，那么您可以将此元素的数量设置为O(N)。

来源

2013-04-08 23:09:47

在这个例子中没有“地图”，只是值。这就是说，我同意你的分析，这可能是O（N）不管... – user949300 2013-04-08 23:41:52

@ user949300 - 真的...有点。但是，概念上有第二种数据结构。在标准HashSet实现中，该集合使用HashMap实现。见http://www.docjar.com/html/api/java/util/HashSet.java.html ...第102行。 – 2013-04-09 03:51:27

通过覆盖add()和addAll()，您可以编写自己的不允许重复的ArrayList版本。据我所知，没有“常见”的第三方版本，这一直让我感到惊讶。有人知道吗？

然后删除代码是非常简单的通过列表中的每个元素（不需要使用ListIterator）

int idx = this.indexOf("D"); 
if (idx >= 0) { 
    for (int goInReverse = this.size()-1; goInReverse > idx; goInReverse--) 
    this.remove(goInReverse); 
}

然而，这仍然是O（N），因为你循环。

来源

2013-04-08 23:40:25 user949300

你的意思是说我应该写自己的逻辑来停止重复？我可以做到这一点，但从学习的角度来看，如果不是这样，你可以详细说明在哪个场景中使用LinkedHashSet？ – Jazib 2013-04-09 16:11:51

不一定应该，但可以 - 根据发生的事情，ArrayList可以更高效。如果您需要维护添加项目的顺序，则LinkedHashSet很有用。我通常使用HashSet（不关心顺序）或TreeSet（使用自然顺序，例如元素的字母顺序）。 – user949300 2013-04-09 19:01:24

Java LinkedHashSet从末尾删除一些元素

回答

相关问题