我正在向 a 添加一些值,LinkedHashSet
并且基于add()
方法的输出,即真/假,我正在执行其他操作。
如果Set
包含重复元素,则返回 false,在这种情况下,我想知道重复元素的索引,Set
因为我需要在其他地方使用该索引。Set
作为一个“链接”集合,必须有某种方法来获取索引,但我在/ LinkedHashSet
API中找不到任何这样的东西。
我正在向 a 添加一些值,LinkedHashSet
并且基于add()
方法的输出,即真/假,我正在执行其他操作。
如果Set
包含重复元素,则返回 false,在这种情况下,我想知道重复元素的索引,Set
因为我需要在其他地方使用该索引。Set
作为一个“链接”集合,必须有某种方法来获取索引,但我在/ LinkedHashSet
API中找不到任何这样的东西。
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
,为您提供可能的此类操作的最佳速度。