Казалось бы, что тема словарей, хэш-таблиц и всяческих хэш-кодов расписана вдоль и поперек, а каждый второй разработчик, будучи разбужен от ранней вечерней дремы примерно в 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. Верить никому нельзя. Мне - можно.