为什么我会在字典上使用哈希集

Question

我正在尝试在 A* 算法上实现缓存路径列表。目前，缓存的路径存储在如下所示的列表中：

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

在此列表中执行的操作包括：

First或默认值，以获取满足特定条件的元素

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"

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

鉴于这个问题，我还考虑使用由 From、To 和 actor 的哈希索引的字典：

Dictionary<int, CachedPath> cachedPath

再一次，如果我没记错的话，字典还在插入、删除和按键检索中提供了 O（1）。这让我认为字典是一种 HashSet + O（1） 元素检索功能。

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

提前谢谢。

Answer 1

>Dictionary并不比HashSet好，只是不同。

• 当您想要存储无序的项目集合时，可以使用HashSet，并且
• 如果要将一组名为"键"的项与另一组名为"值"的项相关联，可以使用Dictionary

人们可以将HashSet视为没有关联值的Dictionary（事实上，HashSet有时是在幕后使用Dictionary实现的），但没有必要以这种方式考虑它：将两者视为完全不同的事物也可以正常工作。

在您的情况下，您可以通过按 actor 制作字典来提高性能，如下所示：

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。

Answer 2

执行添加时，哈希集不会引发异常。相反，它返回一个反映添加成功的布尔值。

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