Generating a hash code for an immutable priority queue introduces an unusual challenge: How do we generate a consistent hash code regardless of the order items are added to the queue?
One approach to implementation would be to iterate through the queue, calculating the hash code by combining the hash codes of our contained items in sequence. This would be very heavyweight, so we’d need to cache the value once calculated. With a little allowance to ensure we weight values at the same priority equally, the code would look like this:
The problem with this approach is that hash codes are supposed to be lightweight, and this is most definitely not.
As an alternative, we could calculate the hash code up front, in our constructor. The challenge with this is that we need to ensure that our calculation gives the same result regardless of the order items are enqueued. This limits us to just a few choices of operation - addition, multiplication and exclusive-or.
To illustrate, let’s just calculate our hash codes by summing up the items in our queue. For our
DualItemImmutablePriorityQueue<T> implementation, we add a new member, some code in the constructor to initialize the member, and override
GetHashCode() to return the precalculated value:
We avoid the possibility of a
NullReferenceException by protecting the call to
Head.GetHashCode() with the elvis operator.
The implementation for
BranchingImmutablePriorityQueue<T> is very similar:
On reflection, I’m not sure which of these two approaches is superior. Calculating the hash code up front is likely more performant, but the quality of the result might not be particularly high. Iterating through the entire queue to calculate the hash code will return a much higher quality result, but the cost of calculation may be excessive.
What do you think?