A HashSet<T> stores unique values and makes membership tests efficient by hashing each value into buckets. For a string of length m, hashing costs O(m), largely independent of the number of stored values. section 5.1.1
Its strengths and limits become clear when searching a large word list:
- Use it for Contains-style membership tests, where hash-based lookup is effective. section 5.1.1
- Do not use it for StartsWith searches: hashing deliberately distributes dissimilar words, providing no efficient prefix-search path. section 5.1.1
- Treat equality and hashing as a pair: equivalent values must produce equal hash codes. section 5.4.2
Mutable values can disappear
If a mutable object is stored in a hash set and later changed in a way that changes its hash code, the set may no longer find it. Immutable values, or carefully controlled mutation, preserve the lookup invariant. section 5.4.2
Listing 5.6 Computing Node equivalence with an equality comparer
sealed class DawgBuilder
{
private class NodeEquality : IEqualityComparer<Node>
{
public bool Equals(Node? x, Node? y)
{
if (ReferenceEquals(x, y))
return true;
if (ReferenceEquals(x, null) || ReferenceEquals(y, null))
return false;
if (x.IsEnd != y.IsEnd || x.Count != y.Count)
return false;
return x.EdgeLabels.All(e =>
y.HasEdge(e) &&
ReferenceEquals(x.FollowEdge(e), y.FollowEdge(e)));
}
Inspect the C# equality comparer pattern used for structurally equivalent nodes, including reference checks, null handling, and edge comparison. section 5.4.2
