A hash value is an integer computed from data so a hash set or dictionary can place that data into a bucket and find it efficiently. For a string, hashing processes its characters; lookup then depends on the hashing work rather than the number of stored items. This helps Contains, but not StartsWith, because hashing deliberately distributes dissimilar words instead of preserving useful prefixes. section 5.1.1
Hashing becomes part of equality design when an object is used in a hash set or as a dictionary key. Equivalent objects must have equal hash values, although equal hash values do not prove equivalence. Any mutation that changes a stored object's hash value can make that object unfindable. section 5.4.2
When combining several fields into a hash value:
- Include the data used to decide equivalence. section 5.4.2
- Preserve the order in which fields are added; changing that order changes the result. section 5.4.2
- Do not assume every equivalence input is necessary: Count may participate in equivalence without appearing in the hash, provided equivalent nodes still hash equally. section 5.4.2
- Use C#'s HashCode helper when combining multiple pieces of data is error-prone. section 5.4.2
Hashing equivalent graph nodes
A node comparer adds the node's end marker, then each edge label and the node reached by that edge, ordering edge labels first. The resulting hash supports equivalence checks for mutable directed acyclic word-graph nodes. section 5.4.2
Listing 5.7 Finishing the Node equality comparer
public int GetHashCode(Node n)
{
var h = new HashCode();
h.Add(n.IsEnd);
foreach(var e in n.EdgeLabels.OrderBy(c=>c))
{
h.Add(e);
h.Add(n.FollowEdge(e)); #1
}
return h.ToHashCode();
}
}
Inspect the C# GetHashCode implementation that combines node properties and ordered edges. section 5.4.2
