HashSet 相对于 ArrayList 的优势，反之亦然

Question

我对Java中的数据结构有疑问。在解决 Java 中的典型散列问题时，我使用了 HashSet 数据结构，在存在重复对象（对象内容）之前它工作正常。由于 HashSet 不支持插入重复项，因此我的逻辑失败了。

我用典型的 Arraylist 替换了哈希集，因为哈希集的方法如 .add(), .contains(), .remove() 两者都支持，然后我的逻辑工作得很好。

但这是否必然意味着当涉及重复项时，ArrayList 是比 Hashset 更合乎逻辑的选择？ Hashset 应该比 ArrayList 有一些时间复杂度优势吧？有人可以就此提供一些见解吗？

编辑：当涉及重复项时，当您想进行散列时，理想的数据结构是什么。我的意思是何时不应忽略重复项并应将其插入。

Answer 1

当您使用 HashMap 时，它会用新的副本替换原始值。
当您使用 HashSet 时，后续的重复项将被忽略（不插入）。
当您使用 ArrayList 时，它只是将副本添加到列表的末尾

这完全取决于您的需求。

Answer 2

如果您不想重复，

ArrayList 不是合乎逻辑的选择。针对不同用例的不同工具。

您可以在重复没有意义的区域使用 Set，例如一组学生。 A List 允许重复。

Answer 3

不清楚您所说的“散列问题”是什么意思，但也许您正在寻找 multiset。来自 Guava 文档：

A collection that supports order-independent equality, like Set, but may have duplicate elements. A multiset is also sometimes called a bag.

Elements of a multiset that are equal to one another are referred to as occurrences of the same single element. The total number of occurrences of an element in a multiset is called the count of that element (the terms "frequency" and "multiplicity" are equivalent, but not used in this API).

JDK 中不存在这样的东西。

Answer 4

如果您特别需要 HashSet 来处理重复项，HashMap 就可以胜任。如果您只需要计算添加的对象数量（使用 quick lookup/etc），HashMap<T,Integer> 将是理想的，其中 T 是对象的类型。如果您确实需要保留对已添加的重复对象的引用，请使用 HashMap<T, List<T>>。这样您就可以使用 HashMap 的 .containsKey(T t) 进行查找，并遍历结果列表中所有类似的散列对象。因此，例如，您可以创建此 class:

public class HashSetWithDuplicates<T> {

    private HashMap<T, List<T>> entries;
    private int size;

    public HashSetWithDuplicates(){
        entries = new HashMap<>();
        size = 0;
    }

    public HashSetWithDuplicates(Collection<? extends T> col){
        this();
        for(T t : col){
            add(t);
        }
    }

    public boolean contains(T t){
        return entries.containsKey(t);
    }

    public List<T> get(T t){
        return entries.get(t);
    }

    public void add(T t){
        if (!contains(t)) entries.put(t, new ArrayList<>());

        entries.get(t).add(t);
        size++;
    }

    public void remove(T t){
        if (!contains(t)) return;
        entries.get(t).remove(t);
        if(entries.get(t).isEmpty()) entries.remove(t);
        size--;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size() == 0;
    }
}

根据您的需要添加功能。

HashSet 相对于 ArrayList 的优势，反之亦然

Adavantages of HashSet over ArrayList and vice versa

java

arraylist

hashset