[API Proposal]: string.GetHashCodeNonRandomized

[stephentoub]

Background and motivation

In .NET Core, string hash codes are always randomized. This is critical to avoid certain kinds of attacks when adding arbitrary, untrusted inputs into types like Dictionary<,> and HashSet<>. However, for situations where the inputs are trusted, the overhead of these randomized hash codes makes them measurably more expensive than their non-randomized counterparts. As such, Dictionary<,> and HashSet<> both start out with non-randomized hash codes and only upgrade to randomized ones when enough collisions are detected. Such a capability is valuable for other collection types as well, but the raw primitives (the non-randomized hash code implementations) aren't trivial to implement efficiently and aren't exposed.

API Proposal

namespace System
{
    public sealed class String
    {
        public static int GetHashCode(ReadOnlySpan<char> value);
        public static int GetHashCode(ReadOnlySpan<char> value, StringComparison comparisonType);

+       public static int GetHashCodeNonRandomized(ReadOnlySpan<char> value);
+       public static int GetHashCodeNonRandomized(ReadOnlySpan<char> value, StringComparison comparisonType);
    }
}

API Usage

int hashcode = string.GetHashCodeNonRandomized(value, StringComparison.OrdinalIgnoreCase);

Alternative Designs

We could instead or in addition expose StringComparer singletons:

namespace System
{
    public abstract class StringComparer
    {
        public static StringComparer Ordinal { get; }
        public static StringComparer OrdinalIgnoreCase { get; }

+       public static StringComparer OrdinalNonRandomized { get; }
+       public static StringComparer OrdinalIgnoreCaseNonRandomized { get; }
    }
}

If we did that instead of the proposed APIs, we should also consider adding Equals/GetHashCode overloads for ReadOnlySpan<char> to StringComparer (something we might want to do anyway as part of https://github.com/dotnet/runtime/issues/27229).

Risks

A risk could be developers defaulting to using these instead of the randomized implementations in situations where the randomized implementations are warranted. However, some developers are already writing their own hash implementations to avoid the randomized overhead, and their implementations may be worse or less efficient than what's already in the box.

[stephentoub]

cc: @GrabYourPitchforks, @bartonjs, @terrajobst

[ghost]

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

Issue Details

---

### Background and motivation In .NET Core, string hash codes are always randomized. This is critical to avoid certain kinds of attacks when adding arbitrary, untrusted inputs into types like `Dictionary<,>` and `HashSet<>`. However, for situations where the inputs are trusted, the overhead of these randomized hash codes makes them measurably more expensive than their non-randomized counterparts. As such, `Dictionary<,>` and `HashSet<>` both start out with non-randomized hash codes and only upgrade to randomized ones when enough collisions are detected. Such a capability is valuable for other collection types as well, but the raw primitives (the non-randomized hash code implementations) aren't trivial to implement efficiently and aren't exposed. ### API Proposal ```diff namespace System { public sealed class String { public static int GetHashCode(ReadOnlySpan value); public static int GetHashCode(ReadOnlySpan value, StringComparison comparisonType); + public static int GetHashCodeNonRandomized(ReadOnlySpan value); + public static int GetHashCodeNonRandomized(ReadOnlySpan value, StringComparison comparisonType); } } ``` ### API Usage ```csharp int hashcode = string.GetHashCodeNonRandomized(value, StringComparison.OrdinalIgnoreCase); ``` ### Alternative Designs We could instead or in addition expose `StringComparer` singletons: ```diff namespace System { public abstract class StringComparer { public static StringComparer Ordinal { get; } public static StringComparer OrdinalIgnoreCase { get; } + public static StringComparer OrdinalNonRandomized { get; } + public static StringComparer OrdinalIgnoreCaseNonRandomized { get; } } } ``` If we did that instead of the proposed APIs, we should also consider adding `Equals`/`GetHashCode` overloads for `ReadOnlySpan` to `StringComparer` (something we might want to do anyway as part of https://github.com/dotnet/runtime/issues/27229). ### Risks A risk could be developers defaulting to using these instead of the randomized implementations in situations where the randomized implementations are warranted. However, some developers are already writing their own hash implementations to avoid the randomized overhead, and their implementations may be worse or less efficient than what's already in the box.

Author:	stephentoub
Assignees:	-
Labels:	`api-suggestion`, `area-System.Runtime`
Milestone:	8.0.0

[bartonjs]

I'd rather see it as new StringComparers. It doesn't seem to me to be a universal enough need on every String to be worthy of an instance method.

[stephentoub]

It doesn't seem to me to be a universal enough need on every String to be worthy of an instance method.

The proposal has them as a static methods, not instance.

(Also as noted, we'd need support for ReadOnlySpan<char> inputs, so as just a StringComparer, we'd need to either augment StringComparer to also supports spans, or expose separate span-based methods as well.)

[Nuklon]

GetNonRandomizedHashCode instead? GetHashCodeNonRandomized is some odd English.

[GSPP]

From reading the source code, it seems that the randomized comparer calls an entirely different algorithm. Can you educate me on why that is? Why does it not call the same algorithm just with a different seed?

https://github.com/dotnet/runtime/blob/40df8f6a4c1a1b0b1b731f2a8023b5bb10357790/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/RandomizedStringEqualityComparer.cs#L58-L72

https://github.com/dotnet/runtime/blob/40df8f6a4c1a1b0b1b731f2a8023b5bb10357790/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/NonRandomizedStringEqualityComparer.cs#L47-L53

https://github.com/dotnet/runtime/blob/40df8f6a4c1a1b0b1b731f2a8023b5bb10357790/src/libraries/System.Private.CoreLib/src/System/String.Comparison.cs#L821-L851

---

It seems that the non-randomized version is not seeded at all and will therefore result in the same output across process restarts. This could lead people to take a dependency on the concrete algorithm (although they should not be doing that). This could be avoided by xoring the result with a per-process constant. The performance cost of that should be very small.

[EgorBo]

It seems that the non-randomized version is not seeded at all and will therefore result in the same output across process restarts. This could be avoided by xoring the result with a per-process constant. The performance cost of that should be very small.

Isn't that why it's called "NonRandomized" ? 🙂

From reading the source code, it seems that the randomized comparer calls an entirely different algorithm. Can you educate me on why that is?

See "Background and motivation" section of this proposal, Marvin32 hash code is good, but it's obviously slower than a simpler non-randomized implementation.

[ArminShoeibi]

GetNonRandomizedHashCode instead? GetHashCodeNonRandomized is some odd English.

@Nuklon I think it's better this way GetHashCodeNonRandomized because of Intellisense and ordering.

[En3Tho]

Personally I would vote for option 2 - a new comparer as on String class it feels like it's kinda leaking implementation details. String methods are usually "generic" like Contains, StartsWith etc. And this one is just way to specific to be on String class. Also, I wouldn't personally want newcomers to find this faster than they should :) This kind of thing is more or less oriented on library authors I guess.

[koszeggy]

When I investigated the new IAlternateEqualityComparer<,> interface I noticed that now there is a public NonRandomizedStringEqualityComparer class in the code base but for some reason I cannot access it in Preview 7. Will it be available in .NET 9? But it would be equally alright if the proposed StringComparer.OrdinalNonRandomized/OrdinalIgnoreCaseNonRandomized properties exposed it.

[jkotas]

Will it be available in .NET 9?

No. It is public in CoreLib just to provide binary formatter compatibility as the comment says. It is not part of the public .NET APIs.

[master0luc]

Hi, I do not like to open a new issue, may be it is not an issue at all, but: if we look at this code:

var ttt = new test { id = "6642225a506a0779ca104aa3" };
Console.WriteLine($"{ttt.id}.{ttt.id.GetHashCode()}");
public class test {
    public string id { get; set; }
}

and running it multiple times we obtained different Hash code for the same string: Is it correct behaviour by design? PS compiled for Net8 PPS from docs does not follow such a behaviour, IMHO

[LeaFrock]

@master0luc Yes, it's by design.

Each time your app starts, the value of String.GetHashCode changes. But if you app is running, the hash code won't change even if you try multiple times.

[master0luc]

@LeaFrock, thank you for clarification, It would be nice to mention this behaviour in docs with exlamation mark, IMHO

[bartonjs]

@master0luc It is mentioned in the docs. With an exclamation mark.

From https://learn.microsoft.com/en-us/dotnet/api/system.string.gethashcode?view=net-8.0.

[bartonjs]

With an exclamation mark.

Oh, that's a lowercase i in a circle. Which looks a lot like the Spanish open-exclamation mark. So... close enough? :)

[master0luc]

@Barton's, You are right, it is my inattentiveness. I am sorry. Thanks