GetHashCode() и философский камень, или краткий очерк о граблях

    Казалось бы, что тема словарей, хэш-таблиц и всяческих хэш-кодов расписана вдоль и поперек, а каждый второй разработчик, будучи разбужен от ранней вечерней дремы примерно в 01:28am, быстренько набросает на листочке алгоритм балансировки Hashtable, попутно доказав все свойства в big-O нотации.

    Возможно, такая хорошая осведомленность о предмете нашей беседы, может сослужить и плохую службу, вселяя ложное чувство уверенности: "Это ж так просто! Что тут может пойти не так?"

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

    Так как статья все-таки пятничная, ликбез будет исключительно кратким и академически не строгим.

    Хэш-таблица для самых маленьких

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

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

    Теплая ламповая хэш-таблица
    Теплая ламповая хэш-таблица

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

    Сама же хэш-таблица представляет собой некий "комод" с ящиками, в каждом из которых лежат объекты, определенным образом сгруппированные по их хэш-кодам. Зачем, спрашивается, нужна эта особая группировка, и почему не использовать сами значения хэша в качестве надписи на ящиках? Ну, наверное, потому, что набор коробок под все возможные фамилии в мире не в каждую поликлинику влезет.

    Поэтому поступают хитрее: от фамилии берут одну, две или три первые буквы. В результате нашему "Иванову" придется лежать в одном ящике с "Ивасенко", но специально обученный сотрудник с достаточно ненулевой вероятностью найдет нужный объект простым перебором.

    Если же хэш числовой (как это обычно у нас бывает в IT), то просто берут остаток от его деления на количество коробок, что еще проще.

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

    1. Хэш-код - это не первичный ключ, он совсем не обязан быть уникальным.
      Поликлиника вполне способна сносно функционировать даже в случае, когда у неё на учете стоят два пациента по фамиилии "Иванов".

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

    3. Хэш-код - это не атрибут объекта, поэтому самостоятельной ценности он не несёт и хранить его не нужно (и даже вредно).
      В одной поликлинике хэш - это фамилия, в другой - имя, а креативный паспортный стол хэширует по дате рождения и цвету глаз. И кто их разберет, как они там внутри работают.

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

    Ну а теперь перейдем к реальным (ну или почти реальным) примерам.

    Хэш, кеш и EF

    На коленке написанная подсистема по работе с документами. Документ - это такая простая штука вида

    public class Document
    {
      public Int32 Id {get; set;}
      public String Name {get; set;}
      ...
    }

    Документы хранятся в базе посредством Entity Framework. А от бизнеса требование - чтобы в один момент времени документ мог редактироваться только одним пользователем.

    В лучших традициях велосипедостроения это требование на самом нижнем уровне реализовано в виде хэш-таблицы:

    HashSet<Document> _openDocuments;

    И когда кто-то создает новый документ, сохраняет его в базу и продолжает редактировать, используется следующий код:

    var newDocument = new Document(); // document is created
    _openDocuments.Add(newDocument); // document is open, nobody else can edit it.
    
    context.Documents.Add(newDocument);
    await context.SaveChangesAsync(); // so it's safe to write the document to the DB

    Как вы думаете, чему равно значение переменной test в следующей строке, которая выполнится сразу после написанного выше кода?

    Boolean test = _openDocuments.Contains(newDocument);

    Разумеется, false, иначе бы этой статьи тут не было. Дьявол обычно кроется в деталях, а в нашем случае - в политике EF и в троеточиях объявления класса Document.

    Для EF свойство Id выступает в роли первичного ключа, поэтому заботливая ORM по умолчанию мапит его на автоинкрементное поле базы данных. Таким образом, в момент создания объекта его Id равен 0, а сразу после записи в базу ему присваевается какое-то осмысленное значение:

    var newDocument = new Document(); // newDocument.Id == 0
    _openDocuments.Add(newDocument);
    
    context.Documents.Add(newDocument);
    await context.SaveChangesAsync(); // newDocument.Id == 42

    Само по себе такое поведение, конечно, хэш-таблицу сломать неспособно, поэтому для того, чтобы красиво выстрелить в ногу, внутри класса Document надо написать так:

    public class Document
    {
    	public Int32 Id {get; set;}
    	public String Name {get; set;}
      
    	public override int GetHashCode()
     	{
        return Id;
     	}
    }

    А вот теперь пазл складывается: записали мы в хэш-таблицу объект с хэш-кодом 0, а позже попросили объект с кодом 42.

    Мораль сей басни такова: если вы закопались в отладке, и вам кажется, что либо вы, либо компилятор сошли с ума - проверьте, как у ваших объектов переопределены GetHashCode и Equals методы. Иногда бывает интересно.

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

    Квадратно-гнездовой метод

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

    private static IEnumerable<Size> FilterRectangles(IEnumerable<Size> rectangles)
    {
    	HashSet<Size> result = new HashSet<Size>();
    	foreach (var rectangle in rectangles)
        result.Add(rectangle);
    
    	return result;
    }

    Вроде бы и работает, но вовремя заметили, что производительность фильтрации как-то тяготеет к O(n^2), а не к более приятному O(n). Но постойте, классики Computer Science, ошибаться, конечно, могут, но не так фатально.

    HashSet опять же самая обычная, да и Size - весьма тривиальная структура из FCL. Хорошо, что догадались проверить, какие же хэш-коды генерируются:

        var a = new Size(20,20).GetHashCode(); // a == 0 
        var b = new Size(30,30).GetHashCode(); // b == 0

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

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

    var a = new SizeF(20,20).GetHashCode(); // a == 346948956
    var b = new SizeF(30,30).GetHashCode(); // b == 346948956

    Нет, a и b теперь не равны примитивному нулю! Теперь это истинно случайное значение 346948956...

    Вместо заключения

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

    var a = Int64.MinValue.GetHashCode(); // a == 0
    var b = Int64.MaxValue.GetHashCode(); // a == 0

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

    А будут ли выводы? Ну, давайте:

    1. Хорошо известные и изученные технологии могут преподносить любопытные сюрпризы на практике.

    2. При написании хэш-функции рекомендуется хорошенько подумать... либо использовать специальные кодогенераторы (см. в сторону Resharper).

    3. Верить никому нельзя. Мне - можно.

    Средняя зарплата в IT

    111 000 ₽/мес.
    Средняя зарплата по всем IT-специализациям на основании 7 000 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 16

      +1
      Само по себе такое поведение, конечно, хэш-таблицу сломать неспособно, поэтому для того, чтобы красиво выстрелить в ногу, внутри класса Document надо написать так

      Вроде, Microsoft явно говорит, что нельзя менять хеш код после использования:


      Otherwise, you might think that the mutable object is lost in the hash table. If you do choose to override GetHashCode() for a mutable reference type, your documentation should make it clear that users of your type should not modify object values while the object is stored in a hash table.



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

      Это ужас, из-за которого UI может тормозить на ровном месте на большом числе компьютеров. Создал issue — https://github.com/dotnet/wpf/issues/3499, проследим за реакцией.

        0
        Это ужас, из-за которого UI может тормозить на ровном месте

        А почему? Кто-то держит размеры всех элементов в хеш-таблицах, или словарях и оных размеров могут быть сотни тысяч?
        едит: убрал глупость
          0
          Ну и в предложенном вами варианте сдвигать 32-х битовое значение на 397 битов как-то не очень, всегдаж будет 0 :)

          Мой косяк, вот так подобные баги и рождаются. Спасибо, исправил на умножение.


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

          Не удивлюсь, что кто-то и держит довольно много этих структур в каких-нибудь хеш-таблицах. Или классов, где этот Size — еще одно поле, которое участвует в GetHashCode.


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

            +2
            Мой косяк, вот так подобные баги и рождаются. Спасибо, исправил на умножение.

            Я написал, а потом проверил, оказалось, что когда сдвигаешь на большее количество бит, чем занимает само число, то все кратные сдвиги отбрасываются.
            То есть, например, для Int32
            x << 1;
            y >> 1;
            и
            x << 1 + 32;
            y >> 1 + 32;
            будет одинаковый результат. а раньше не знал :)
          0
          Microsoft явно говорит

          Но кто же читает документацию? :)
          Тем более, что при всей своей капитанской очевидности, занимательное поведение наблюдается только при совпадении ряда факторов.

          github.com/dotnet/wpf/issues/3499

          Там не только в WPF стреляет, System.Drawings много где используется.
            +1
            Rect и Point не лучше: везде значения просто xor'ятся.

            edit: там всё плохо: все примитивны содержат эту ошибку в хеш-функции
          0

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


          Да, чудо не произошло. Но на капельку снизить нагрузку на CPU удалось.

            +1
            Вопрос в том, как вы этот код считаете:

            1. Если вы где-то на пути вычисления используете стандартный GetHashCode(), то MS не гарантирует, что даже между запусками приложения этот код будет одинаков.
            Самый банальный пример — Object.GetHashCode(), который тупо зависит от ссылки объекта.
            Или если, например, починят генерацию кода для структуры Size (по реквесту выше) — то у вас тоже сохраненное с вычисленным не совпадет.

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

            3. А если вы, положим, добавите в класс новое свойство, то придется в дополнение к стандартной миграции базы писать обработчик, которые все коды в базе пересчитает.

            4. Если у вас все обложено тестами, то, наверное, можно спать спокойно… Но если покрытие не 100%, то изредка (и, скорее всего, только на продакшене) вы будете периодически удивляться чудесам.

            Ну а стоит ли вот это вот все капельки снижения нагрузки на CPU — я не знаю.
              0

              Ситуация немного другая. Я на scala пишу.
              Речь об хэшкоде иммутабельного case класса. Сериализовать в базу его не требуется.


              Реализация конкретная — MurmurHash3 по всем параметрам конструктора (для знатоков — хэш от Product).


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

              0
              А почему хранить хэшкод плохо?

              В теории, он может поменяться между запусками, а значит на него можно расчитывать только внутри запущенного процесса (а точнее даже — внутри домена). Ну и плюс он может быть разным между разными версиями .Net'а и разными архитектурами процессора (например, String.GetHashCode различался раньше для x64 и x86).


              Пруф по ссылке:


               Warning
              
              A hash code is intended for efficient insertion and lookup in collections that are based on a hash table. A hash code is not a permanent value. For this reason:
              
              Do not serialize hash code values or store them in databases.
              Do not use the hash code as the key to retrieve an object from a keyed collection.
              Do not send hash codes across application domains or processes. In some cases, hash codes may be computed on a per-process or per-application domain basis.
              Do not use the hash code instead of a value returned by a cryptographic hashing function if you need a cryptographically strong hash. For cryptographic hashes, use a class derived from the System.Security.Cryptography.HashAlgorithm or System.Security.Cryptography.KeyedHashAlgorithm class.
              Do not test for equality of hash codes to determine whether two objects are equal. (Unequal objects can have identical hash codes.) To test for equality, call the ReferenceEquals or Equals method.
                +1

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

                  +1
                  Ежели так, то, конечно, ничего плохого в этом не вижу; особенно, если объект иммутабельный.
              0

              Мне в последнее время всё чаще приходит в голову мысль, что сам интерфейс GetHashCode должен был быть GetHashCode(IHasher). И уже в инстанс этого IHasher скармливать значащие данные типа. А он уж сам решает, как из них собрать хеш. Избавляет от множества головняков, в т.ч. описанного для Size и SizeF. Плюс возможность менять по необходимости хешер в хеш-контейнере, не правя тип ключа.

                0

                Кажется, вы только что придумали интерфейс IEquatable(T) — это как раз и есть внешний хешер и сравнитель)
                Хотя идея ваша понятна — не объект передавать во внешний хешер (IEquatable), а хешер в объект — как стратегию, инвертировать эту ситуацию.


                Отчасти при реализации GetHashCode может помочь https://docs.microsoft.com/en-gb/dotnet/api/system.hashcode?view=dotnet-plat-ext-3.1
                Да, это не внешний хешер, но структура, принимающая значимые данные типа, и вычисляющая хеш.

                  +2
                  Не IEquatable(T), а IEqualityComparer(T). Его можно передавать в словари, для которых и придуман GetHashCode() в первую очередь.
                  +1
                  Мне показалось, что так не стали делать by default сугубо по эстетическим причинам. Видимо, кому-то из дизайнеров языка очень хотелось, чтобы можно было писать как-то так:
                  if (a == b)…

                  Т.е. сам объект должен уметь в Equals без каких-то сторонних параметров. Ну а раз есть Equals, то, логично, нужен такой же GetHashCode. А то как же так — объекты равны, а хэш-коды у них разные? В результате и получили то, что получили.

                  И теперь вот затыкаем с разных сторон такую красоту: начиная от перегруженного Equals для строк, и заканчивая IEqualityComparer(T).

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое