Могу ли я быть уверен, что встроенный хэш для данной строки всегда одинаков?

Question

Я получаю строковый хеш, как это:

string content = "a very long string";
int contentHash = content.GetHashCode();

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

Могу ли я быть уверен, что хеш для данной строки («очень длинная строка») всегда будет одинаковым?

Могу ли я быть уверен, что две разные строки не будут иметь одинаковый хэш?

Кроме того, если возможно, насколько вероятно получить один и тот же хеш для разных строк?

Answer 1

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

Answer 2

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

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

Класс String переопределяет реализацию GetHashCode по умолчанию в объекте.

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

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

Редактировать : Я только что заметил, что ни один из ответов не имеет прямого отношения к каждому из вас (хотя я думаю, что ответ на них ясен), но просто приведу в порядок: -

Могу ли я быть уверен, что хеш для данной строки («очень длинная строка») всегда будет одинаковым?

В вашем использовании, да.

Могу ли я быть уверен, что две разные строки не будут иметь одинаковый хэш?

Нет. Две разные строки могут иметь одинаковый хеш.

Также, если возможно, насколько вероятно получить одинаковый хеш для разных строк?

Вероятность довольно низкая, результирующий хеш довольно случайный для домена 4G.

Answer 3

Как уже говорили многие другие, реализация зависит от версии платформы, но также зависит от архитектуры . Реализация string.GetHashCode () отличается в версиях платформы x86 и x64, даже если они имеют одинаковый номер версии.

Например, если вы пишете архитектуру типа клиент-сервер или .net remoting и хотите использовать строковый HashCode, чтобы остановить загрузку большого ресурса, вы можете сделать это только в том случае, если обе версии имеют одинаковую версию и разрядность. В противном случае вы должны использовать другой хеш - MD5, SHA и т. Д. Будут работать правильно.

Answer 4

Как отмечали другие, хэш будет оставаться постоянным с течением времени. Но почему вы хэшируете строку, а затем помещаете ее как ключ в словарь? Хэши не гарантируются быть уникальными. Так что ваши сравнения могут быть неверными. Пусть Словарь сделает свое дело. Я думаю, что наиболее подходящая коллекция для этого случая - HashSet .

Answer 5

Да, так и есть, цель хеш-кода! Это не гарантируется быть одинаковым между различными версиями среды выполнения. Больше информации о MSDN

Answer 6

Документация для Object.GetHashCode состояний

Если два объекта сравниваются как равные, метод GetHashCode для каждого объекта должен возвращать одинаковое значение.

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

Answer 7

Вам не нужно угадывать время выполнения или версии, просто используйте этот класс CaseInsensitiveStringComparer, который я создал в свое свободное время (вы можете передать его в конструктор словаря или, если вы используете .NET 3.5, HashSet):

/// <summary>
/// StringComparer that is basically the same as StringComparer.OrdinalIgnoreCase, except that the hash code function is improved and guaranteed not to change.
/// </summary>
public class CaseInsensitiveStringComparer : StringComparer
{
    /// <summary>
    /// Compares two strings, ignoring case
    /// </summary>
    /// <param name="x">First string</param>
    /// <param name="y">Second string</param>
    /// <returns>Compare result</returns>
    public override int Compare(string x, string y)
    {
        return StringComparer.OrdinalIgnoreCase.Compare(x, y);
    }

    /// <summary>
    /// Checks if two strings are equal, ignoring case
    /// </summary>
    /// <param name="x">First string</param>
    /// <param name="y">Second string</param>
    /// <returns>True if strings are equal, false if not</returns>
    public override bool Equals(string x, string y)
    {
        return Compare(x, y) == 0;
    }

    /// <summary>
    /// Gets a hash code for a string, ignoring case
    /// </summary>
    /// <param name="obj">String to get hash code for</param>
    /// <returns>Hash code</returns>
    public override int GetHashCode(string obj)
    {
        if (obj == null)
        {
            return 0;
        }
        int hashCode = 5381;
        char c;
        for (int i = 0; i < obj.Length; i++)
        {
            c = obj[i];
            if (char.IsLower(c))
            {
                c = char.ToUpperInvariant(c);
            }
            hashCode = ((hashCode << 5) + hashCode) + c;
        }
        return hashCode;
    }
}

Answer 8

Учитывая, что существует бесконечное количество разных строк, просто невозможно выделить разные значения типа int (32 бита, которые могут представлять до 4 миллиардов) для каждой.

Всего 8 символов - это 2 ^ 60 разных строк. Это бесконечно больше, чем 2 ^ 32. Естественно, хэш-код некоторых из этих строк должен конфликтовать.

Два объекта с одинаковым хеш-кодом не обязательно должны быть равны. Чтобы знать наверняка, используйте метод equals. Это в основном стратегия, используемая хэш-картой для определения того, равны ли ключи.

Map.get (Строковый ключ)

• Рассчитать хеш-код ключа
• Используйте модуль по модулю, чтобы выяснить, к какому ключу ведра принадлежит тоже.
• Перебрать все записи из этого сегмента, пытаясь найти соответствующий ключ.
• Если найдено совпадение ключей, вернуть значение этих записей.

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

Javadoc для Object.hashcode делает для интересного чтения - я вставил фрагмент ниже.

 The equals method implements an equivalence relation:

* It is reflexive: for any reference value x, x.equals(x) should return true.
* It is symmetric: for any reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
* It is transitive: for any reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
* It is consistent: for any reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the object is modified.
* For any non-null reference value x, x.equals(null) should return false. 

Метод equals для класса Object реализует максимально различающее возможное отношение эквивалентности для объектов; то есть для любых ссылочных значений x и y этот метод возвращает true, если и только если x и y ссылаются на один и тот же объект (x == y имеет значение true).

Answer 9

Могу ли я быть уверен, что хеш для заданная строка («очень длинная строка») будет всегда одинаковым?

Да

Могу ли я быть уверен, что два разных строки не будут иметь одинаковый хеш?

нет

Нет

Answer 10

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

Так что я бы сказал, что этот метод хорош, если он используется внутри приложения. Если вы сохраняете значение в хранилище данных, то, вероятно, лучше свернуть свою собственную функцию, чтобы убедиться, что она остается согласованной между версиями.