GetHashCode for multiple boolean values

Question

In the following StackOverflow question Jon Skeets answer specifies one good implementation is ...

// Note: Not quite FNV!
public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = (int) 2166136261;
        // Suitable nullity checks etc, of course :)
        hash = (hash * 16777619) ^ bool1.GetHashCode();
        hash = (hash * 16777619) ^ bool2.GetHashCode();
        return hash;
    }
}

What if the two fields are both bools. Would this still be a good implementation or would this be overkill? If this is overkill what is the recommended approach for implementing GetHashCode when all fields are bool types?

In my case I am only comparing two bools.

How many boolean fields do you have? Say, more than thirty or less than thirty? — Sergey Kalinichenko, Mar 27 '17 at 17:50
It still works quite well. I suppose you can turn the set of booleans to a bit field, which maps well when there are less than 32 (one fore each bit in an `int`). However, the complexity/speed trade-offs would be a wash either way. — Berin Loritsch, Mar 27 '17 at 17:55
@dasblinkenlight two Booleans, modified question to reflect this. — Gene S, Mar 27 '17 at 18:23

Sergey Kalinichenko · Accepted Answer · 2017-03-27T19:16:24.787

7

When you have fewer than thirty bool fields you can implement a perfect hashing scheme by treating each bool as a single bit in the value of hash code. By "perfect" I mean that hash equality would be equivalent to actual equality (as opposed to "ordinary" hashing schemes, in which actual equality implies hash equality, but not vice versa).

The code would look like this:

public override int GetHashCode() {
    var hash = 0;
    if (field1)
        hash |= 1<<0;
    if (field2)
        hash |= 1<<1;
    if (field3)
        hash |= 1<<2;
    if (field4)
        hash |= 1<<3;
    return hash;
}

edited Mar 27 '17 at 19:16

answered Mar 27 '17 at 17:54

Sergey Kalinichenko

714,442
84
1,110
1,523

4

You said "caching schemes" twice in the answer did you mean to say "hashing schemes"? – Scott Chamberlain Mar 27 '17 at 18:18
Why fewer than 30 fields? Surely the limitation is 32. – Kyle Mar 27 '17 at 18:40
2

@Kyle 31 actually. Many implmentations that use the hash code (for example [in HashSet](https://referencesource.microsoft.com/#System.Core/System/Collections/Generic/HashSet.cs,3000888850fdc510)) only use the lower 31 bits and ignore the sign bit. They do this because they use negative values as sentinel values to represent uninitialized data. – Scott Chamberlain Mar 27 '17 at 18:42
@ScottChamberlain Ah, you are right, of course it's hashing! Thank you very much! – Sergey Kalinichenko Mar 27 '17 at 19:18

GetHashCode for multiple boolean values

1 Answers1