Давайте иметь этот класс C # (это будет почти то же самое в Java)
public class MyClass {
public string A {get; set;}
public string B {get; set;}
public override bool Equals(object obj) {
var item = obj as MyClass;
if (item == null || this.A == null || item.A == null)
{
return false;
}
return this.A.equals(item.A);
}
public override int GetHashCode() {
return A != null ? A.GetHashCode() : 0;
}
}
Как видите, равенство двух экземпляров MyClass
зависит A
только от. Таким образом, могут быть два экземпляра, которые равны, но содержат различную информацию в своем B
свойстве.
В стандартной библиотеке коллекций многих языков (включая, конечно, C # и Java) есть Set
( HashSet
в C #) коллекция, которая может содержать не более одного элемента из каждого набора равных экземпляров.
Можно добавлять элементы, удалять элементы и проверять, содержит ли набор элемент. Но почему невозможно получить конкретный предмет из набора?
HashSet<MyClass> mset = new HashSet<MyClass>();
mset.Add(new MyClass {A = "Hello", B = "Bye"});
//I can do this
if (mset.Contains(new MyClass {A = "Hello", B = "See you"})) {
//something
}
//But I cannot do this, because Get does not exist!!!
MyClass item = mset.Get(new MyClass {A = "Hello", B = "See you"});
Console.WriteLine(item.B); //should print Bye
Единственный способ получить мой элемент - это перебрать всю коллекцию и проверить все элементы на равенство. Однако O(n)
вместо этого требуется время O(1)
!
До сих пор я не нашел ни одного языка, который бы поддерживал набор. Все «общие» языки, которые я знаю (Java, C #, Python, Scala, Haskell ...), выглядят одинаково: вы можете добавлять элементы, но не можете их извлекать. Есть ли веская причина, почему все эти языки не поддерживают что-то такое простое и очевидно полезное? Они не могут быть просто не правы, верно? Есть ли языки, которые поддерживают это? Может быть, получение определенного предмета из набора неправильно, но почему?
Есть несколько связанных с этим вопросов SO:
/programming/7283338/getting-an-element-from-a-set
/programming/7760364/how-to-retrieve-actual-item-from-hashsett
std::set
поддерживает поиск объектов, поэтому не все «общие» языки такие, как вы описали.Set<E>
реализации находятся толькоMap<E,Boolean>
внутри.a == b
всегда верно) на всякий случайthis.A == null
.if (item == null || this.A == null || item.A == null)
Тест «перестарались» и проверяет много, возможно , для того , чтобы искусственно создать «высокого качества» кода. Я вижу этот вид «перепроверки» и все время слишком корректен в Code Review.Ответы:
Проблема здесь не в том, что
HashSet
не хватаетGet
метода, а в том, что ваш код не имеет смысла с точки зренияHashSet
типа.Этот
Get
метод, по сути, «принесите мне это значение, пожалуйста», на что люди .NET Framework разумно ответили бы: «А? У вас уже есть это значение<confused face />
».Если вы хотите сохранить элементы, а затем извлечь их на основе сопоставления с другим немного другим значением, используйте следующее
Dictionary<String, MyClass>
:Ну да, но это потому, что не в порядке
MyClass
с принципом наименьшего удивления (POLA). С этой инкапсулированной функциональностью равенства вполне разумно предположить, что следующий код допустим:Чтобы предотвратить это,
MyClass
необходимо четко документировать его странную форму равенства. Сделав это, он больше не заключен в капсулу, и изменение принципа равенства нарушит принцип открытия / закрытия. Поэтому это не должно измениться и, следовательно,Dictionary<String, MyClass>
является хорошим решением для этого странного требования.источник
Dictionary<MyClass, MyClass>
поскольку это тогда выберет значение, основанное на ключе, который используетMyClass.Equals
.Dictionary<MyClass, MyClass>
поставляемое с соответствующимIEqualityComparer<MyClass>
и вытащить отношение эквивалентности из.MyClass
ПочемуMyClass
нужно знать об этом отношении по его экземплярам?...reasonable to assume...
. Все это может быть правдой в 99% случаев, но возможность извлечения предмета из набора может оказаться полезной. Код реального мира не всегда может следовать принципам POLA и т. Д. Например, если вы дедуплицируете строки без учета регистра, вы можете получить «главный» элемент.Dictionary<string, string>
это обходной путь, но стоит перф.У вас уже есть предмет, который находится «в» наборе - вы передали его в качестве ключа.
«Но это не тот случай, когда я назвал« Добавить »» - да, но вы специально утверждали, что они были равны.
A
Set
также является частным случаемMap
|Dictionary
с void в качестве типа значения (ну, бесполезные методы не определены, но это не имеет значения).Структура данных, которую вы ищете, - это то,
Dictionary<X, MyClass>
откудаX
каким-то образом получается As из MyClasses.Тип C # Dictionary хорош в этом отношении, так как он позволяет вам предоставлять IEqualityComparer для ключей.
Для приведенного примера у меня будет следующее:
Используется таким образом:
источник
Dictionary<String, String>
.Comparer
иDictionary<MyClass, MyClass>
является прагматичным решением. В Java то же самое может быть достигнутоTreeSet
илиTreeMap
плюс пользовательскийComparator
.Ваша проблема в том, что у вас есть два противоречивых понятия равенства:
Если бы вы использовали фактическое отношение равенства в вашем наборе, проблема извлечения определенного элемента из набора не возникает - чтобы проверить, находится ли объект в наборе, у вас уже есть этот объект. Поэтому никогда не требуется извлекать конкретный экземпляр из набора, если вы используете правильное отношение равенства.
Мы также можем утверждать, что набор - это абстрактный тип данных, который определяется исключительно отношением
S contains x
илиx is-element-of S
(«характеристическая функция»). Если вы хотите другие операции, вы на самом деле не ищете набор.То, что происходит довольно часто, но не является множеством, - это то, что мы группируем все объекты в отдельные классы эквивалентности . Объекты в каждом таком классе или подмножестве являются только эквивалентными, а не равными. Мы можем представлять каждый класс эквивалентности через любой член этого подмножества, и тогда становится желательным получить этот представляющий элемент. Это будет отображение класса эквивалентности на представительный элемент.
Я думаю, что в C # словарь может использовать явное отношение равенства. В противном случае такое отношение можно реализовать, написав быстрый класс-обертку. псевдокод:
источник
Потому что это не то, для чего наборы.
Позвольте мне перефразировать пример.
Если заменить «HashSet» на «Collection», «objects» на «Values» и «property A» на «Key», предложение становится:
Описывается словарь. Фактический вопрос, который задают: «Почему я не могу рассматривать HashSet как словарь?»
Ответ в том, что они не используются для одной и той же вещи. Причина использования набора состоит в том, чтобы гарантировать уникальность его индивидуального содержимого, в противном случае вы можете просто использовать List или массив. Поведение, описываемое в этом вопросе, предназначено для словаря. Все дизайнеры языка не облажались. Они не предоставляют метод get, потому что если у вас есть объект, и он находится в наборе, они эквивалентны, что означает, что вы «получаете» эквивалентный объект. Утверждение, что HashSet должен быть реализован таким образом, чтобы вы могли «получить» неэквивалентные объекты, которые вы определили как равные, не является началом, когда языки предоставляют другие структуры данных, которые позволяют вам это делать.
Заметка об ООП и равенстве комментариев / ответов. Это нормально, когда ключ сопоставления является свойством / членом хранимого значения в словаре. Например: иметь в качестве ключа Guid, а также свойство, которое используется для метода equals, вполне разумно. Что не разумно, так это иметь разные значения для остальных свойств. Я считаю, что если я иду в этом направлении, мне, вероятно, нужно переосмыслить структуру своего класса.
источник
Как только вы переопределите равно, вам лучше переопределить хэш-код. Как только вы это сделаете, ваш «экземпляр» никогда не должен снова менять внутреннее состояние.
Если вы не переопределяете equals и для определения равенства используется хеш-код, то идентификатор объекта VM. Если вы поместите этот объект в набор, вы сможете найти его снова.
Изменение значения объекта, используемого для определения равенства, приведет к невозможности отслеживания этого объекта в структурах на основе хеша.
Так что сеттер на А опасен.
Теперь у вас нет B, который не участвует в равенстве. Проблема здесь семантически, а не технически. Потому что технически изменение B нейтрально для факта равенства. Семантически B должен быть чем-то вроде флага «версия».
Дело в том:
Если у вас есть два объекта, которые равны A, но не B, у вас есть предположение, что один из этих объектов новее, чем другой. Если у B нет информации о версии, это предположение скрыто в вашем алгоритме, когда вы решаете «перезаписать / обновить» этот объект в наборе. Такое расположение исходного кода, где это происходит, может быть неочевидным, поэтому разработчику будет непросто определить отношение между объектом X и объектом Y, которое отличается от X в B.
Если B имеет информацию о версии, вы выставляете предположение, что ранее он был только неявным образом выводим из кода. Теперь вы можете видеть, что объект Y является более новой версией X.
Подумайте о себе: ваша личность остается на всю жизнь, возможно, некоторые свойства меняются (например, цвет ваших волос ;-)). Конечно, вы можете предположить, что если у вас есть две фотографии, одна с каштановыми волосами, другая с седыми, то вы можете быть моложе на фотографии с коричневыми волосами. Но, может быть, вы покрасили волосы? Проблема в том, что вы можете знать, что вы покрасили волосы. Могут другие? Чтобы поместить это в действительный контекст, вы должны ввести свойство age (версию). Тогда вы семантически откровенны и однозначны.
Чтобы избежать скрытой операции «замена старого на новый объект», в Set не должно быть метода get. Если вам нужно такое поведение, вы должны сделать его явным, удалив старый объект и добавив новый объект.
Кстати: что это должно означать, если вы передаете объект, равный объекту, который вы хотите получить? Это не имеет смысла. Держите семантику в чистоте и не делайте этого, хотя технически никто не будет вам мешать.
источник
В частности, в Java
HashSet
изначально был реализован с использованием вHashMap
любом случае, и просто игнорируя значение. Таким образом, первоначальный дизайн не предполагал каких-либо преимуществ в предоставлении метода getHashSet
. Если вы хотите сохранить и извлечь каноническое значение среди различных объектов, которые равны, то вы просто используетеHashMap
сами.Я не был в курсе таких подробностей реализации, поэтому не могу сказать, применимы ли эти рассуждения в полной мере в Java, не говоря уже о C # и т. Д. Но даже если бы
HashSet
было переопределено использовать меньше памяти, чемHashMap
, в любом случае, было бы серьезным изменением добавить новый метод вSet
интерфейс. Так что это довольно большая боль для выгоды, которую не все считают достойной.источник
default
непрерывной работы. Это просто не кажется очень полезным изменением.O(n)
сравнениях, даже если хеш-функция дает хорошее распределение. Тогда реализацииSet
этого переопределения реализации по умолчанию в интерфейсе, в том числеHashSet
, могут дать лучшую гарантию.Существует основной язык, набор которого имеет свойство, которое вы хотите.
В C ++
std::set
это упорядоченный набор. У него есть.find
метод, который ищет элемент на основе предоставленного вами оператора упорядочения<
или двоичнойbool(T,T)
функции. Вы можете использовать find для реализации нужной вам операции get.Фактически, если
bool(T,T)
указанная вами функция имеет определенный флаг (is_transparent
), вы можете передавать объекты другого типа, для которых функция имеет перегрузки. Это означает, что вам не нужно вставлять «пустые» данные во второе поле, просто убедитесь, что используемая вами операция упорядочения может упорядочивать между поиском и вложенными типами.Это позволяет эффективно:
где
my_string_compare
понимает, как упорядочить целые числа и строки без предварительного преобразования целого числа в строку (с потенциальной ценой).Для
unordered_set
(хеш-набор C ++) не существует эквивалентного прозрачного флага (пока). Вы должны перейтиT
кunordered_set<T>.find
методу. Его можно добавить, но для хэшей требуется==
и хеш, в отличие от упорядоченных наборов, которые просто требуют упорядочения.Общий шаблон заключается в том, что контейнер выполнит поиск, а затем предоставит вам «итератор» для этого элемента в контейнере. В какой момент вы можете получить элемент в наборе или удалить его и т. Д.
Короче говоря, не у всех стандартных контейнеров есть недостатки, которые вы описываете. Контейнеры, основанные на итераторах стандартной библиотеки C ++, отсутствуют, и, по крайней мере, некоторые из контейнеров существовали раньше, чем любой из других языков, которые вы описали, и возможность сделать получение еще эффективнее, чем вы описали, была даже добавлена. Нет ничего плохого в вашем дизайне или желании этой операции; дизайнеры наборов, которые вы используете, просто не предоставили этот интерфейс.
Стандартные контейнеры C ++, предназначенные для чистой обертки низкоуровневых операций эквивалентного свернутого вручную кода C, который был разработан, чтобы соответствовать тому, как вы могли бы эффективно написать его в сборке. Его итераторы являются абстракцией указателей в стиле C. Все языки, о которых вы упомянули, отошли от указателей как понятия, поэтому они не использовали абстракцию итератора.
Возможно, тот факт, что C ++ не имеет этого недостатка, является случайностью дизайна. Путь, ориентированный на итератор, означает, что для взаимодействия с элементом в ассоциативном контейнере сначала нужно получить итератор для элемента, а затем использовать этот итератор для обсуждения записи в контейнере.
Стоимость состоит в том, что есть правила аннулирования итерации, которые вы должны отслеживать, и некоторые операции требуют 2 шага вместо одного (что делает клиентский код более шумным). Преимущество заключается в том, что надежная абстракция позволяет более расширенное использование, чем те, которые изначально задумывались дизайнерами API.
источник