[.NET, C#, Алгоритмы] GetHashCode() и философский камень, или краткий очерк о граблях
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Казалось бы, что тема словарей, хэш-таблиц и всяческих хэш-кодов расписана вдоль и поперек, а каждый второй разработчик, будучи разбужен от ранней вечерней дремы примерно в 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 == 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
Так что если вы раутете за активное использование в ваших алгоритмах магических констант, и при этом поглядываете на хэширование.... В общем, не говорите, что вас не предупреждали. А будут ли выводы? Ну, давайте:
- Хорошо известные и изученные технологии могут преподносить любопытные сюрпризы на практике.
- При написании хэш-функции рекомендуется хорошенько подумать... либо использовать специальные кодогенераторы (см. в сторону Resharper).
- Верить никому нельзя. Мне - можно.
===========
Источник:
habr.com
===========
Похожие новости:
- [Big Data, Алгоритмы, Карьера в IT-индустрии, Машинное обучение] Подбор скважин-кандидатов для гидравлического разрыва пласта с использованием методов машинного обучения
- [C#, ООП, Программирование] Волшебные методы в C# (перевод)
- [Занимательные задачки, Программирование, C++, Алгоритмы] Обобщение классической задачи на множества с собеседований
- [Высокая производительность, Поисковые технологии, Программирование, Алгоритмы, Go] Текстовый индекс по котировкам в памяти на Go (перевод)
- [C#, Unity] Простая имитация разрушений с использованием Unity и Blender
- [.NET, ASP, C#, Программирование, Тестирование IT-систем] Я 20 лет наслаждаюсь разнообразием архитектур и хочу поделиться мыслями
- [Программирование, Java, .NET] Мне надоело, что индустрия зависит от прихоти создателей языков программирования. Сообществу нужно больше власти
- [.NET, ASP, C#] Варианты использования конфигурации в ASP.NET Core
- [PostgreSQL, SQL, Алгоритмы, Ненормальное программирование] SQL HowTo: курсорный пейджинг с неподходящей сортировкой
- [Программирование, .NET] Enum и switch, и что с ними не так
Теги для поиска: #_.net, #_c#, #_algoritmy (Алгоритмы), #_.net, #_hashset, #_heshtablitsa (хэш-таблица), #_heshkod (хэш-код), #_vse_chitajut_tegi_po_pjatnitsam (все читают теги по пятницам), #_.net, #_c#, #_algoritmy (
Алгоритмы
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 23-Ноя 00:00
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
Казалось бы, что тема словарей, хэш-таблиц и всяческих хэш-кодов расписана вдоль и поперек, а каждый второй разработчик, будучи разбужен от ранней вечерней дремы примерно в 01:28am, быстренько набросает на листочке алгоритм балансировки Hashtable, попутно доказав все свойства в big-O нотации.Возможно, такая хорошая осведомленность о предмете нашей беседы, может сослужить и плохую службу, вселяя ложное чувство уверенности: "Это ж так просто! Что тут может пойти не так?"Как оказалось, может! Что именно может - в паре программистских пятничных баек, сразу после краткого ликбеза о том, что же такое хэш-таблица. Так как статья все-таки пятничная, ликбез будет исключительно кратким и академически не строгим.Хэш-таблица для самых маленькихНаверняка, многие из вас ходили в поликлиники, ЖЭКи, паспортные столы и другие заведения повышенного уровня человеколюбия старого образца. Когда вы, нагибаясь к окошку, называете свою фамилию (адрес, номер паспорта и количество родимых пятен), бабушка-божий-одуванчик по ту сторону кивает, шаркающей походкой удаляется в недра конторы, и затем через не слишком-то продолжительное время приносит вашу бумажку: будь то медицинская карта, а то и новый паспорт. Волшебство, позволяющее не самому быстрому в мире сотруднику найти нужный документ среди тысяч других, представляет собой ни что иное, как воплощенную в физическом мире хэш-таблицу:  Теплая ламповая хэш-таблицаПри подобной организации данных каждому объекту соответствует какой-то хэш-код. В случае с поликлиникой хэш-кодом может быть ваша фамилия. Сама же хэш-таблица представляет собой некий "комод" с ящиками, в каждом из которых лежат объекты, определенным образом сгруппированные по их хэш-кодам. Зачем, спрашивается, нужна эта особая группировка, и почему не использовать сами значения хэша в качестве надписи на ящиках? Ну, наверное, потому, что набор коробок под все возможные фамилии в мире не в каждую поликлинику влезет. Поэтому поступают хитрее: от фамилии берут одну, две или три первые буквы. В результате нашему "Иванову" придется лежать в одном ящике с "Ивасенко", но специально обученный сотрудник с достаточно ненулевой вероятностью найдет нужный объект простым перебором. Если же хэш числовой (как это обычно у нас бывает в IT), то просто берут остаток от его деления на количество коробок, что еще проще.Так и живем, а чтобы все это хозяйство работало правильно, хэш-коды должны соответствовать некоторым весьма простым правилам:
public class Document
{ public Int32 Id {get; set;} public String Name {get; set;} ... } 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 Boolean test = _openDocuments.Contains(newDocument);
var newDocument = new Document(); // newDocument.Id == 0
_openDocuments.Add(newDocument); context.Documents.Add(newDocument); await context.SaveChangesAsync(); // newDocument.Id == 42 public class Document
{ public Int32 Id {get; set;} public String Name {get; set;} public override int GetHashCode() { return Id; } } private static IEnumerable<Size> FilterRectangles(IEnumerable<Size> rectangles)
{ HashSet<Size> result = new HashSet<Size>(); foreach (var rectangle in rectangles) result.Add(rectangle); return result; } var a = new Size(20,20).GetHashCode(); // a == 0
var b = new Size(30,30).GetHashCode(); // b == 0 var a = new SizeF(20,20).GetHashCode(); // a == 346948956
var b = new SizeF(30,30).GetHashCode(); // b == 346948956 var a = Int64.MinValue.GetHashCode(); // a == 0
var b = Int64.MaxValue.GetHashCode(); // a == 0
=========== Источник: habr.com =========== Похожие новости:
Алгоритмы ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 23-Ноя 00:00
Часовой пояс: UTC + 5