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

Казалось бы, что тема словарей, хэш-таблиц и всяческих хэш-кодов расписана вдоль и поперек, а каждый второй разработчик, будучи разбужен от ранней вечерней дремы примерно в 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 _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 FilterRectangles(IEnumerable rectangles)
{
	HashSet result = new HashSet();
	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. Верить никому нельзя. Мне — можно.

© Habrahabr.ru