Подтвердить что ты не робот

Почему объект System.String не кэширует хэш-код?

Взгляните на исходный код string.GetHashCode, используя Reflector показывает следующее (для версии mscorlib.dll 4.0):

public override unsafe int GetHashCode()
{
    fixed (char* str = ((char*) this))
    {
        char* chPtr = str;
        int num = 0x15051505;
        int num2 = num;
        int* numPtr = (int*) chPtr;
        for (int i = this.Length; i > 0; i -= 4)
        {
            num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
            if (i <= 2)
            {
                break;
            }
            num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
            numPtr += 2;
        }
        return (num + (num2 * 0x5d588b65));
    }
}

Теперь я понимаю, что реализация GetHashCode не указана и зависит от реализации, поэтому вопрос "есть GetHashCode реализованы в виде X или Y?" на самом деле не отвечает. Мне просто интересно несколько вещей:

  • Если Reflector правильно разобрал DLL, и это реализация GetHashCode (в моей среде), могу ли я правильно интерпретировать этот код, чтобы указать, что объект string, основанный на этой конкретной реализации, не будет кэшировать его хеш-код?
  • Предполагая, что ответ да, почему это было бы? Мне кажется, что стоимость памяти будет минимальной (еще одно 32-битное целое число, падение пруда по сравнению с размером самой строки), тогда как экономия будет значительной, особенно в тех случаях, когда используются, например, строки как ключи в коллекции на основе хэш-таблицы, например, Dictionary<string, [...]>. А поскольку класс string неизменен, это не похоже на то, что значение, возвращаемое GetHashCode, даже изменится.

Что я могу потерять?

ОБНОВЛЕНИЕ. В ответ на замечание Андраса Золтана:

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

Эй, ага! Это интересный момент для создания (и да, это очень верно), но я действительно сомневаюсь, что это было принято рассмотрение при реализации GetHashCode. Утверждение "поэтому для кэширования результата было бы неправильным" подразумевает, что отношение структуры к строкам "Ну, они должны быть неизменными, но на самом деле, если разработчики хотят получить подлый, они изменяемы, поэтому мы будем рассматривать их как таковых". Это определенно не то, как строки представления структуры. Он полностью полагается на их неизменность во многих отношениях (интернирование строковых литералов, назначение всех строк нулевой длины на string.Empty и т.д.), Которые, в основном, если вы мутируете строку, вы пишете код, поведение которого полностью undefined и непредсказуемым.

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

4b9b3361

ОТВЕТЫ

Ответ 1

Очевидный потенциальный ответ: потому что это будет стоить памяти.

Здесь приведен анализ затрат и выгод:

Стоимость: 4 байта для каждой строки (и быстрый тест при каждом вызове GetHashCode). Также сделайте объект string изменяемым, что, очевидно, означает, что вам нужно быть осторожным в отношении реализация - если вы не всегда вычисляете хеш-код вверх, что представляет собой стоимость вычисления его один раз для каждой строки, независимо от того, вы когда-либо делаете хэш-код.

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

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

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

EDIT: Я только что поговорил с Эриком Липпертом об этом (NDC является удивительным:) и в основном речь идет о дополнительном удалении памяти и ограниченных преимуществах.

Ответ 2

Во-первых, не известно, действительно ли кеширование этого результата улучшило бы Dictionary<string, ...> et al, потому что они не обязательно используют String.GetHashCode, потому что он использует IComparer для получения хэш-кода для строки.

И если вы следуете за вероятной цепочкой вызовов для класса StringComparer, она переходит в класс System.Globalization.CompareInfo, который, наконец, заканчивается при этом методе:

[SecurityCritical, SuppressUnmanagedCodeSecurity, DllImport("QCall",
   CharSet=CharSet.Unicode)]
private static extern int InternalGetGlobalizedHashCode(IntPtr handle, string
   localeName, string source, int length, int dwFlags);

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

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

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

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

ИЗМЕНИТЬ

Там также точка в ответе Тима (+1 там). Если он прав, и я думаю, что он есть, то нет никакой гарантии, что строка будет неизменной после построения, поэтому для кэширования результат будет неправильным.

ДОПОЛНИТЕЛЬНОЕ ИЗОБРАЖЕНИЕ (!)

Дэн утверждает, что строки должны быть неизменными в сфере Net, и поэтому эта строка должна быть свободной для кэширования собственного хэш-кода на основе этого. Проблема здесь в том, что .Net framework также предоставляет законный способ изменения якобы неизменяемой строки, которая не включает в себя привилегированное отражение или что-то еще. Это фундаментальная проблема со строками, это указатель на буфер, который вы не можете контролировать. Не обращайте внимания на мир С#, а что на С++, где векторное преобразование и изменение буферов памяти является общим. Просто потому, что вы в идеале не должны этого делать, это не означает, что структура должна ожидать, что вы этого не сделаете.

.Net, как представляется, обеспечивает эту функциональность, и поэтому, если это было конструктивным решением команды .Net в ответ на вид бинарной гадости, предложенный Тимом, тогда они были очень мудры, чтобы принять это во внимание. Независимо от того, сделали они это, или это случайно, это совсем другое дело!:)

Ответ 3

Возможно, я сделал неверный вывод, но не правда ли, что, хотя строка является неизменяемой в контексте объекта .NET String, все еще можно изменить значение?

Например, если вы так склонны это делать...

String example = "Hello World";

unsafe
{
    fixed (char* strPointer = myString) {
        strPointer[1] = 'a';
    }
}

... не будет example по-прежнему представлять один и тот же объект String, но теперь со значением, которое вычисляло бы другое значение для GetHashCode()? Я могу быть вне базы здесь, но поскольку вы можете легко (если не бессмысленно) сделать это, это также вызовет некоторые проблемы.

Ответ 4

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

Но, как отмечали другие, основной причиной не кэширования значения является то, что использование дополнительной памяти, вероятно, намного перевешивает потенциальную экономию кеширования хэш-кода. Время выполнения GetHashCode равно O (N) по длине строки, поэтому худший сценарий повторного хеширования хорошо ограничен.

Ответ 5

Любое значение int является допустимым кодом HashCode. Это означает, что нет значения по умолчанию для int, например -1 или 0, которое мы можем использовать, чтобы указать, что мы еще не вычислили HashCode. Поэтому, если строка должна кэшировать свой HashCode, необходимо выполнить одно из следующих действий:

  • Имейте int-поле для HashCode, плюс поле bool, которое будет использоваться в качестве флага для вычисления HashCode еще, а затем только вычислить HashCode при первом запросе (ленивая оценка), или
  • Имейте поле int для HashCode и всегда вычислять HashCode при построении строки.

Оба варианта имеют недостаток; первая требует еще большего объема памяти, а вторая имеет производительность для вычисления HashCodes, которая никогда не понадобится.

Теперь рассмотрим случай Dictionary<TKey,TValue>. HashCode, используемый Словарем, зависит от того, какой компаратор используется. По умолчанию для сравнения используется обычный метод GetHashCode() объекта. Но вы могли бы создать словарь, который, например, использует нечувствительный к регистру сравнитель, и HashCode, используемый Словарем, будет производиться этим компаратором, который, вероятно, создаст совершенно другой HashCode, чем String.GetHashCode(). Итак, какой HashCode выполняет строковый кеш? Строка может быть в двух словарях, причем каждый использует другой сопоставитель, ни один из которых не использует обычную строку GetHashCode. Таким образом, строка может кэшировать HashCode, ни один из словарей даже не используется.

В случае Dictionary<TKey,TValue> существует еще более важная причина, что наличие строк кэширования их HashCodes, скорее всего, не принесет никакой выгоды от производительности. Внутренняя реализация словаря делает следующее при добавлении новой записи:

  • Вычисляет HashCode ключа с помощью метода GetHashCode() сопоставления равенства, предоставленного при построении, или сравнения по умолчанию, если ни один не указан.
  • Сбрасывает знаковый бит с HashCode
  • Сохраняет новую запись, состоящую из модифицированного HashCode сверху, ключа, значения и индекса следующей записи в списке записей, которые отображаются в одном и том же ведре.

Когда Словарь выполняет поиск ключа, он вычисляет измененный (то есть положительный) HashCode искомого ключа, получает ведро, к которому привязано HashCode, а затем просматривает список записей в этом ковше. Чтобы проверить, соответствует ли запись, сначала проверяется, соответствуют ли модифицированные коды HashCodes (если ключи равны, также должны быть равны HashCodes), и если они равны, проверяет, равны ли эти два ключа. В случае строк этот алгоритм реализует две вещи; во-первых, он избегает многих сопоставлений строк, используя простое целое сравнение сначала, чтобы увидеть, стоит ли сравнивать строку, а во-вторых, кэширует HashCodes каждого ключа в словаре. HashCode каждого ключа в словаре вычисляется только один раз, когда пара ключ/значение добавляется в словарь.

(Если вам интересно, почему словарь блокирует бит знака из HashCode, он потому, что он использует значение -1 в качестве значения маркера в поле hashCode для входных слотов, которые в настоящее время пустые.)