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?

Remember from recent posts that we’ve decided that two queues are equal if they return the same items in the same sequence and have the same prioritization rule.

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?

## Comments

blog comments powered by Disqus