有没有一个无重复元素的列表实现？

Question

我知道有关于 SortedSet 的内容，但在我的情况下，我需要实现 List 而不是 Set。所以是否存在一个在API中或其他地方的实现呢？

虽然我自己实现这个应该不难，但我想先问一下这里的人们。

- Yuval

---

为什么需要实现List？集合和列表一样可迭代，所以我想接收方法之所以强制使用List，是出于其他原因。 - Rob

@Rob 没错，这是一个外部需求，数据结构包含的不仅仅是一个列表。 - Yuval

如果用户需要一个列表，那么很明显需要的是列表接口中SET接口不存在的方法。 - marcolopes

Answer 1

在Java标准库中没有专门用于此目的的集合类。但是，LinkedHashSet<E> 可以保留元素添加顺序，类似于 List，因此，如果你将其包装在一个 List 中使用，则可以获得所需的语义。

另外，Commons Collections（或者通用版本的 commons-collections4）已经有了符合你要求的 List ：SetUniqueList / SetUniqueList<E>。

- Calum

---

Commons 类正是我所需要的，不过我的老板告诉我最终要自己来实现。无论如何还是非常感谢您！ - Yuval

啊，没什么比重新发明轮子更好的了！无论如何，如果需要再次出现，你现在就知道了。collections15是一个非常有用的东西；特别是MultiMaps可以减轻自己经常实现的某些东西的痛苦。 - Calum

@skaffman: 他其实不是个白痴，但有时候会做一些...嗯，奇怪的举动。无论如何，我不会在产品中引入漏洞。在今天的市场上，我对我的工作感到满意，不想关门而去并烧毁桥梁，如果你明白我的意思。 - Yuval

当SetUniqueList没有参数化类型时，我感到相当惊讶。 - emeraldhieu

在移动平台上，系统通常会删除未使用的类，但是当然，你可能不会选择其中任何一种“正常”的解决方案。总是需要做出一些权衡，并且没有一种解决方案能够解决所有情况。 - Calum

Answer 2

这是我做的，它可行。

假设我有一个ArrayList，我所做的第一件事是创建一个新的LinkedHashSet。

LinkedHashSet<E> hashSet = new LinkedHashSet<E>()

然后我尝试将我的新元素添加到LinkedHashSet中。如果新元素是重复的，add方法不会改变LinkedHasSet并返回false。这就成为了我在添加到ArrayList之前可以测试的一个条件。

if (hashSet.add(E)) arrayList.add(E);

这是一种简单而优雅的方法，用于防止重复项被添加到数组列表中。如果您愿意，可以将其封装在扩展 ArrayList 类的类的 add 方法中。只需记得通过循环遍历元素并调用add方法来处理 addAll 。

- user3570018

---

是的，我认为这是最好的解决方案，你也可以简单地使用普通的HashSet，而不是Linked，然后你可以按照自己的意愿使用列表，在某些情况下你也可以决定要做什么，比如在特定索引之前向列表中添加元素时，你可以决定是否将重复的项移动到该位置。 - gyurix

最佳解决方案在这里...我将发布我的UniqueList类代码。 - marcolopes

这对我在我的BFS图算法中起作用了。因为我有一些节点，只有当它们不在队列（LinkedList）中时才将它们添加到队列中。 - Jeancarlo Fontalvo

Answer 3

所以最终我做了什么，希望这能帮到其他人。

class NoDuplicatesList<E> extends LinkedList<E> {
    @Override
    public boolean add(E e) {
        if (this.contains(e)) {
            return false;
        }
        else {
            return super.add(e);
        }
    }

    @Override
    public boolean addAll(Collection<? extends E> collection) {
        Collection<E> copy = new LinkedList<E>(collection);
        copy.removeAll(this);
        return super.addAll(copy);
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> collection) {
        Collection<E> copy = new LinkedList<E>(collection);
        copy.removeAll(this);
        return super.addAll(index, copy);
    }

    @Override
    public void add(int index, E element) {
        if (this.contains(element)) {
            return;
        }
        else {
            super.add(index, element);
        }
    }
}   

- Yuval

---

注意 - LinkedList.contains() 方法需要遍历整个链表来确定一个对象是否包含在其中。这意味着当你将对象添加到一个大型链表时，每次添加操作都会扫描整个链表（在最坏情况下）。这可能会变得很慢。 - matt b

另外，您的addAll覆盖没有检查传递给addAll()的集合中是否存在重复项。 - matt b

@mattb，那么你会如何解决这个问题呢：在Android上，当将对象绑定到列表项视图时，我们会得到视图适配器中该项的位置。由于集合没有索引，因此使用列表时唯一的方法是迭代并查找现有副本以检查对象是否存在。 - TheRealChx101

这个解决方案的性能问题可以通过一个简单的附加Set<Integer>来解决，该集合存储元素的哈希码（而不是搜索整个列表）-当然，这需要所有元素正确实现hashCode()，但是使用像Lombok这样的辅助框架，这真的不是问题...实际上有点琐碎。 甚至可以使用红黑树优化该解决方案的哈希码...对于大量性能提升的小内存开销；欢迎来到云计算的世界;-) - specializt

Answer 4

为什么不用列表封装一个集合，像这样排序：

new ArrayList( new LinkedHashSet() )

这就留给真正精通集合的人去实现了；-)

- dhiller

---

这个构造函数会将Set的内容复制到新的List中，而不是简单地包装它。 - Calum

@Calum，你说得对，但是他不必担心将重复项添加到列表中，他可以将对象添加到Set中（让Set负责过滤重复项），并在传递给外部方法时将该Set包装在List中。 - matt b

这将一个集合复制到一个列表中，但你不会有任何已知的排序。但这正是问题的核心所在。 - Janning Vygen

Answer 5

你应该认真考虑dhiller的答案：

1. 不要担心将对象添加到不重复的List中，而是将它们添加到Set（任何实现），这样自然会过滤掉重复项。
2. 当需要调用需要List的方法时，请将其包装在new ArrayList(set)中（或者new LinkedList(set)，任选其一）。

我认为你发布的解决方案NoDuplicatesList存在一些问题，主要是contains()方法，此外你的类没有处理检查传递给addAll()方法的集合中是否有重复项。

- matt b

---

我很想了解这些contains()函数的问题。至于addAll()函数，我会创建给定集合的副本，并删除已经存在于“this”中的所有对象。那么这样不就处理了重复项吗？ - Yuval

正如我在您的课堂帖子中提到的评论中所述，contains() 方法必须扫描整个列表（在最坏的情况下）以查找对象是否包含在列表中。如果您有一个包含100万项的列表，并逐个添加10个项目，则（在最坏的情况下）将扫描超过一千万个项目。 - matt b

关于addAll()，如果传递给addAll的集合本身包含重复项，则不会检测到它们。例如：您的列表{A，B，C，D}参数列表{B，D，E，E，E}。您可以创建参数的副本，在removeAll之后它包含{E，E，E}。 - matt b

addAll() 的问题对我来说并不是很相关，因为在整个过程中我使用了 NoDuplicatesList，并且 addAll() 应该接收另一个 NoDuplicatesList 作为其参数。你有什么建议来提高 contains() 的性能？ - Yuval

Answer 6

我需要类似的功能，于是我去了commons collections并使用了SetUniqueList，但当我运行一些性能测试时，我发现与使用Set.toArray()方法获得一个Array相比，它似乎没有被优化。

相比其他实现方式，SetUniqueTest填充并遍历100,000个字符串所需的时间是20:1倍，这是一个很大的差别。

因此，如果您担心性能问题，我建议您使用Set和获取数组，而不是使用SetUniqueList，除非您真的需要SetUniqueList的逻辑，那么您将需要检查其他解决方案...

测试代码主方法：

public static void main(String[] args) {


SetUniqueList pq = SetUniqueList.decorate(new ArrayList());
Set s = new TreeSet();

long t1 = 0L;
long t2 = 0L;
String t;


t1 = System.nanoTime();
for (int i = 0; i < 200000; i++) {
    pq.add("a" + Math.random());
}
while (!pq.isEmpty()) {
    t = (String) pq.remove(0);
}
t1 = System.nanoTime() - t1;

t2 = System.nanoTime();
for (int i = 0; i < 200000; i++) {
    s.add("a" + Math.random());
}

s.clear();
String[] d = (String[]) s.toArray(new String[0]);
s.clear();
for (int i = 0; i < d.length; i++) {
    t = d[i];

}
t2 = System.nanoTime() - t2;

System.out.println((double)t1/1000/1000/1000); //seconds
System.out.println((double)t2/1000/1000/1000); //seconds
System.out.println(((double) t1) / t2);        //comparing results

敬礼， Mohammed Sleem

- Mohammed Sleem

Answer 7

我最新的实现：https://github.com/marcolopes/dma/blob/master/org.dma.java/src/org/dma/java/util/UniqueArrayList.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedHashSet;

/**
 * Extends <tt>ArrayList</tt> and guarantees no duplicate elements
 */
public class UniqueArrayList<T> extends ArrayList<T> {

    private static final long serialVersionUID = 1L;

    public UniqueArrayList(int initialCapacity) {
        super(initialCapacity);
    }

    public UniqueArrayList() {
        super();
    }

    public UniqueArrayList(T[] array) {
        this(Arrays.asList(array));
    }

    public UniqueArrayList(Collection<? extends T> col) {
        addAll(col);
    }


    @Override
    public void add(int index, T e) {
        if (!contains(e)) super.add(index, e);
    }

    @Override
    public boolean add(T e) {
        return contains(e) ? false : super.add(e);
    }

    @Override
    public boolean addAll(Collection<? extends T> col) {
        Collection set=new LinkedHashSet(this);
        set.addAll(col);
        clear();
        return super.addAll(set);
    }

    @Override
    public boolean addAll(int index, Collection<? extends T> col) {
        Collection set=new LinkedHashSet(subList(0, index));
        set.addAll(col);
        set.addAll(subList(index, size()));
        clear();
        return super.addAll(set);
    }

    @Override
    public T set(int index, T e) {
        return contains(e) ? null : super.set(index, e);
    }

    /** Ensures element.equals(o) */
    @Override
    public int indexOf(Object o) {
        int index=0;
        for(T element: this){
            if (element.equals(o)) return index;
            index++;
        }return -1;
    }


}

- marcolopes

Answer 8

集合接口文档中提到：

Set — 一个不能包含重复元素的集合。
List — 一个有序的集合（有时称为序列）。列表可以包含重复元素。

因此，如果您不想要重复项，则可能不应使用列表。

- Hauch

---

我特别提到我需要一个List实现。相信我，这是有原因的。 - Yuval

你遇到的问题是因为你正在与一个需要 List 作为参数（而不是 Collection）的 API 进行交互吗？这有点让人烦恼。 - matt b

实际上，该API接受一个Map<AccountType, Map<AccountType, List<Account>>>，这意味着在某个地方保存了数十到数百个列表... 哎。 - Yuval

使用元素-概率对构建概率函数时可能涉及到去重，尽管重复的元素可以合并。 - Al G Johnston

Answer 9

从我的记忆中，列表允许重复项。您可以快速实现一个UniqueArrayList并覆盖所有的add/insert函数，在调用继承方法之前检查contains()。对于个人使用，您只需实现您使用的add方法，并覆盖其他方法以防止未来的程序员以不同的方式使用列表而抛出异常。

- Kieveli

---

如果没有人提出更好的建议，我已经准备好回到这个想法（最终我不得不这样做）=8-)请参见我上面的答案。 - Yuval

Answer 10

这个怎么样？在添加之前，通过包含一个已经存在的对象来检查列表

while (searchResult != null && searchResult.hasMore()) {
    SearchResult nextElement = searchResult.nextElement();
    Attributes attributes = nextElement.getAttributes();

    String stringName = getAttributeStringValue(attributes, SearchAttribute.*attributeName*);
   
   if(!List.contains(stringName)){
    List.add(stringName);
   }
}

- GerNi

---

如果我们想要自己实现它，就不会询问。 - Eddie Jamsession