-1

我正在向 a 添加一些值，LinkedHashSet并且基于add()方法的输出，即真/假，我正在执行其他操作。

如果Set包含重复元素，则返回 false，在这种情况下，我想知道重复元素的索引，Set因为我需要在其他地方使用该索引。Set作为一个“链接”集合，必须有某种方法来获取索引，但我在/ LinkedHashSetAPI中找不到任何这样的东西。

4

1 回答 1

2

LinkedHashSet本身没有明确索引。如果您需要索引，Set则对此类应用程序使用 a 通常表示错误的抽象和/或糟糕的编程。LinkedHashSet仅保证您可预测的迭代顺序，而不是正确的元素索引。在这种情况下，您应该使用 a List，因为这是为您提供索引保证的接口。但是，您可以使用几种方法推断索引，例如（不推荐，请注意）：

a) 在集合中使用索引迭代（例如使用for循环），寻找重复项并在找到时中断；获取索引的复杂度为 O(n)，

Object o; // this is the object you want to add to collection
if ( !linkedHashSet.add(o) ) {
    int index = 0;
    for( Object obj : linkedHashSet ) {
        if ( obj == o ) // or obj.equals(o), depending on your code's semantics
            return index;
        index++;
    }
}

b) 使用.toArray()并查找数组中的元素，例如通过

Object o; // this is the object you want to add to collection
int index;
if ( !linkedHashSet.add(o) )
    index = Arrays.asList(linkedHashSet.toArray()).indexOf(o);

再次，获取索引的 O(n) 复杂度。

两者都会导致严重的运行时损失（第二种解决方案在效率方面显然更差，因为它每次查找索引时都会创建一个数组；创建一个镜像该集合的并行数组会更好）。总而言之，我在您的示例中看到了一个破碎的抽象。你说

我需要在其他地方使用该索引

...如果真的是这样，那么使用Set本身就有 99% 的时间是错误的。

另一方面，您可以使用Map（HashMap例如），其中包含一个[index,Object]（或[Object,index]，取决于确切的用例）对。它需要一些重构，但它是 IMO 执行此操作的首选方式。对于大多数操作，它会为您提供与 相同的复杂性顺序LinkedHashSet，但是您将获得 O(1) 来获得基本上免费的索引（Java无论如何在内部HashSet使用HashMap，因此您不会通过替换为 丢失任何内存HashSet）HashMap。

更好的方法是使用显式处理整数映射的类 - 请参阅HashMap 和 int 作为键以获取更多信息；tl;dr - http://trove.starlight-systems.com/有TIntObjectHashMap& TObjectIntHashMap，为您提供可能的此类操作的最佳速度。

于 2015-08-08T12:52:50.483 回答