Казалось бы, тема словарей, хеш-таблиц и всяких хэш-кодов исписана с ног до головы, и каждый второй разработчик, пробуждаясь от раннего вечернего сна примерно в 01:28, быстро набрасывает на листке бумаги алгоритм балансировки Hashtable, одновременно доказывающий все свойства в нотации big-O. Возможно, такое хорошее знание предмета нашего разговора может сослужить и плохую службу, вселяя ложное чувство уверенности: «Это так просто! Что может пойти не так?" Как оказалось, может! Что конкретно он умеет — в паре пятничных программистских сказок, сразу после небольшого ликбеза о том, что такое хеш-таблица.
Поскольку статья все еще пятничная, ликбез будет предельно кратким и не академически строгим.
Хэш-таблица для самых маленьких
Наверняка, многие из вас обращались в поликлиники, ЖКХ, паспортные столы и другие учреждения с высоким уровнем благотворительности старого типа.
Когда вы, наклонившись к окну, называете свою фамилию (адрес, номер паспорта и количество родимых пятен), бабушка-одуванчик с другой стороны кивает, шаркает в недра кабинета, а потом через не слишком долгое время приносит свой листок бумаги: будь то медицинская карта, или даже новый паспорт. Магия, позволяющая даже самому быстрому сотруднику в мире найти нужный документ среди тысяч других, — это не что иное, как хеш-таблица, воплощенная в физическом мире: 
Хэш-таблица теплой трубки При такой организации данных каждый объект имеет соответствующий хеш-код. В случае с клиникой хеш-кодом может быть ваша фамилия.
Сама хеш-таблица представляет собой своего рода «комод» с ящиками, в каждом из которых находятся объекты, сгруппированные определенным образом по их хэш-кодам.
Зачем, спрашивается, нужна эта специальная группировка и почему бы не использовать сами хеш-значения в качестве меток на коробках? Ну, наверное, потому, что не в каждую клинику поместится набор коробочек на все возможные фамилии мира.
Поэтому действуют хитрее: берут из фамилии одну, две или три первые буквы.
В результате нашему «Иванову» придется лежать в одном ящике с «Ивасенко», а специально обученный сотрудник с достаточно ненулевой вероятностью найдет искомый предмет простым перебором.
Если хэш числовой (как это обычно бывает в IT), то просто берут остаток от его деления на количество коробочек, что еще проще.
Так мы живем, и чтобы все это работало корректно, хэш-коды должны соответствовать некоторым очень простым правилам:
- Хэш-код Нет Первичный ключ вообще не обязательно должен быть уникальным.
Клиника вполне способна сносно функционировать даже при наличии двух пациентов, зарегистрированных на фамилию «Иванов».
- В этом случае хэш-коды должны быть более или менее равномерно распределены по пространству возможных значений.
Можно, конечно, использовать в качестве хэш-кода количество глаз у пациента, но никаких преимуществ такая картотека не даст – рулят двуглазые, поэтому каждый раз придется проходить практически все.
- Хэш-код не является атрибутом объекта, поэтому не имеет самостоятельного значения и его не нужно (и даже вредно) хранить.
В одной клинике хешем является фамилия, в другой — имя, а в творческом паспортном столе хеши — по дате рождения и цвету глаз.
И кто сможет в них разобраться, как они работают внутри.
- Но для одного и того же объекта (или разных, но идентичных объектов) хэш должен совпадать.
Не должно быть так, что по понедельникам моя карта находится сверху и справа, по четвергам — по центру, а по субботам — вообще под ножку, чтобы хеш-таблица не шаталась.
Хэш, кеш и EF
Есть написанная подсистема работы с документами на коленке.Документ – это такая простая вещь, как
Документы хранятся в базе данных с помощью Entity Framework. Бизнес-требование состоит в том, чтобы документ мог редактировать только один пользователь одновременно.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
Как вы думаете, какое значение имеет переменная test в следующей строке, которая будет выполнена сразу после написанного выше кода? Boolean test = _openDocuments.Contains(newDocument);
Конечно, ложь, иначе этой статьи здесь бы не было.
Дьявол обычно кроется в деталях, а в нашем случае — в политике 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
{
Теги: #Алгоритмы #C++ #.
NET #хеш-таблица #hashset #хеш-код #все читают теги по пятницам
-
Фейерабенд, Пол
19 Oct, 24 -
Клиент Возражает Или Сомневается?
19 Oct, 24 -
Про2. Перезагрузить
19 Oct, 24 -
Nokia 6120 Classic – Умный Малыш
19 Oct, 24
