为什么我应该使用 HashSet 而不是 Dictionary？

Question

我正在尝试在A*算法中实现一个缓存路径列表。目前，缓存的路径被存储在一个类似于这样的列表中:

readonly List<CachedPath> _cachedPaths = new List<CachedPath>();

这个列表可以执行以下操作：

使用FirstOrDefault获取满足特定条件的元素

var cached = _cachedPaths.FirstOrDefault(p => p.From == from && p.To == target && p.Actor == self);

删除一个元素

_cachedPaths.Remove(cached);

新增内容

_cachedPaths.Add(new CachedPath {
                    From = from,
                    To = target,
                    Actor = self,
                    Result = pb,
                    Tick = _world.WorldTick
                });

注意：CachedPath类仅使用From，To和Actor重写了GetHashCode和Equals方法，因此具有这些相同属性的两个实例具有相同的哈希和相等性。

鉴于在“HashSet”中进行快速查找（Contains），插入和删除均为O（1）（如果我没有弄错的话），我考虑使用“HashSet”来执行这些操作。唯一的问题是FirstOrDefault，我不得不枚举整个集合来获取它。

考虑到这个问题，我还考虑使用由From，To和Actor的哈希索引的Dictionary：

Dictionary<int, CachedPath> cachedPath

再次强调，如果我没有理解错误的话，字典(Dictionary)在插入、删除和按键检索方面也提供了O(1)的性能。这让我认为字典是一个哈希集合(HashSet)加上O(1)元素检索功能。

我有遗漏什么吗？字典真的比哈希集合更好，因为它支持更多的操作吗？

提前感谢。

- David Jiménez Martínez

---

https://dev59.com/DXE85IYBdhLWcg3wikEu - Yuval Itzchakov

Answer 1

Dictionary并不比HashSet更好，它们只是不同的。

• 当您想要存储无序项目集合时，请使用HashSet,
• 当您想要将一组称为“键”的项目与另一组称为“值”的项目相关联时，请使用Dictionary

人们可以把HashSet看作没有相关值的Dictionary（实际上，有时会在HashSet背后使用Dictionary进行实现），但完全将两者视为完全不同的东西也可以。

在您的情况下，您可以通过按演员创建字典来提高性能，如下所示：

Dictionary<ActorType,List<CachedPath>> _cachedPathsByActor

通过这种方式，您的线性搜索会基于一个演员快速选择一个子列表，然后按目标进行线性搜索：

var cached = _cachedPathsByActor[self].FirstOrDefault(p => p.From == from && p.To == target);

或者通过创建一个考虑所有三个项的相等比较器，并使用将 CachedPath 作为键和值的 Dictionary，以及该自定义的IEqualityComparer<T>作为键比较器：

class CachedPathEqualityComparer : IEqualityComparer<CachedPath> {
    public bool Equals(CachedPath a, CachedPath b) {
        return a.Actor == b.Actor
            && a.From == b.From
            && a.To == b.To;
    }
    public int GetHashCode(CachedPath p) {
        return 31*31*p.Actor.GetHashCode()+31*p.From.GetHashCode()+p.To.GetHashCode();
    }
}
...
var _cachedPaths = new Dictionary<CachedPath,CachedPath>(new CachedPathEqualityComparer());
...
CachedPath cached;
if (_cachedPaths.TryGetValue(self, out cached)) {
    ...
}

然而，这种方法假设在字典中具有相同 From、To 和 Actor 的条目最多只会有一个。

- Sergey Kalinichenko

---

那么，对于这种情况，使用Actor.GetHashcode() + From.GetHashCode() + To.GetHashCode()作为键，而不仅仅是Actor，会更快吗？ - David Jiménez Martínez

Answer 2

在进行添加操作时，哈希集合（hashset）不会抛出异常。相反，它返回一个反映添加成功与否的布尔值。

此外，哈希集合不需要键值对。我使用哈希集合来保证一组唯一的值。

- Scott Nimrod