Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Consecutive hashes create conflicts #21

Closed
ENikS opened this issue May 8, 2023 · 0 comments · Fixed by #22
Closed

Consecutive hashes create conflicts #21

ENikS opened this issue May 8, 2023 · 0 comments · Fixed by #22

Comments

@ENikS
Copy link
Contributor

ENikS commented May 8, 2023

Method hash(...) gets the hash code from the key and applies bitmask to prevent zero hash code. It ORs the actual hashcode with 0b1100_0000_0000_0001

        protected virtual int hash(TKey key)
        {
            Debug.Assert(!(key is null));

            int h = _keyComparer.GetHashCode(key);

            // ensure that hash never matches 0, TOMBPRIMEHASH, ZEROHASH or REGULAR_HASH_BITS
            return h | (SPECIAL_HASH_BITS | 1);
        }

The problem is if two objects have two consecutive hash codes, they will end up with the same hash:

0xXXX0 -> 0xXXX1
0xXXX1 -> 0xXXX1
0xXXX2 -> 0xXXX3
0xXXX3 -> 0xXXX3
0xXXX4 -> 0xXXX5
0xXXX5 -> 0xXXX5
0xXXX6 -> 0xXXX7
0xXXX7 -> 0xXXX7
etc.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant