C# 2.0中HashSet的替代方案

Question

我在我的项目中使用了 List<T>，这个列表包含了数百个条目。我经常使用 List.Contains 方法，但是这会影响性能。我曾试图用字典来代替 List，但结果却出现了内存瓶颈，导致性能更加恶化。有没有更好的解决方案可以建议一下，以便在 List 中进行搜索？C# 2.0 中是否有 HashSet<T> 的替代品或者其他更好的方式，既能提高速度又能节省内存？

- FIre Panda

---

你想要做什么？列表有哪些限制条件？你没有提供建议所需的信息类型。 - Oded

我正在使用List<long>，而List.Contains的时间复杂度为O(N)，因此它会影响性能。 - FIre Panda

你的列表中保存了什么类型的数据？通常数百个条目并不算太多。但是，您没有解释您在列表中做什么。说“包含”毫无意义。 - Oded

foreach (Entity entity in _lstEntities) { if (entitiesExt.Contains(entity.EntityId)) continue; } Profiler 显示此代码总共花费了 437 秒。 - FIre Panda

你真的应该在问题中发布所有这些代码。 - Oded

Answer 1

可以使用 Dictionary<T,bool> 替代 HashSet<T>。无论您添加值为 True 还是 False 的项，都是随机的，该值不相关。

它比 HashSet<T> 更麻烦，不够轻量级，但肯定比 List<T> 好。

- Tergiver

---

OP说：“我用字典替换了列表，但导致了内存瓶颈问题。” - marsh-wiggle

Answer 2

public class HashCollection <T> : ICollection <T>
{
    private Dictionary<T, bool> _innerDictionary;

    public HashCollection()
    {
        _innerDictionary = new Dictionary<T, bool>();
    }

    void ICollection <T>.Add(T item)
    {
        AddInternal(item);
    }

    private void AddInternal(T item)
    {
        _innerDictionary.Add(item, false);
    }

    public bool Add(T item)
    {
        if (_innerDictionary.ContainsKey(item))
            return false;

        AddInternal(item);
        return true;
    }

    public void Clear()
    {
        _innerDictionary.Clear();
        _innerDictionary = new Dictionary<T, bool>();
    }

    public bool Contains(T item)
    {
        return _innerDictionary.ContainsKey(item);
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        _innerDictionary.Keys.CopyTo(array, arrayIndex);
    }

    public int Count
    {
        get { return _innerDictionary.Keys.Count; }
    }

    public bool IsReadOnly
    {
        get
        {
            return false;
        }
    }

    public bool Remove(T item)
    {
        return _innerDictionary.Remove(item);
    }

    public IEnumerator<T> GetEnumerator()
    {
        return _innerDictionary.Keys.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

- George Lica

Answer 3

如果您可以接受需要安装 .Net 3.5 框架的要求，您可以在 2.0 项目中使用来自 .Net 3.5 (System.Core.dll) 的 HashSet。

请参阅此问题：Using HashSet in C# 2.0, compatible with 3.5 如果不行，我会使用字典。

- jeroenh