为什么我要使用 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
                });

注意：class CachedPath 的 GetHashCode 和 Equals 仅被 From、To 和 Actor 覆盖，因此具有这些相同属性的两个实例具有相同的散列和相等性。

鉴于 'HashSet' 中的快速查找（包含）、插入和删除是 O(1)（如果我没记错的话），我考虑使用 'HashSet' 来执行这些操作.唯一的问题是 FirstOrDefault，我必须枚举整个集合才能得到它。

考虑到这个问题，我考虑过使用由 From、To 和 Actor 的散列索引的字典：

Dictionary<int, CachedPath> cachedPath

再说一次，如果我没记错的话，Dictionary 还提供 O(1) 的插入、删除和 Key 检索。这让我想到 Dictionary 是一个 HashSet + O(1) 元素检索能力。

我错过了什么吗？在支持更多操作的意义上，Dictionary 真的比 HashSet 更好吗？

提前致谢。

Answer 1

哈希集在执行添加时不会抛出异常。相反，它 returns 一个反映添加成功的布尔值。

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

Answer 2

Dictionary 并不比 HashSet 好，只是不同而已。

当你想存储一个无序的项目集合时，你使用 HashSet，
当您想要将一组名为 "keys" 的项目与另一组名为 "values"

Dictionary

人们可以将 HashSet 视为没有关联值的 Dictionary（事实上，HashSet 有时在幕后使用 Dictionary 来实现）但是没有必要这样想：把两者想成完全不同的东西也行。

在你的情况下，你可以通过按演员制作字典来潜在地提高性能，如下所示：

Dictionary<ActorType,List<CachedPath>> _cachedPathsByActor

这样你的线性搜索会根据演员快速选择子列表，然后按目标线性搜索：

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

或者通过制作一个考虑所有三个项目的相等比较器，并使用 Dictionary 和 CachedPath 作为键和值，并将自定义 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。

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

Why would I use a HashSet over a Dictionary?

c#

dictionary

hashset