为什么我会在字典上使用HashSet？

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'中的插入和删除是O(1)(如果我没有记错),我考虑使用'HashSet'来执行这些操作.唯一的问题是FirstOrDefault,我必须枚举整个集合才能得到它.

鉴于此问题,我还考虑使用由From,To和Actor的哈希索引的Dictionary:

Dictionary<int, CachedPath> cachedPath

再一次,如果我没有弄错的话,Dictionary还提供O(1)插入,删除和Key检索.这使我认为Dictionary是HashSet + O(1)元素检索功能.

我错过了什么吗？在它支持更多操作的意义上,字典真的比HashSet好吗？

提前致谢.

Answer 1

Dictionary是不是更好的比HashSet,它只是不同.

• HashSet当你想要存储无序的项目集合时,你可以使用
• Dictionary当您想要将一组称为"键"的项与另一组称为"值"的项目关联时,您可以使用

人们可以想到的HashSet作为Dictionary与不相关的值(事实上,HashSet使用有时执行Dictionary幕后),但想想这样没有必要:这两个是完全不同的事情的思维工作正常,太.

在您的情况下,您可以通过按actor创建字典来提高性能,如下所示:

Dictionary<ActorType,List<CachedPath>> _cachedPathsByActor

这样,线性搜索会快速选择基于actor的子列表,然后按目标线性搜索:

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

或者通过创建一个考虑所有三个项目的相等比较器,并使用Dictionarywith 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.

Answer 2

执行添加时,哈希集不会引发异常.相反,它返回一个反映add成功的bool.

此外,散列集不需要keyValue对.我使用hashsets来保证一组唯一值.