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

Question

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

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

我可以使用哈希集的另一种方法，如果我尝试添加一个新项目，它本身会检查该项目是否存在，如果不存在，它将添加新项目，如果存在，则不执行任何操作。

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

还有其他选择吗？

谢谢。

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

您无法避免List中出现重复。没办法——没有物品验证。

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

如果您想保留项目的顺序（实际上有一点歧义 - 项目应该出现在第一个添加的索引处还是最后一个添加的索引处）。但是您想确保所有项目都是唯一的，那么您应该编写自己的 List 类。 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 的列表。注意：如果内存消耗比性能更重要，则不要使用哈希，而是使用

items.Contains

操作，该操作的时间复杂度为 O(n)。

BTW 我们刚才所做的实际上是一个 IList Decorator

Answer 3

A

List

是一种可能包含重复项的数据结构。重复元素通过其索引消除歧义。

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

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

我可以使用哈希集的另一种方法，如果我尝试添加一个新项目，它本身会检查该项目是否存在，如果不存在，它将添加新项目，如果存在，则不执行任何操作。

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

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

效率取决于你想做什么；请参阅https://stackoverflow.com/a/23949528/1256041。

还有其他选择吗？

您可以使用

ISet

实现您自己的

List

。这会使插入速度变慢（您需要迭代整个集合），但您将获得

O(1)

随机访问。

Answer 4

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

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

Answer 5

如果您有一个

datatable ldtbResult

并且它包含如下值：

EMPLOYER_PAYMENT_PLAN_HEADER_ID |EMPLOYER_ACCOUNT_ID|PLAN_TYPE_VALUE |  STATUS_VALUE
538                             |     360915        |     STND       |   PAID
538                             |     360915        |     STND       |   PAID
538                                   360915              STND           PEND

并且在一个集合中，您希望拥有这样的行

datatable

，这样任何两行都不应该具有相同的主键值，即本例中的

employer_payment_plan_header_id(PK column)

。然后这是代码，

//下一行将数据表ldtbResult的值分配给集合

//rpEmployerPaymentPlanList

lprmPaymentPlanUtility.rpEmployerPaymentPlanList = GetCollection(ldtbResult, "icdoEmployerPaymentPlanHeader");

//下面的行确保没有 2 行具有相同的雇主_付款计划_标题_id（PK 字段）值：

            List<busEmployerPaymentPlanHeader> distinctPaymentPlans = lprmPaymentPlanUtility.rpEmployerPaymentPlanList
                                             .GroupBy(x => x.icdoEmployerPaymentPlanHeader.employer_payment_plan_header_id)
                                             .Select(group => group.First())
                                             .ToList();

//下面一行是返回原始集合的列表的值 //rpEmployerPaymentPlanList

            lprmPaymentPlanUtility.rpEmployerPaymentPlanList = new Collection<busEmployerPaymentPlanHeader>(distinctPaymentPlans);