为什么我要使用 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 的 GetHashCode 和 Equals 被 From、To 和 Actor 覆盖，因此具有这些相同属性的两个实例具有相同的哈希值和相等性。

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

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

Dictionary<int, CachedPath> cachedPath

再次强调一下，如果我没记错的话，Dictionary 还提供了 O(1) 的插入、删除以及通过 Key 检索的功能。这让我认为字典是一个 HashSet + O(1) 元素检索能力。

我错过了什么吗？ Dictionary 真的比 HashSet 更好，因为它支持更多操作吗？

提前致谢。

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);

或者通过创建一个考虑所有三个项目的相等比较器，并使用

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

。

Answer 2

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

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

Answer 3

HashSet 似乎足以满足您需要做的事情：存储唯一路径并检查路径是否已存储并将其删除。

这是关于美学的：你的代码读起来就像是带有集合的数学证明，而不是操作字典的过程。

不要使用FirstOrDefault；只需使用 HashSet.Contains(p) 和 HashSet.Remove(p) ，其中“p”是 CachedPath 的新实例，具有您正在查找的属性。

我遇到了完全相同的问题，这就是我遇到这篇文章的原因。我的情况与您的情况类似，存储的项目需要通过多个属性有效地查找。然而，就我而言，存储的项目和用于搜索的项目并不相同；它们仅具有用作密钥的潜在相同属性组合，而其余属性则不同。

这就是为什么我需要一个字典和一个关于属性组合的自定义比较器。我需要存储的实际项目，因为它与我搜索时使用的项目不同。

但在您的情况下，如果一个缓存路径具有相同的属性，则它们与另一个缓存路径相同。这就是为什么您可以使用更简单的 HashSet。您不需要从 HashSet 中检索项目，因为您只需构造一个项目的新实例并使用它来检查哈希集是否已包含其等效项，并从哈希集中删除该等效项。