-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% 的时间是错误的。

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

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

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