Казалось бы, что тема словарей, хэш-таблиц и всяческих хэш-кодов расписана вдоль и поперек, а каждый второй разработчик, будучи разбужен от ранней вечерней дремы примерно в 01:28am, быстренько набросает на листочке алгоритм балансировки Hashtable, попутно доказав все свойства в big-O нотации.
Возможно, такая хорошая осведомленность о предмете нашей беседы, может сослужить и плохую службу, вселяя ложное чувство уверенности: "Это ж так просто! Что тут может пойти не так?"
Как оказалось, может! Что именно может - в паре программистских пятничных баек, сразу после краткого ликбеза о том, что же такое хэш-таблица.
Так как статья все-таки пятничная, ликбез будет исключительно кратким и академически не строгим.
Хэш-таблица для самых маленьких
Наверняка, многие из вас ходили в поликлиники, ЖЭКи, паспортные столы и другие заведения повышенного уровня человеколюбия старого образца. Когда вы, нагибаясь к окошку, называете свою фамилию (адрес, номер паспорта и количество родимых пятен), бабушка-божий-одуванчик по ту сторону кивает, шаркающей походкой удаляется в недра конторы, и затем через не слишком-то продолжительное время приносит вашу бумажку: будь то медицинская карта, а то и новый паспорт.
Волшебство, позволяющее не самому быстрому в мире сотруднику найти нужный документ среди тысяч других, представляет собой ни что иное, как воплощенную в физическом мире хэш-таблицу:
Теплая
ламповая хэш-таблица
При подобной организации данных каждому объекту соответствует какой-то хэш-код. В случае с поликлиникой хэш-кодом может быть ваша фамилия.
Сама же хэш-таблица представляет собой некий "комод" с ящиками, в каждом из которых лежат объекты, определенным образом сгруппированные по их хэш-кодам. Зачем, спрашивается, нужна эта особая группировка, и почему не использовать сами значения хэша в качестве надписи на ящиках? Ну, наверное, потому, что набор коробок под все возможные фамилии в мире не в каждую поликлинику влезет.
Поэтому поступают хитрее: от фамилии берут одну, две или три первые буквы. В результате нашему "Иванову" придется лежать в одном ящике с "Ивасенко", но специально обученный сотрудник с достаточно ненулевой вероятностью найдет нужный объект простым перебором.
Если же хэш числовой (как это обычно у нас бывает в IT), то просто берут остаток от его деления на количество коробок, что еще проще.
Так и живем, а чтобы все это хозяйство работало правильно, хэш-коды должны соответствовать некоторым весьма простым правилам:
-
Хэш-код - это не первичный ключ, он совсем не обязан быть уникальным.
Поликлиника вполне способна сносно функционировать даже в случае, когда у неё на учете стоят два пациента по фамиилии "Иванов". -
При этом хэш-коды должны быть более-менее равномерно распределены по пространству возможных значений.
Можно, конечно, в качестве хэш-кода использовать количество глаз у пациента, только вот преимуществ такая картотека никаких не даст - двухлазые рулят, поэтому перебирать каждый раз придется почти все. -
Хэш-код - это не атрибут объекта, поэтому самостоятельной ценности он не несёт и хранить его не нужно (и даже вредно).
В одной поликлинике хэш - это фамилия, в другой - имя, а креативный паспортный стол хэширует по дате рождения и цвету глаз. И кто их разберет, как они там внутри работают. -
Но для одного и того же объекта (или разных, но одинаковых объектов) хэш должен совпадать. Не должно происходить такого, что по понедельникам моя карточка лежит сверху и справа, по четвергам - по центру, а по субботам её вообще под ножку ставят, чтобы хэш-таблица не шаталась.
Ну а теперь перейдем к реальным (ну или почти реальным) примерам.
Хэш, кеш и 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 == 346948956var b = new SizeF(30,30).GetHashCode(); // b == 346948956
Нет, a и b теперь не равны примитивному нулю! Теперь это истинно случайное значение 346948956...
Вместо заключения
Если вы думаете, что хэш-коды могут забавно вычисляться только в ваших собственных классах, ну и изредка в сущностях FCL, еще один забавный пример:
var a = Int64.MinValue.GetHashCode(); // a == 0var b = Int64.MaxValue.GetHashCode(); // a == 0
Так что если вы раутете за активное использование в ваших алгоритмах магических констант, и при этом поглядываете на хэширование.... В общем, не говорите, что вас не предупреждали.
А будут ли выводы? Ну, давайте:
-
Хорошо известные и изученные технологии могут преподносить любопытные сюрпризы на практике.
-
При написании хэш-функции рекомендуется хорошенько подумать... либо использовать специальные кодогенераторы (см. в сторону Resharper).
-
Верить никому нельзя. Мне - можно.
