Гарантируем ли мы, что кеширование хэш-кода через гонку данных будет работать правильно?

public class TestHashRace
{
    private int cachedHash = 0;
    private readonly object value;

    public object Value
    {
        get { return value; }
    }

    public TestHashRace(object value)
    {
        this.value = value;
    }

    public override int GetHashCode()
    {
        if (cachedHash == 0) {
            cachedHash = value.GetHashCode();
        }
        return cachedHash;
    }

    //Equals isn't part of the question, but since comments request it, here we go:
    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != GetType()) return false;
        return Equals((TestHashRace) obj);
    }

    protected bool Equals(TestHashRace other)
    {
        return Equals(value, other.value);
    }
}

Вот простой тестовый класс.

Гарантируем ли мы, что GetHashCode всегда будет возвращать одно и то же значение? И если да, может ли кто-нибудь указать на какой-нибудь справочный материал, который дает нам эту гарантию?

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

Наш класс должен быть неизменным, а поле cachedHash - изменяемым. Поле не может быть изменчивым по соображениям производительности (вся идея этого вопроса и оптимизации мы здесь ставим под сомнение). Ценность неизменна. И это должно быть потокобезопасным.

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


.net concurrency volatile memory-model
person Valentin Kuzub    schedule 24.11.2016    source источник
comment
Непонятно, что вы здесь делаете. У вас нет возможности узнать, когда value изменится - все, что содержит внешнюю ссылку на него, потенциально может изменить это, сделав ваше кешированное хеш-значение устаревшим. Вам нужен тот же хеш-код или правильный хеш-код? Единственный способ, которым это может работать, - это если объект value может уведомить содержащий класс, если он был изменен таким образом, чтобы изменить его хэш (или вам нужен какой-то способ гарантировать, что value не будет изменен извне - сохраните клон или глубокую копию , и т.д). Это должно быть потокобезопасным? Здесь слишком много вопросов ...   -  person J...    schedule 24.11.2016
comment
Переопределение GetHashCode без переопределения Equals приведет к ошибкам. Вам также нужно показать реализацию равных   -  person Scott Chamberlain    schedule 24.11.2016
comment
@J ... отредактировал вопрос в соответствии с вашими требованиями   -  person Valentin Kuzub    schedule 24.11.2016
comment
Поле не может быть изменчивым по причинам производительности. Каковы эти причины производительности? Вы убедились, что это действительно узкое место?   -  person BartoszKP    schedule 24.11.2016
comment
Ваш равный неправ. Если вы получаете True для равенства, вы также должны получить то же значение с помощью GetHashCode от обоих объектов. Также ваш equals в настоящее время бесконечно рекурсивен, потому что у вас нет перегрузки Equals, которая принимает TestHashRace   -  person Scott Chamberlain    schedule 24.11.2016
comment
См. Также stackoverflow.com/a/13160370/569302   -  person Jesus is Lord    schedule 24.11.2016
comment
@BartoszKP Я не говорю, что у нас проблемы с производительностью. Я спрашиваю, правильно ли будет работать удаление volatile в этом коде на C #.   -  person Valentin Kuzub    schedule 24.11.2016
comment
@ValentinKuzub Ну, это ты сказал причины производительности. Я только спрашиваю, что это за причины.   -  person BartoszKP    schedule 24.11.2016
comment
Fyi, volatile не влияет на производительность в этом случае на x86. Инструкции не меняются. Я не вижу, что это помешает JIT-оптимизации (здесь). Но это также не влияет на правильность.   -  person usr    schedule 24.11.2016
comment
@usr звучит очень интересно, не могли бы вы рассказать подробнее? Какие-то ссылки, ссылки, пруфы? Я ищу такой ответ.   -  person Valentin Kuzub    schedule 24.11.2016
comment
Согласно спецификации ECMA для корректности здесь требуется синхронизация. Но никакая JIT в реальном мире не сломает этого. Я бы сравнил машинный код, который генерирует JIT с изменчивым и без него (не стесняйтесь публиковать его). Режим выпуска, x64, не позволяет отладчику предотвращать оптимизацию. Я не знаю, почему может быть разница.   -  person usr    schedule 25.11.2016

Ответы (3)


arrow_upward
6
arrow_downward

Гарантируем ли мы, что GetHashCode всегда будет возвращать одно и то же значение?

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

Это верно, даже если сам TestHashRace неизменен, потому что вы можете сделать это:

var evil = new StringBuilder("hello");
var thr = new TestHashRace(evil);
RunConcurrentCode(thr);
evil.Append(", world!");

Если несколько потоков в RunConcurrentCode запускают вызов GetHashCode thr одновременно, а затем завершаются с разных сторон Append, число, возвращаемое из value.GetHashCode, может быть другим.

[Изменить:] Значение неизменяемо

Тогда единственное, что требуется для сохранения гарантии, - это то, что value GetHashCode правильно реализован, то есть не использует случайные вещи и т. Д.

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

int? cachedHash;
...
public override int GetHashCode() {
    return cachedHash ?? (cachedHash = value.GetHashCode());
}
person Sergey Kalinichenko    schedule 24.11.2016
comment
Спасибо. Я добавил несколько правок к вопросу. Естественно сказать, что нам гарантируется такая же стоимость, но откуда эта гарантия? Некоторые доказательства, ссылки или что-то еще было бы здорово. - person Valentin Kuzub; 24.11.2016
comment
@ValentinKuzub Это происходит из-за неизменности объекта и предположения, что GetHashCode ведет себя как чистая функция, т.е. возвращает то же значение для той же комбинации входных параметров. В этом случае входные параметры - это состояние объекта. От Microsoft: Метод GetHashCode для объекта должен последовательно возвращать один и тот же хэш-код до тех пор, пока не будет изменено состояние объекта, определяющее возвращаемое значение метода Equals объекта. - person Sergey Kalinichenko; 24.11.2016
comment
В этом случае входные параметры - это состояние объекта. - но в нашем случае состояние нашего объекта может быть другим, хэш-код меняет состояние объекта. Он пытается выглядеть как чистая функция, но это не чистая функция. Отсюда вопрос. - person Valentin Kuzub; 24.11.2016
comment
@ValentinKuzub Ваш объект в порядке, он не имеет права голоса в том, что возвращается. Под вопросом value объект. - person Sergey Kalinichenko; 25.11.2016
comment
Абсолютно нормально использовать изменяемые объекты в качестве ключей, если их GetHashCode не переопределен. - person Georg; 29.11.2016

arrow_upward
3
arrow_downward

Нет, не будет, потому что 0 - допустимый результат для value.GetHashCode(). Сделайте cacheedHash типом int, допускающим значение NULL, и проверьте значение NULL вместо 0.

person Scott Chamberlain    schedule 24.11.2016

arrow_upward
-1
arrow_downward

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

Другой вопрос: можете ли вы ожидать, что GetHashCode всегда будет возвращать одно и то же значение. Ответ на этот вопрос в основном положительный. Это дизайнерское решение. Однако для большинства классов возможность использовать экземпляры в качестве ключа в словаре достаточно важна для реализации GetHashCode таким образом, чтобы значение никогда не изменялось, например, не переопределяя его, или только переопределяя его, чтобы сэкономить затраты на отражение.

Примечательно, что сюда входит StringBuilder, так что состояние гонки, отмеченное dasblinkenlight, на самом деле не существует: в отличие от String, StringBuilder всегда будет возвращать один и тот же хэш-код.

Так почему в основном? Ответ на этот вопрос немного неудобен. Технически класс string не является неизменным. Существуют некоторые злые (то есть небезопасные) способы изменить содержимое строки без изменения ссылки, что, в свою очередь, приведет к различным хэш-кодам для той же ссылки. Вы также найдете множество людей, реализующих подобные значения Equals и GetHashCode для классов, страдающих от одной и той же проблемы (и вам не нужно использовать небезопасный код, чтобы попасть в беду).

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

person Georg    schedule 29.11.2016
comment
Почему голосование против? Пожалуйста, оставьте комментарий, если считаете, что что-то не так. - person Georg; 02.12.2016