Почему объект System.String не может кэшировать свой хэш-код?

Question

Взгляд на исходный код string.GetHashCode с использованием Отражатель показывает следующее (для 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?" на самом деле не несет ответственности. Мне просто любопытно несколько вещей:

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

Чего мне не хватать?

---

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

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

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

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

Answer 1

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

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

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

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

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

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

РЕДАКТИРОВАТЬ: Я только что говорил с Эриком Липпертом об этом (NDC это круто :) и в основном это это о дополнительном обращении к памяти по сравнению с ограниченными преимуществами.

Answer 2

Во-первых, неизвестно, улучшится ли кэширование этого результата Dictionary<string, ...> и др., Потому что они не обязательно используют 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<,> и т. Д., Не могут использовать внутреннюю реализацию, не кэширование этого результата, вероятно, не окажет большого влияния, потому что, честно говоря как часто этот метод будет вызываться в реальном мире: поскольку в большинстве случаев хеш-код строки вычисляется с помощью какого-либо другого механизма.

EDIT

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

ДОПОЛНИТЕЛЬНОЕ РЕДАКТИРОВАНИЕ (!)

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

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

Answer 3

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

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

String example = "Hello World";

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

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

Answer 4

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

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

Answer 5

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

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

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

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

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

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

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

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