Comments 26
ээээ… под кат засунте пожалуйста…
Добавьте плиз, что ключевое — это имплементация GetHashCode из IEqualityComparer, а не переопределение GetHashCode объекта, т.к. во втором случае словарь будет работать неправильно.
И да, в .NET блоге это будет лучше смотреться ;) Возможность перенести у вас есть
Рекомендую прочитать(посмотреть соответствующие главы) книгу Effective C# Била Вагнера. Там о подобных вещах хорошо написано.
«Так как GetHashCode при сравнении имеет больший приоритет перед Equals»
«Наверное такое поведение было сделано для улучшения производительности. „
по-моему автор не совсем представляет что такое хеш-таблица, почему, зачем и как она устроена.
«Наверное такое поведение было сделано для улучшения производительности. „
по-моему автор не совсем представляет что такое хеш-таблица, почему, зачем и как она устроена.
В этих строках имеется в виду порядок вызова методов.
Или вы хотите сказать что в .NET System.Object или List это хеш-таблицы?
Или вы хотите сказать что в .NET System.Object или List это хеш-таблицы?
я хочу сказать, что хэш-таблица — это совершенно определенным образом (вообще, т.е. безотносительно .net) устроенная структура данных, из свойств которой очевидно следуют все те выводы, к которым вы пришли, и еще некоторые другие.
вы же, предлагая читателю недопустимые определения «наверное такое поведение было сделано» и прочее, вводите последнего в заблуждение относительно устройства мира, демонстрируя параллельно незнание фундаментальных вещей из области алгоритмов и структур данных.
верные выводы на катастрофически неверном материале и на фантастических же предположениях — это путь в полное никуда.
вы же, предлагая читателю недопустимые определения «наверное такое поведение было сделано» и прочее, вводите последнего в заблуждение относительно устройства мира, демонстрируя параллельно незнание фундаментальных вещей из области алгоритмов и структур данных.
верные выводы на катастрофически неверном материале и на фантастических же предположениях — это путь в полное никуда.
Я вообще-то веду речь об переопределении метода GetHashCode, Equals и потому что в нем фигурирует слово хеш еще не значит что это хеш таблица на примере обычного списка List<T> (берем общий случай IEnumerable), повторюсь List — обычный список, массив если хотите, размер которого меняется динамически. Скажите массив — это хеш таблица или нет?
Да если очень внимательно читать МСДН то сразу все станет ясно, но как показывает практика подобную описанную ошибку делают многие и она касается не хеш-таблицы как таковой а переопределения методов GetHashCode и Equals и почему Equals не вызывается как ожидают многие разработчики, особенно начинающие.
Как раз материал и построен относительно .net.
Да если очень внимательно читать МСДН то сразу все станет ясно, но как показывает практика подобную описанную ошибку делают многие и она касается не хеш-таблицы как таковой а переопределения методов GetHashCode и Equals и почему Equals не вызывается как ожидают многие разработчики, особенно начинающие.
Как раз материал и построен относительно .net.
вы мне прокомментируйте предложение из вашего поста: «Наверное такое поведение было сделано для улучшения производительности», а то мне как-то не хватает фактического материала продолжить дискуссию.
А Equals не вызывается, потому что эти многие разработчики не знают, что такой хэш-таблица. И .Net тут, ну поверьте, совершенно не при чем. Ну, вот ни разу. Даже приблизительно. И даже MSDN не при чем, в котором конечно же ни слова про то, что такое хэш-таблица нет.
А Equals не вызывается, потому что эти многие разработчики не знают, что такой хэш-таблица. И .Net тут, ну поверьте, совершенно не при чем. Ну, вот ни разу. Даже приблизительно. И даже MSDN не при чем, в котором конечно же ни слова про то, что такое хэш-таблица нет.
Вот я как-то не могу уловить вашу мысль по поводу хеш-таблиц и связи с Equals.
Может вместо ваших реплик об устройстве мира все таки опишите в чем причина, да и закроем этот вопрос?
Может вместо ваших реплик об устройстве мира все таки опишите в чем причина, да и закроем этот вопрос?
хэш-код используется в хэш-таблицах для быстрого поиска элементов
хэш-таблицы устроены таким образом, что у равных элементов должен быть одинаковый хэш-код
хэш-код не должен меняться в течении жизни объекта
все. и никаких оптимизаций, приоритетов, улучшений производительности и связи с .Net
это элементарные алгоритмические вещи
хэш-таблицы устроены таким образом, что у равных элементов должен быть одинаковый хэш-код
хэш-код не должен меняться в течении жизни объекта
все. и никаких оптимизаций, приоритетов, улучшений производительности и связи с .Net
это элементарные алгоритмические вещи
Object — это пустой объект
List — это список
Хэш-таблица — это хэш-таблица
Массив — это массив
GetHashCode — метод, возвращающий хэш-код данного объекта
и возьмите Кнута или книжку с осликами и прочитайте, что такое хэш-таблица, зачем в ней хэш-код и все прочие сопутствующие штуки
List — это список
Хэш-таблица — это хэш-таблица
Массив — это массив
GetHashCode — метод, возвращающий хэш-код данного объекта
и возьмите Кнута или книжку с осликами и прочитайте, что такое хэш-таблица, зачем в ней хэш-код и все прочие сопутствующие штуки
Так вот, если бы вы внимательно почитали то Hashtable и Dictionary в коде статьи не присутствует. Да такое поведние как есть связано с принципом их работы о чем и указываеться в тексте.
Но причем хеш-таблица к List, массиву, Object. Или если мы переопределяем метод Object.GetHashCode — то Object — тоже хеш таблица.
Повторяюсь суть статьи об переопределении методов GetHashCode, Equals.
Но причем хеш-таблица к List, массиву, Object. Или если мы переопределяем метод Object.GetHashCode — то Object — тоже хеш таблица.
Повторяюсь суть статьи об переопределении методов GetHashCode, Equals.
1) Вы все-таки определитесь, присутствуют они в тексте статьи или не присутствуют, я про Hashtable и Dictionary, и вообще все контейнеры на основе хэш-таблиц.
2) хэш-таблица у вас есть в методе Intersect (это, конечно, детали реализации, но IEqualityComparer в любом случае должен быть консистентным)
3) Вы все-таки не понимаете и не прочитали, что такое хэш-таблица. GetHashCode — метод возвращающий хэш-код объекта. Хэш-таблица — это характеристика контейнера, а не объекта. Если вы переопределяете GetHashCode, то вы переопределяете хэш-код объекта. Будите ли вы его складывать в хэш или нет — это уже следующий этап. Но сам метод GetHashCode подразумевает совершенно единственное его применение — возвращение хэш-кода для хэшей. Все, если метод возвращает лабуду, то хэши не работают, что ваш пример и демонстрирует.
И к .Net это вообще не имеет отношения. Это фундаментальное свойство хэш-контейнетров.
У вас же в голове какой-то безумный мусор из всех понятий.
2) хэш-таблица у вас есть в методе Intersect (это, конечно, детали реализации, но IEqualityComparer в любом случае должен быть консистентным)
3) Вы все-таки не понимаете и не прочитали, что такое хэш-таблица. GetHashCode — метод возвращающий хэш-код объекта. Хэш-таблица — это характеристика контейнера, а не объекта. Если вы переопределяете GetHashCode, то вы переопределяете хэш-код объекта. Будите ли вы его складывать в хэш или нет — это уже следующий этап. Но сам метод GetHashCode подразумевает совершенно единственное его применение — возвращение хэш-кода для хэшей. Все, если метод возвращает лабуду, то хэши не работают, что ваш пример и демонстрирует.
И к .Net это вообще не имеет отношения. Это фундаментальное свойство хэш-контейнетров.
У вас же в голове какой-то безумный мусор из всех понятий.
По моему, вы сильно перевозбудились от этих хэшей, ложитесь лучше спать :)
1) 2)Итак в код наведенном в статье присутствует хеш таблица? Нет. Что запрятано за кулисами CLR это одно, именно по этому и написано «связано с принципом работы HashTable и Dictionary», потому что для IEqualityComparer он за кулисами и используется «скорее всего». Опять придеретесь к «скорее всего»? Я так написал потому что кода CLR нет. Возьмите рефлектор повыдирайте куски и когда найдете их и покажете, я тогда исправлю на 100% там используется хеш-таблица.
List, IEnumerable — не хеш теблицы, а вот чтобы правильно отрабатывала операция и IEqualityComparer приведен.
Давайте еще такой вариант расcмотрим — System.Object у него GetHashCode — хеш-код для алгоритмов хеширования? нет. Читайте МСДН. Не везде где есть GetHashCode метод есть хеш-таблица. Вот строка из МСДН:
Consequently, the default implementation of this method [Object.GetHashCode] must not be used as a unique object identifier for hashing purposes.
List, IEnumerable — не хеш теблицы, а вот чтобы правильно отрабатывала операция и IEqualityComparer приведен.
Давайте еще такой вариант расcмотрим — System.Object у него GetHashCode — хеш-код для алгоритмов хеширования? нет. Читайте МСДН. Не везде где есть GetHashCode метод есть хеш-таблица. Вот строка из МСДН:
Consequently, the default implementation of this method [Object.GetHashCode] must not be used as a unique object identifier for hashing purposes.
1) Во-первых, хэш-таблица эта основной (и единственный известный широкой публике) метод проверить наличие элемента в массиве за O(1). Во-вторых, исходники фреймворка конечно же есть и свободно доступны почти в полном виде:
public static IEnumerable<TSource> Intersect<TSource>([NotNull] this IEnumerable<TSource> first, [NotNull] IEnumerable<TSource> second, [CanBeNull] IEqualityComparer<TSource> comparer)
{
if (first == null)
throw new ArgumentNullException(«first»);
if (second == null)
throw new ArgumentNullException(«second»);
return IntersectImpl(first, second, comparer);
}
private static IEnumerable<TSource> IntersectImpl<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
var secondSet = new HashSet<TSource>(second, comparer);
foreach (var element in first)
{
if (secondSet.Remove(element))
yield return element;
}
}
2) В том куске MSDN, который вы выдрали из контекста, написано только лишь то, что реализация GetHashCode _по-умолчанию_ из Object — плохая реализация, потому что не даст в итоге должного распределения, и приведет к операции поиска стоимостью O(N).
И там же: The GetHashCode method is suitable for use in hashing algorithms and data structures such as a hash table.
И во всем фреймворке этот метод используется именно и только так.
public static IEnumerable<TSource> Intersect<TSource>([NotNull] this IEnumerable<TSource> first, [NotNull] IEnumerable<TSource> second, [CanBeNull] IEqualityComparer<TSource> comparer)
{
if (first == null)
throw new ArgumentNullException(«first»);
if (second == null)
throw new ArgumentNullException(«second»);
return IntersectImpl(first, second, comparer);
}
private static IEnumerable<TSource> IntersectImpl<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
var secondSet = new HashSet<TSource>(second, comparer);
foreach (var element in first)
{
if (secondSet.Remove(element))
yield return element;
}
}
2) В том куске MSDN, который вы выдрали из контекста, написано только лишь то, что реализация GetHashCode _по-умолчанию_ из Object — плохая реализация, потому что не даст в итоге должного распределения, и приведет к операции поиска стоимостью O(N).
И там же: The GetHashCode method is suitable for use in hashing algorithms and data structures such as a hash table.
И во всем фреймворке этот метод используется именно и только так.
Если доступны то дайте ссылку. Отладочные символы и рефлектор — это недоступные сорсы. Рефлектор по сути дизассемблер.
Я вот не пойму чего вы добиваетесь?
Да статья не про хеш-таблицы. Тем не менее все упоминания соблюдены. Ну так если вы очень хотите, напишите про хеш-таблицы, конечно статья уже есть в википедии, но будет еще и на хабре.
Я вот не пойму чего вы добиваетесь?
Да статья не про хеш-таблицы. Тем не менее все упоминания соблюдены. Ну так если вы очень хотите, напишите про хеш-таблицы, конечно статья уже есть в википедии, но будет еще и на хабре.
1) Я знаю, что такое Рефлектор. Исходники фрейморка же доступны через MS Source Server: Tools -> Options -> Debuggings -> General -> Enable Source server support ну и далее в хелп, про то как этим пользоваться.
2) Я добивась того, чтобы вы либо исправили, либо удалили безграмотную статью. А безграмотна он ересью, которую я процитировал в самом начале:
«Так как GetHashCode при сравнении имеет больший приоритет перед Equals»
«Наверное такое поведение было сделано для улучшения производительности»
Вы делаете выводы при совершенном незнакомстве с базовыми вещами и при полном непонимании процессов, которые происходят внутри.
2) Я добивась того, чтобы вы либо исправили, либо удалили безграмотную статью. А безграмотна он ересью, которую я процитировал в самом начале:
«Так как GetHashCode при сравнении имеет больший приоритет перед Equals»
«Наверное такое поведение было сделано для улучшения производительности»
Вы делаете выводы при совершенном незнакомстве с базовыми вещами и при полном непонимании процессов, которые происходят внутри.
Я думал что холливар бывает между линуксоидами и не линуксоидами :) А оказывается и здесь ересь.
Значится так все необходимые упоминания соблюдены.
Строка «Так как GetHashCode при сравнении имеет больший приоритет перед Equals» подразумевает порядок вызова методов. Чтобы в ее не извращали добавлю приписку «в порядке вызова методов»
«Наверное такое поведение было сделано для улучшения производительности» — строку я для вас убрал. А то вы спать не можете.
«Вы делаете выводы… » — это ваше личное мнение.
Вы прицепились к двум строчкам и пытаетесь удалить статью. И при том что в статье изначально указано упоминание «Это связано с принципом работы HashTable и Dictionary». Напоминаю статья не о хеш-таблицах, поэтому о них здесь упоминанием и ограничится.
Хотите больше, пишите. Охотно почитаю и потроллю у вас в камментах.
Значится так все необходимые упоминания соблюдены.
Строка «Так как GetHashCode при сравнении имеет больший приоритет перед Equals» подразумевает порядок вызова методов. Чтобы в ее не извращали добавлю приписку «в порядке вызова методов»
«Наверное такое поведение было сделано для улучшения производительности» — строку я для вас убрал. А то вы спать не можете.
«Вы делаете выводы… » — это ваше личное мнение.
Вы прицепились к двум строчкам и пытаетесь удалить статью. И при том что в статье изначально указано упоминание «Это связано с принципом работы HashTable и Dictionary». Напоминаю статья не о хеш-таблицах, поэтому о них здесь упоминанием и ограничится.
Хотите больше, пишите. Охотно почитаю и потроллю у вас в камментах.
Да легко.
1) Почему у вас в CustomType не переопределен метод GetHashCode?
Особенно в свете (в первом варианте)
public int GetHashCode(CustomType obj)
{
return obj.GetHashCode();
}
Это ж будет жуткий втык.
2) А вы считаете, что две Оли с разными возрастами — это одна Оля? Пример конечно же в таком случае удачнейший, из реальной жизни, и прозрачный.
3) И это не холивар. Вы маскируете под кажущейся простотой и очевидностью важные вещи. Крадя у ума пищу и провоцируя будущие ошибки у наивного читателя.
4) И вы делаете выводы. Вы ж целую статью выводов из своих наблюдений написали.
5) Если вы нормально напишите о применимости метода GetHashCode, а он применяется в хеш-таблицах и больше почти нигде, то статья будет вменяемая.
А вся эта лабуда про приоритеты — это ж кто-то подумает, что объекты с равными хэш-кодами считаются равными. Никакого приоритета в сравнении нет, и GetHashCode используется не для сравнения, а для поиска.
И потом, кто мешает возвращать в GetHashCode констунту? И как правильно переопределять GetHashCode, если он дожен считаться для группы полей?
1) Почему у вас в CustomType не переопределен метод GetHashCode?
Особенно в свете (в первом варианте)
public int GetHashCode(CustomType obj)
{
return obj.GetHashCode();
}
Это ж будет жуткий втык.
2) А вы считаете, что две Оли с разными возрастами — это одна Оля? Пример конечно же в таком случае удачнейший, из реальной жизни, и прозрачный.
3) И это не холивар. Вы маскируете под кажущейся простотой и очевидностью важные вещи. Крадя у ума пищу и провоцируя будущие ошибки у наивного читателя.
4) И вы делаете выводы. Вы ж целую статью выводов из своих наблюдений написали.
5) Если вы нормально напишите о применимости метода GetHashCode, а он применяется в хеш-таблицах и больше почти нигде, то статья будет вменяемая.
А вся эта лабуда про приоритеты — это ж кто-то подумает, что объекты с равными хэш-кодами считаются равными. Никакого приоритета в сравнении нет, и GetHashCode используется не для сравнения, а для поиска.
И потом, кто мешает возвращать в GetHashCode констунту? И как правильно переопределять GetHashCode, если он дожен считаться для группы полей?
1) Потому что вы не шарите. Потому что для этого имплементирован IEqualityComparer. Не был бы имплементирован, пришлось бы оверрайдить. А про ваш «жуткий втык» который вы нашли, так он в статье подается как распространенная ошибка. Специально чтобы избежать двузначности добавил коммент в код
// распространенная ошибка, неверно
И вы хотите сказать что внимательно читали?
2) Пример вполне из жизни. Вам как опытному программисту я решил помочь абстрагироваться и поменял имена на марки машин. Не говорите теперь что пример не из жизни.
3)4) это ваша личная имха, которая вообще не аргумент. Видимо мой ответ что вы придерживаетесь к двум строчкам вас задел.
5) Согласен логично что GetHashCode применяется только там, но как же быть с реализацией GetHashCode из System.Object, она немного не вписывается в общую концепция. Так что не будьте так категоричны. В CLR благодаря System.Object существует некая двузначность, может стоило эти методы вообще убрать от туда и тех кто хочет использовать свои объекты в словарях и хеш-таблицах заставлять вручную реализовывать GetHashCode например из того же IEqualityComparer, ведь собственно так и происходит почти всегда.
5) Опять вы невнимательно читали ни статью ни мои ответы вам. Приоритетов нет. Приоритетами — так был назван порядок вызова методов GetHashCode и Equals. Потому что многие разработчики думают что Equals вызывается всегда — это ошибка и суть статьи была указать именно на нее. Я убрал это предложение чтобы не было больше двучтений.
По поводу «Если вы нормально напишите о применимости метода GetHashCode ...» я добавил ссылки, потому что незачем дублировать материал из википедии и мсдн.
// распространенная ошибка, неверно
И вы хотите сказать что внимательно читали?
2) Пример вполне из жизни. Вам как опытному программисту я решил помочь абстрагироваться и поменял имена на марки машин. Не говорите теперь что пример не из жизни.
3)4) это ваша личная имха, которая вообще не аргумент. Видимо мой ответ что вы придерживаетесь к двум строчкам вас задел.
5) Согласен логично что GetHashCode применяется только там, но как же быть с реализацией GetHashCode из System.Object, она немного не вписывается в общую концепция. Так что не будьте так категоричны. В CLR благодаря System.Object существует некая двузначность, может стоило эти методы вообще убрать от туда и тех кто хочет использовать свои объекты в словарях и хеш-таблицах заставлять вручную реализовывать GetHashCode например из того же IEqualityComparer, ведь собственно так и происходит почти всегда.
5) Опять вы невнимательно читали ни статью ни мои ответы вам. Приоритетов нет. Приоритетами — так был назван порядок вызова методов GetHashCode и Equals. Потому что многие разработчики думают что Equals вызывается всегда — это ошибка и суть статьи была указать именно на нее. Я убрал это предложение чтобы не было больше двучтений.
По поводу «Если вы нормально напишите о применимости метода GetHashCode ...» я добавил ссылки, потому что незачем дублировать материал из википедии и мсдн.
1) У вас новый перл в статье появился: «Поэтому если упаковать свой тип в Object и пытаться использовать его в словаре то ничего хорошего из этого не выйдет».
Я вот совершенно не понимаю, как можно упаковать свой тип в Object. Не подскажите?
2) Пример не из жизни, если вам надо получить множество всех машин, а не множество всех машин + случаный год выпуска, как у вас, то обычно пишут что-то такое: customTypeLongList.Select(x => x.Name).Intersect(customTypeShortList.Select(x => x.Name));
3) Про GetHashCode. Вообще, складываение в хэши — это настолько частая операция, особенно в бизнес-приложениях, что иметь для этого все под рукой — очень логичная задача. Более того, создавая отдельный специализированный comparer вы нарушаете инкапсуляцию, потому что только сам объект знает о своей внутренней структуре и знает как себя сравнивать на равенство и проч. (особенно это очевидно, когда у вас может быть несколько инстансов объекта, которые представляют один и тот же объект реального мира). И именно поэтому GetHashCode у Object никак не зависит от данных объекта, к тому же как вы будите считать тогда хэш-код, например, у узла графа или двунаправленного списка?
Внешний comparer бывает полезен, когда вы смотрите под объекты под разным углом, например: равенство и похожесть (похожие объекты вы, например, хотите на экране пользователю подсвечивать одним цветом).
Вы же в своем примере реализуете такой comparer похожести в самом объекте, что как бы намекает пользователю, что все машины с одинаковым названием и разным годом выпуска одинаковы. Это примерно как все Иван Петровчи — одно и то же лицо. Вот если бы у вас был внешний компарер (к тому же как смущающе выглядит new CustomType() в Intersect), который назывался как-нибудь типа OnlyNameComparer — было бы понятно и логично.
4) И ваш вариант:
public int GetHashCode(CustomType obj)
{
return string.Empty.GetHashCode();
}
Еще какой верный. Только он превратит операцию поиска в хэше из O(1) в O(n), со всеми вытекающими взрывами сложности сопряженных алгоритмов. Intersect, например, сразу станет занимать O(n^2). А это выстрелит в ногу уже на сотне элементов.
5) Если вы не далаете выводов, то зачем вы написали всю эту статью?
Я вот совершенно не понимаю, как можно упаковать свой тип в Object. Не подскажите?
2) Пример не из жизни, если вам надо получить множество всех машин, а не множество всех машин + случаный год выпуска, как у вас, то обычно пишут что-то такое: customTypeLongList.Select(x => x.Name).Intersect(customTypeShortList.Select(x => x.Name));
3) Про GetHashCode. Вообще, складываение в хэши — это настолько частая операция, особенно в бизнес-приложениях, что иметь для этого все под рукой — очень логичная задача. Более того, создавая отдельный специализированный comparer вы нарушаете инкапсуляцию, потому что только сам объект знает о своей внутренней структуре и знает как себя сравнивать на равенство и проч. (особенно это очевидно, когда у вас может быть несколько инстансов объекта, которые представляют один и тот же объект реального мира). И именно поэтому GetHashCode у Object никак не зависит от данных объекта, к тому же как вы будите считать тогда хэш-код, например, у узла графа или двунаправленного списка?
Внешний comparer бывает полезен, когда вы смотрите под объекты под разным углом, например: равенство и похожесть (похожие объекты вы, например, хотите на экране пользователю подсвечивать одним цветом).
Вы же в своем примере реализуете такой comparer похожести в самом объекте, что как бы намекает пользователю, что все машины с одинаковым названием и разным годом выпуска одинаковы. Это примерно как все Иван Петровчи — одно и то же лицо. Вот если бы у вас был внешний компарер (к тому же как смущающе выглядит new CustomType() в Intersect), который назывался как-нибудь типа OnlyNameComparer — было бы понятно и логично.
4) И ваш вариант:
public int GetHashCode(CustomType obj)
{
return string.Empty.GetHashCode();
}
Еще какой верный. Только он превратит операцию поиска в хэше из O(1) в O(n), со всеми вытекающими взрывами сложности сопряженных алгоритмов. Intersect, например, сразу станет занимать O(n^2). А это выстрелит в ногу уже на сотне элементов.
5) Если вы не далаете выводов, то зачем вы написали всю эту статью?
Sign up to leave a comment.
Сравниваешь по Equals подразумеваешь GetHashCode