Is hashcode comparison necessary in DefaultFrozenDictionary GetValueRefOrNullRefCore?

[Artromskiy]

Description

I looked at the code of frozen dictionaries. In the DefaultFrozenDictionary class, when we receive a reference to an object, we get the first/last indexes of the keys from the FrozenHashTable. Should the keys for these indexes have the same hash codes? If yes, then additional comparison of hash codes in the frozen dictionary is not necessary. This also applies to ValueTypeDefaultComparerFrozenDictionary and probably other implementations.

Code

        private protected override ref readonly TValue GetValueRefOrNullRefCore(TKey key)
        {
            IEqualityComparer<TKey> comparer = Comparer;

            int hashCode = comparer.GetHashCode(key);
            _hashTable.FindMatchingEntries(hashCode, out int index, out int endIndex);

            while (index <= endIndex)
            {
                // THIS CHECK CAN BE ELIMINATED
                if (hashCode == _hashTable.HashCodes[index])
                {
                    if (comparer.Equals(key, _keys[index]))
                    {
                        return ref _values[index];
                    }
                }

                index++;
            }

            return ref Unsafe.NullRef<TValue>();
        }

Links

https://github.com/dotnet/runtime/blob/main/src/libraries/System.Collections.Immutable/src/System/Collections/Frozen/DefaultFrozenDictionary.cs

https://github.com/dotnet/runtime/blob/main/src/libraries/System.Collections.Immutable/src/System/Collections/Frozen/ValueTypeDefaultComparerFrozenDictionary.cs

[dotnet-policy-service[bot]]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

[stephentoub]

While the implementation tries to reduce the number of collisions when mapping hash tables to buckets, it doesn't guarantee a 1:1 ratio. As such, the same bucket can contain entries with different hash codes. And as it's generally much cheaper to compare an int than to do the equality comparison for a key, eliminating the hash code can show up as a regression. It's there to prevent that.