В чем разница между разными типами Dictionary?

@ht1515 · Регистрация: 31.01.2010

Студворк — интернет-сервис помощи студентам

https://msdn.microsoft.com/ru-... .120).aspx
Три типа Dictionary. В чем между ними разница?
Зачем три?

HashSet<T> Это тупо список уникальных значений, так? Ключа нет ж.

Получается хеш в дотнете реализует только Dictionary?

Можете помочь разобраться с переопределение getHashCode и Equils.
Не понимаю если таблица ключей массив, то он ж ограничен должен быть, а если хешкод - как индекс массива выйдет за пределы массива? Если например хеш код уже такой сушествует, тогда на элементе массива делают список типа ключ-хешкод, так?

nimazzzy · 20.01.2017, 17:02

Сообщение от ht1515

Не понимаю если таблица ключей массив, то он ж ограничен должен быть

Так и есть, он ограничен.

Сообщение от ht1515

а если хешкод - как индекс массива выйдет за пределы массива?

Нет, в самом простом "классическом" случае, хэш-код делится на размер массива и берется остаток от деления в качестве индекса.

Сообщение от ht1515

Если например хеш код уже такой сушествует, тогда на элементе массива делают список типа ключ-хешкод, так?

Все зависит от реализации. Хэши могут и без списка работать. А список - ключ-значение, хэш хранить там не за чем.

@Usaga · 20.01.2017, 19:22

ht1515, с устройством "словаря" ты можешь ознакомиться самостоятельно тут. Это в чистом виде хеш-таблица (гугл в помощь).

@ht1515 · 20.01.2017, 20:25 **[ТС]**

метод цепочек (метод прямого связывания);
метод открытой адресации.

это из вики. Борьба с коллизиями.

Вот получается 1 это тупо связный список. То есть в ячейке массива я делаю структуру связного списка, в ней указатель на след элемент и тд...

А в случае

метод открытой адресации.

не массив наверно используется а список и пары ключ- хешкод записываются в список и потом тупо перебором ищутся. Я прав?

Usaga, спасибо, лето в отпуске почитаю. Сейчас ноль времени вообще...

@Usaga · 21.01.2017, 04:16

ht1515, мне кажется, что раз вопрос устройства словаря тебя интересует уже сейчас, то и изучить его исходник можно сейчас, благо, что на это пары часов хватит.

@ht1515 · 21.01.2017, 12:11 **[ТС]**

Usaga, Да, хорошо. А вы с ни разбирались? С Вами проконсулььтироваться можно?

Вот функция поиска вхождения ключа

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
private int FindEntry(TKey key) {
            if( key == null) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
 
            if (buckets != null) {
                int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
                for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
                    if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
                }
            }
            return -1;
        }

Как я понял тут они используют баскет - корзины.
То есть массив хеш кодов делят на баскеты и сканят нужны.... Жаль я надеялся на магию.

Все равно перебор только не O(N), а O(N/M)
где M - количество баскетов

ТАк?

@Usaga · 21.01.2017, 13:02

ht1515, да, там есть перебор. Но dictionary старается поддерживать размер массива бакетов таким, чтобы количество бакетов было не меньше количества хранящихся объектов. Плюс Dictionary отслеживает ситуацию, когда в одном бакете хранится слишком много объктов. Тогда таблица бакетов также перестраивается. Поэтому перебор тебя смущать не должен.

Посмотри на метод Insert.

nimazzzy · 21.01.2017, 15:40

Сообщение от ht1515

Все равно перебор только не O(N), а O(N/M)
где M - количество баскетов

О это не про количество элементов или баскетов, а про то, как меняется поведение алгоритма в зависимости от размера входных данных. Допустим, что алгоритм хэш таблицы, не дает наполнятся списку больше 5 элементов, делает пересчет. То есть, худший сценарий - O(N), 5 проходов по списку. На сколько бы большой на была таблица, будут все те же пять проходов - O(N).

@TopLayer · 21.01.2017, 16:12

nimazzzy, можно подобрать входные данные так, что хэш таблица будет работать очень медленно, это вы хотели услышать?

nimazzzy · 21.01.2017, 21:49

Не по теме:

Сообщение от TopLayer

это вы хотели услышать?

С чего ты взял, что я что-то хотел услышать?

@ht1515 · 21.01.2017, 22:58 **[ТС]**

Usaga, почитал статью американца ... блин потерял ссылку... Вообщем, он говорит что переопределять свой GetHashCode, а соответственно Equils - сложное дело. Нужно добиться правильной балансировки между бекитами (неправильно прочитал их, называл баскетами - корзинами).

Как вы думаете, вот те кто у объектов их переопределяет, ну скажем в фирмах каких-то, они матан знают? Смогут получить хорошее распределение по бекитам? Просто так и в O(n) в конечно итоге можно прийти, а словарик нам ну если не O(1) дает, то мы тихо мечтаем об этом...

@TopLayer · 21.01.2017, 23:44

nimazzzy, не к тому обратился. Сообщение было для ht1515. Ошибся.

nimazzzy · 21.01.2017, 23:55

Не по теме:

TopLayer, я тоже ошибся. Писал в сообщении O(N). Конечно, O(1) там имел в виду.

@Storm23 · 22.01.2017, 11:54

Сообщение от ht1515

Как вы думаете, вот те кто у объектов их переопределяет, ну скажем в фирмах каких-то, они матан знают? Смогут получить хорошее распределение по бекитам? Просто так и в O(n) в конечно итоге можно прийти, а словарик нам ну если не O(1) дает, то мы тихо мечтаем об этом...

Все это фантазии. Dictionary прекрасно работает, и доступ у него O(1). И переопределять GetHashCode тоже не сложно.
Для сравнения создайте список List<int> на сотню миллионов элементов и сделайте Dictionary<int,int>(или HashSet<int>) и сравните скорость поиска элементов в них. Увидите, что никаких O(n) в словаре нет.
Что касается GetHashCode то тут тоже проблем нет. Обычно пользовательский объект имеет какое либо поле, которое является идентификатором. Тогда в GetHashCode просто возвращаем хешкод идентификатора:

C#
1
2
3
4
public override int GetHashCode()
{
   return Id.GetHashCode();
}

Аналогично, в Equals просто сравниваем идентификаторы.
Конечно бывают вырожденные случаи, когда в Dictionary падает производительность, но это далеко не ординарное событие, и обычно вызвано криворукостью в переопределенном GetHashCode.

Сообщение от ht1515

Получается хеш в дотнете реализует только Dictionary?

В дотнете есть масса классов, реализующих быстрый доступ по ключу в том или ином виде:

Hashtable
HashSet<>
Dictionary<>
SortedList<>
SortedDictionary<>
ConcurrentDictionary<>

@ht1515 · 22.01.2017, 18:14 **[ТС]**

Сообщение от Storm23

Для сравнения создайте список List<int> на сотню миллионов элементов и сделайте Dictionary<int,int>(или HashSet<int>) и сравните скорость поиска элементов в них. Увидите, что никаких O(n) в словаре нет.
Что касается GetHashCode то тут тоже проблем нет.

Так считать O(n) нельзя. Это асимптотическая сложность алгоритма... Абстрактная величина, абстрагированная от идеального вычислителя. Авторы абстрагируются от всяких Intel core I7, спарков и тд
Короче, таким образом (запустить и проверить) судить об алгоритме нельзя

Сообщение от Storm23

Обычно пользовательский объект имеет какое либо поле, которое является идентификатором. Тогда в GetHashCode просто возвращаем хешкод идентификатора:

Обычно? Я не знаю какие объект будут в хеши, поэтому нам и дают право переопределить наверно гетхешкод и иквелс.
От типа объектов очень много зависит. А насчет идентификатора объекта, не у все так архитектура объектов построена, что они придумывают их номер...
Н-р вытащенные строки из БД и взятый у них ID, можно это считать примеро?

@Usaga · 22.01.2017, 18:48

ht1515, не нужно быть дофига математиком, чтобы породить хеш-код контретного объекта. Всё что от тебя требуется - чтобы полученный хеш выглядел как настоящий и отвечал простым требованиям: быть одинаковым для одинаковых объектов и, по возможности, сильно отличаться для разных объектов. Некой комбинации результатов вызова метода GetHashCode() полей класса входящих в критерии сравнения объектов вполне будет достаточно.

@ht1515 · 22.01.2017, 19:34 **[ТС]**

https://blogs.msdn.microsoft.c... 03/20/943/

Я знаю это из своего глубокого, личного и очень болезненного опыта. Более десяти лет назад я написал алгоритм хеширования строк для хеш-таблицы, используемой серверами msn.com. Я думал, что распределение значений является достаточно случайным, но я допустил ошибку, и это оказалось не так. Выяснилось, что все сто тысяч строк длиной 5 и содержащие только цифры, всегда помещались в один из пяти сегментов вместо шестиста доступных. Ребята из msn.com использовали мою хеш-таблицу для быстрого поиска среди десяти тысяч почтовых индексов, каждый из которых был строкой из пяти цифр. Эта проблема, а также ошибка, связанная с многопоточностью, полностью накрыла производительность важной страницы сайта msn.com; было очень стыдно и это стоило кучу денег. Данные иногда могут быть сильно сгруппированными и хороший алгоритм хеширования должен принимать это во внимание.

@Usaga · 22.01.2017, 19:41

ht1515, и?

@ht1515 · 22.01.2017, 20:15 **[ТС]**

Сообщение от Usaga

ht1515, и?

Сообщение от Usaga

ht1515, не нужно быть дофига математиком, чтобы породить хеш-код контретного объекта. Всё что от тебя требуется - чтобы полученный хеш выглядел как настоящий и отвечал простым требованиям: быть одинаковым для одинаковых объектов и, по возможности, сильно отличаться для разных объектов. Некой комбинации результатов вызова метода GetHashCode() полей класса входящих в критерии сравнения объектов вполне будет достаточно.

Ну породить то можно легко, автор статьи говорит что балансировка должна быть равномерной по всему хеш массиву, ваш хеш код - индекс, ну и надо чтобы норм он распределялся

Storm23, например предлагает просто идентификатор использовать объекта. Ну ок, вроде норм, если есть такая возможность.
Просто имхо могут быть случаи в которых хеш код ищут не так просто.

Просто если все делать по принципу что у объекта будет ИД и хеш код будет ИД, то нафиг микрософт выдал его нам для переопределения? имхо потому что объекты могут быть разными и предметная область может быть разной и ... ну я не могу придумать сейчас ситуации такой, опыта нет, помогите придумать... и в такой ситуации нужно придумать свой алгоритм.

Кстати O(n) это максимально плохой случай, это например

C#
1
2
3
4
public override int GetHashCode()
{
   return 10;
}

@Usaga · 23.01.2017, 07:37

ht1515, ты не сможешь добиться равномерного распределения элементов в хеш-таблице потому, что это самое распределение зависит от количества элементов хранящихся в таблице. Всё что ты сможешь сделать - сделать хеш убедительно разным для разных объектов и не париться так сильно этим.

Ну а пример автора выше - не пример, там человек дикий косяк допустил, раз у него сотня тысяч записей один и тот же хеш имела. Даже простейший XOR над всеми символами строки дал бы что-то очень похожее на хеш.

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@ht1515 шарпопочитатель 59 / 26 / 7 Регистрация: 31.01.2010 Сообщений: 1,035

	В чем разница между разными типами Dictionary? 20.01.2017, 16:21. Показов 8231. Ответов 24 Метки нет (Все метки) https://msdn.microsoft.com/ru-... .120).aspx Три типа Dictionary. В чем между ними разница? Зачем три? HashSet<T> Это тупо список уникальных значений, так? Ключа нет ж. Получается хеш в дотнете реализует только Dictionary? Можете помочь разобраться с переопределение getHashCode и Equils. Не понимаю если таблица ключей массив, то он ж ограничен должен быть, а если хешкод - как индекс массива выйдет за пределы массива? Если например хеш код уже такой сушествует, тогда на элементе массива делают список типа ключ-хешкод, так? 0

@Usaga 14100 / 9317 / 1349 Регистрация: 21.01.2016 Сообщений: 34,993
	20.01.2017, 19:22
	ht1515, с устройством "словаря" ты можешь ознакомиться самостоятельно тут. Это в чистом виде хеш-таблица (гугл в помощь). 0

@Usaga 14100 / 9317 / 1349 Регистрация: 21.01.2016 Сообщений: 34,993
	21.01.2017, 04:16
	ht1515, мне кажется, что раз вопрос устройства словаря тебя интересует уже сейчас, то и изучить его исходник можно сейчас, благо, что на это пары часов хватит. 0

@Usaga 14100 / 9317 / 1349 Регистрация: 21.01.2016 Сообщений: 34,993
	21.01.2017, 13:02
	ht1515, да, там есть перебор. Но dictionary старается поддерживать размер массива бакетов таким, чтобы количество бакетов было не меньше количества хранящихся объектов. Плюс Dictionary отслеживает ситуацию, когда в одном бакете хранится слишком много объктов. Тогда таблица бакетов также перестраивается. Поэтому перебор тебя смущать не должен. Посмотри на метод Insert. 1

@TopLayer 907 / 664 / 318 Регистрация: 23.10.2016 Сообщений: 1,543
	21.01.2017, 16:12
	nimazzzy, можно подобрать входные данные так, что хэш таблица будет работать очень медленно, это вы хотели услышать? 0

@ht1515 шарпопочитатель 59 / 26 / 7 Регистрация: 31.01.2010 Сообщений: 1,035
	21.01.2017, 22:58 [ТС]
	Usaga, почитал статью американца ... блин потерял ссылку... Вообщем, он говорит что переопределять свой GetHashCode, а соответственно Equils - сложное дело. Нужно добиться правильной балансировки между бекитами (неправильно прочитал их, называл баскетами - корзинами). Как вы думаете, вот те кто у объектов их переопределяет, ну скажем в фирмах каких-то, они матан знают? Смогут получить хорошее распределение по бекитам? Просто так и в O(n) в конечно итоге можно прийти, а словарик нам ну если не O(1) дает, то мы тихо мечтаем об этом... 0

@TopLayer 907 / 664 / 318 Регистрация: 23.10.2016 Сообщений: 1,543
	21.01.2017, 23:44
	nimazzzy, не к тому обратился. Сообщение было для ht1515. Ошибся. 0

nimazzzy
	21.01.2017, 23:55
	Не по теме: TopLayer, я тоже ошибся. Писал в сообщении O(N). Конечно, O(1) там имел в виду. 0

@Usaga 14100 / 9317 / 1349 Регистрация: 21.01.2016 Сообщений: 34,993
	22.01.2017, 18:48
	ht1515, не нужно быть дофига математиком, чтобы породить хеш-код контретного объекта. Всё что от тебя требуется - чтобы полученный хеш выглядел как настоящий и отвечал простым требованиям: быть одинаковым для одинаковых объектов и, по возможности, сильно отличаться для разных объектов. Некой комбинации результатов вызова метода GetHashCode() полей класса входящих в критерии сравнения объектов вполне будет достаточно. 0

@Usaga 14100 / 9317 / 1349 Регистрация: 21.01.2016 Сообщений: 34,993
	22.01.2017, 19:41
	ht1515, и? 0

@Usaga 14100 / 9317 / 1349 Регистрация: 21.01.2016 Сообщений: 34,993
	23.01.2017, 07:37
	ht1515, ты не сможешь добиться равномерного распределения элементов в хеш-таблице потому, что это самое распределение зависит от количества элементов хранящихся в таблице. Всё что ты сможешь сделать - сделать хеш убедительно разным для разных объектов и не париться так сильно этим. Ну а пример автора выше - не пример, там человек дикий косяк допустил, раз у него сотня тысяч записей один и тот же хеш имела. Даже простейший XOR над всеми символами строки дал бы что-то очень похожее на хеш. 0