Хэш-качество и стабильность String.GetHashCode () в .NET?

Question

Я задаюсь вопросом о качестве хеш-функции и стабильности хеширования , созданной реализацией String.GetHashCode() в .NET?

Что касается качества, я концентрируюсь на алгоритмических аспектах (следовательно, качество хеш-функции, поскольку она влияет на большие хеш-таблицы, а не на проблемы безопасности).

Затем, что касается стабильности, я задаюсь вопросом о потенциальных проблемах с версионированием, которые могут возникнуть при переходе с одной версии .NET на другую.

Некоторые сведения об этих двух аспектах будут весьма полезны.

Answer 1

Я не могу дать вам каких-либо подробностей о качестве (хотя я бы предположил, что это довольно хорошо, учитывая, что строка является одним из базовых классов фреймворка, который, вероятно, будет использоваться в качестве хеш-ключа).

Однако, что касается стабильности, хеш-код, созданный в разных версиях фреймворка, не обязательно будет одинаковым, и он изменился в прошлом, поэтому вы абсолютно не должны полагаться на стабильность хеш-кода между версиями ( см. Здесь для справки, что он изменился между 1,1 и 2,0 ). Фактически, она даже отличается между 32-битной и 64-битной версиями той же версии framework; из документов :

Значение, возвращаемое GetHashCode, зависит от платформы. Для конкретного строкового значения оно отличается в 32-разрядной и 64-разрядной версиях .NET Framework.

Answer 2

Это старый вопрос, но я бы хотел добавить, упомянув эту ошибку Microsoft о качестве хеша .

Сводка: На 64b, качество хэша очень низкое, когда ваша строка содержит байты '\ 0' . По сути, будет хэшироваться только начало строки.

Если вы, как и я, должны использовать строки .Net для представления двоичных данных в качестве ключа для высокопроизводительных словарей, вы должны знать об этой ошибке.

Жаль, это WONTFIX ... Как замечание, я не понимаю, как они могли бы сказать, что изменение хеш-кода является критическим изменением, когда код включает

// We want to ensure we can change our hash function daily.
// This is perfectly fine as long as you don't persist the
// value from GetHashCode to disk or count on String A
// hashing before string B. Those are bugs in your code.
hash1 ^= ThisAssembly.DailyBuildNumber;

и хеш-код уже в x86 / 64b уже другой.

Answer 3

Я знаю, что это на самом деле не включает указанные вами значения качества и стабильности, но стоит помнить, что хеширование очень больших строк может привести к исключению OutOfMemoryException.

https://connect.microsoft.com/VisualStudio/feedback/details/517457/stringcomparers-gethashcode-string-throws-outofmemoryexception-with-plenty-of-ram-available

Answer 4

Я только что столкнулся с проблемой, связанной с этим.На одном из моих компьютеров (64-битном) у меня возникла проблема: я обнаружил, что два разных объекта идентичны, за исключением (сохраненного) хэш-кода.Этот хеш-код был создан из строки .... той же строки!

m_storedhash = astring.GetHashCode();

Я не знаю, как эти два объекта оказались с разными хеш-кодами, если они были из одной строкиоднако я подозреваю, что в том же exe-файле .NET один из проектов библиотеки классов, от которого я зависел, был установлен на x86, а другой на ANYCPU, и один из этих объектов был создан в методе внутри класса x86 lib, а другой -объект (те же входные данные, все то же самое) был создан в методе внутри библиотеки классов ANYCPU.

Итак, звучит ли это правдоподобно: в одном и том же исполняемом файле в памяти (не между процессами) часть кода может быть запущена со строкой x86 Framework.

Answer 5

Качество хеш-кодов достаточно хорошее для их предназначения, то есть они не вызывают слишком много коллизий, когда вы используете строки в качестве ключа в словаре.Я подозреваю, что он будет использовать всю строку для вычисления хеш-кода, если длина строки достаточно короткая, для огромных строк он будет использовать только первую часть.

Нет гарантии стабильности между версиями.В документации четко сказано, что алгоритм хеширования может меняться от одной версии к другой, поэтому хэш-коды предназначены для краткосрочного использования.