C# 如何避免列表中的重复项？

Question

我可以使用什么方法来避免列表中出现重复项？

一种方法是当我添加一个新项目时，首先检查该元素是否存在，但这让我使用更多代码并迭代所有列表以检查它是否存在。

我可以使用哈希集的另一种方式，如果我尝试添加一个新项目，它自己会检查该项目是否存在，如果不存在，它将添加新项目，如果存在，则什么也不做。

但是我知道 hashset 效率较低，需要比列表更多的资源，所以我不知道使用 hashset 来避免重复是否是 hashset 的一个很好的用途。

还有其他选择吗？

谢谢。

Answer 1

您可以在一行代码中实现：-

List<long> longs = new List<long> { 1, 2, 3, 4, 3, 2, 5 };

List<long> unique = longs.Distinct().ToList();

unique 将只包含 1,2,3,4,5

Answer 2

A List 是一个可能包含重复项的数据结构。重复元素由它们的索引消除歧义。

One way is when I will add a new item, check first if the element exists, but this make me use more code and iterate all the list to check if it exists.

这是可能的，但容易出错且速度慢。每次要添加元素时都需要遍历整个列表。您也有可能忘记检查代码中的某处。

Another way I could use a hashset, that if I try to add a new item, itself check if the item exists, if not, it will add the new item, if exists, then do nothing.

这是首选方式。最好使用标准库来强制执行您想要的约束。

But I know that the hashset is less efficient, need more resources than a list, so I don't know if using a hashset to avoid duplicates it is a good use of the hashset.

效率取决于你想做什么；参见。

There are any other alternative?

您可以使用 List 实现您自己的 ISet。这会使插入速度变慢（您需要迭代整个集合），但您将获得 O(1) 随机访问。

Answer 3

哈希集是检查项目是否存在的最佳方式，因为它的复杂度为 O(1)。

因此您可以将项目同时插入列表和哈希集中在插入新项目之前，您检查它是否存在于哈希集中。

Answer 4

您无法避免 List 中的重复项。没办法-没有验证项目。

如果您不介意项目的顺序 - 使用 HashSet。

如果你想保留项目的顺序（实际上有一点歧义——项目应该出现在第一次添加的索引处还是最后一次添加的索引处）。但是你想确保所有的项目都是唯一的，那么你应该写你自己的Listclass。 IE。实现 IList<T> 接口的东西：

public class ListWithoutDuplicates<T> : IList<T>

你在这里有不同的选择。例如。你应该决定什么对你更重要 - 快速添加或内存消耗。因为为了快速添加和包含操作，您应该使用一些基于散列的数据结构。这是无序的。下面是使用 HashSet 的示例实现，用于存储存储在内部列表中的所有项目的哈希值。您将需要以下字段：

private readonly HashSet<int> hashes = new HashSet<int>();
private readonly List<T> items = new List<T>();
private static readonly Comparer<T> comparer = Comparer<T>.Default;

添加项目很简单（警告：此处及以后没有空值检查）- 使用项目哈希码快速 O(1) 检查它是否已添加。使用相同的方法删除项目：

public void Add(T item)
{
    var hash = item.GetHashCode();
    if (hashes.Contains(hash))
        return;

    hashes.Add(hash);
    items.Add(item);
}

public bool Remove(T item)
{
    var hash = item.GetHashCode();
    if (!hashes.Contains(hash))
        return false;

    hashes.Remove(item.GetHashCode());
    return items.Remove(item);
}

一些基于索引的操作：

public int IndexOf(T item)
{
    var hash = item.GetHashCode();
    if (!hashes.Contains(hash))
        return -1;

    return items.IndexOf(item);
}

public void Insert(int index, T item)
{
    var itemAtIndex = items[index];
    if (comparer.Compare(item, itemAtIndex) == 0)
        return;

    var hash = item.GetHashCode();

    if (!hashes.Contains(hash))
    {
        hashes.Remove(itemAtIndex.GetHashCode());
        items[index] = item;
        hashes.Add(hash);
        return;
    }

    throw new ArgumentException("Cannot add duplicate item");
}

public void RemoveAt(int index)
{
    var item = items[index];
    hashes.Remove(item.GetHashCode());
    items.RemoveAt(index);
}

还有剩菜：

public T this[int index]
{
    get { return items[index]; }
    set { Insert(index, value); }
}

public int Count => items.Count;
public bool Contains(T item) => hashes.Contains(item.GetHashCode());
public IEnumerator<T> GetEnumerator() => items.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => items.GetEnumerator();

就是这样。现在你有了列表实现，它只会添加一次项目（第一次）。例如

var list = new ListWithoutDuplicates<int> { 1, 2, 1, 3, 5, 2, 5, 3, 4 };

将创建包含项目 1、2、3、5、4 的列表。注意：如果内存消耗比性能更重要，那么不要使用哈希，而是使用 O(n) 的 items.Contains 操作。

顺便说一句，我们刚才做的实际上是一个 IList Decorator

C# 如何避免列表中的重复项？

C# how to avoid duplicates in a list?

c#

list

hashset