шарпопочитатель
59 / 26 / 7
Регистрация: 31.01.2010
Сообщений: 1,035
|
|
1 | |
В чем разница между разными типами Dictionary?20.01.2017, 16:21. Показов 7332. Ответов 24
Метки нет (Все метки)
https://msdn.microsoft.com/ru-... .120).aspx
Три типа Dictionary. В чем между ними разница? Зачем три? HashSet<T> Это тупо список уникальных значений, так? Ключа нет ж. Получается хеш в дотнете реализует только Dictionary? Можете помочь разобраться с переопределение getHashCode и Equils. Не понимаю если таблица ключей массив, то он ж ограничен должен быть, а если хешкод - как индекс массива выйдет за пределы массива? Если например хеш код уже такой сушествует, тогда на элементе массива делают список типа ключ-хешкод, так?
0
|
20.01.2017, 16:21 | |
Ответы с готовыми решениями:
24
В чем разница между HashTable и Dictionary? Объясните, пожалуйста в чем разница между типами-значениями и ссылочными типами? Visual Studio, в чем разница между разными типами проектов? В чем разница между типами данных Integer и Long? |
Заблокирован
|
|
20.01.2017, 17:02 | 2 |
Так и есть, он ограничен.
Нет, в самом простом "классическом" случае, хэш-код делится на размер массива и берется остаток от деления в качестве индекса.
Все зависит от реализации. Хэши могут и без списка работать. А список - ключ-значение, хэш хранить там не за чем.
1
|
шарпопочитатель
59 / 26 / 7
Регистрация: 31.01.2010
Сообщений: 1,035
|
|
20.01.2017, 20:25 [ТС] | 4 |
Вот получается 1 это тупо связный список. То есть в ячейке массива я делаю структуру связного списка, в ней указатель на след элемент и тд... А в случае Usaga, спасибо, лето в отпуске почитаю. Сейчас ноль времени вообще...
0
|
12005 / 8329 / 1268
Регистрация: 21.01.2016
Сообщений: 31,424
|
|
21.01.2017, 04:16 | 5 |
ht1515, мне кажется, что раз вопрос устройства словаря тебя интересует уже сейчас, то и изучить его исходник можно сейчас, благо, что на это пары часов хватит.
0
|
шарпопочитатель
59 / 26 / 7
Регистрация: 31.01.2010
Сообщений: 1,035
|
||||||
21.01.2017, 12:11 [ТС] | 6 | |||||
Usaga, Да, хорошо. А вы с ни разбирались? С Вами проконсулььтироваться можно?
Вот функция поиска вхождения ключа
То есть массив хеш кодов делят на баскеты и сканят нужны.... Жаль я надеялся на магию. Все равно перебор только не O(N), а O(N/M) где M - количество баскетов ТАк?
0
|
12005 / 8329 / 1268
Регистрация: 21.01.2016
Сообщений: 31,424
|
|
21.01.2017, 13:02 | 7 |
ht1515, да, там есть перебор. Но dictionary старается поддерживать размер массива бакетов таким, чтобы количество бакетов было не меньше количества хранящихся объектов. Плюс Dictionary отслеживает ситуацию, когда в одном бакете хранится слишком много объктов. Тогда таблица бакетов также перестраивается. Поэтому перебор тебя смущать не должен.
Посмотри на метод Insert.
1
|
Заблокирован
|
|
21.01.2017, 15:40 | 8 |
О это не про количество элементов или баскетов, а про то, как меняется поведение алгоритма в зависимости от размера входных данных. Допустим, что алгоритм хэш таблицы, не дает наполнятся списку больше 5 элементов, делает пересчет. То есть, худший сценарий - O(N), 5 проходов по списку. На сколько бы большой на была таблица, будут все те же пять проходов - O(N).
0
|
907 / 664 / 318
Регистрация: 23.10.2016
Сообщений: 1,543
|
|
21.01.2017, 16:12 | 9 |
nimazzzy, можно подобрать входные данные так, что хэш таблица будет работать очень медленно, это вы хотели услышать?
0
|
|
21.01.2017, 21:49
#10
|
0
|
шарпопочитатель
59 / 26 / 7
Регистрация: 31.01.2010
Сообщений: 1,035
|
|
21.01.2017, 22:58 [ТС] | 11 |
Usaga, почитал статью американца ... блин потерял ссылку... Вообщем, он говорит что переопределять свой GetHashCode, а соответственно Equils - сложное дело. Нужно добиться правильной балансировки между бекитами (неправильно прочитал их, называл баскетами - корзинами).
Как вы думаете, вот те кто у объектов их переопределяет, ну скажем в фирмах каких-то, они матан знают? Смогут получить хорошее распределение по бекитам? Просто так и в O(n) в конечно итоге можно прийти, а словарик нам ну если не O(1) дает, то мы тихо мечтаем об этом...
0
|
907 / 664 / 318
Регистрация: 23.10.2016
Сообщений: 1,543
|
|
21.01.2017, 23:44 | 12 |
nimazzzy, не к тому обратился. Сообщение было для ht1515. Ошибся.
0
|
|
21.01.2017, 23:55
#13
|
Не по теме: TopLayer, я тоже ошибся. Писал в сообщении O(N). Конечно, O(1) там имел в виду.
0
|
22.01.2017, 11:54 | 14 | |||||
Все это фантазии. Dictionary прекрасно работает, и доступ у него O(1). И переопределять GetHashCode тоже не сложно.
Для сравнения создайте список List<int> на сотню миллионов элементов и сделайте Dictionary<int,int>(или HashSet<int>) и сравните скорость поиска элементов в них. Увидите, что никаких O(n) в словаре нет. Что касается GetHashCode то тут тоже проблем нет. Обычно пользовательский объект имеет какое либо поле, которое является идентификатором. Тогда в GetHashCode просто возвращаем хешкод идентификатора:
Конечно бывают вырожденные случаи, когда в Dictionary падает производительность, но это далеко не ординарное событие, и обычно вызвано криворукостью в переопределенном GetHashCode. В дотнете есть масса классов, реализующих быстрый доступ по ключу в том или ином виде: Hashtable HashSet<> Dictionary<> SortedList<> SortedDictionary<> ConcurrentDictionary<>
1
|
шарпопочитатель
59 / 26 / 7
Регистрация: 31.01.2010
Сообщений: 1,035
|
|
22.01.2017, 18:14 [ТС] | 15 |
Так считать O(n) нельзя. Это асимптотическая сложность алгоритма... Абстрактная величина, абстрагированная от идеального вычислителя. Авторы абстрагируются от всяких Intel core I7, спарков и тд
Короче, таким образом (запустить и проверить) судить об алгоритме нельзя Обычно? Я не знаю какие объект будут в хеши, поэтому нам и дают право переопределить наверно гетхешкод и иквелс. От типа объектов очень много зависит. А насчет идентификатора объекта, не у все так архитектура объектов построена, что они придумывают их номер... Н-р вытащенные строки из БД и взятый у них ID, можно это считать примеро?
0
|
12005 / 8329 / 1268
Регистрация: 21.01.2016
Сообщений: 31,424
|
|
22.01.2017, 18:48 | 16 |
ht1515, не нужно быть дофига математиком, чтобы породить хеш-код контретного объекта. Всё что от тебя требуется - чтобы полученный хеш выглядел как настоящий и отвечал простым требованиям: быть одинаковым для одинаковых объектов и, по возможности, сильно отличаться для разных объектов. Некой комбинации результатов вызова метода GetHashCode() полей класса входящих в критерии сравнения объектов вполне будет достаточно.
0
|
шарпопочитатель
59 / 26 / 7
Регистрация: 31.01.2010
Сообщений: 1,035
|
|
22.01.2017, 19:34 [ТС] | 17 |
0
|
12005 / 8329 / 1268
Регистрация: 21.01.2016
Сообщений: 31,424
|
|
22.01.2017, 19:41 | 18 |
ht1515, и?
0
|
шарпопочитатель
59 / 26 / 7
Регистрация: 31.01.2010
Сообщений: 1,035
|
||||||
22.01.2017, 20:15 [ТС] | 19 | |||||
Ну породить то можно легко, автор статьи говорит что балансировка должна быть равномерной по всему хеш массиву, ваш хеш код - индекс, ну и надо чтобы норм он распределялся
Storm23, например предлагает просто идентификатор использовать объекта. Ну ок, вроде норм, если есть такая возможность. Просто имхо могут быть случаи в которых хеш код ищут не так просто. Просто если все делать по принципу что у объекта будет ИД и хеш код будет ИД, то нафиг микрософт выдал его нам для переопределения? имхо потому что объекты могут быть разными и предметная область может быть разной и ... ну я не могу придумать сейчас ситуации такой, опыта нет, помогите придумать... и в такой ситуации нужно придумать свой алгоритм. Кстати O(n) это максимально плохой случай, это например
0
|
12005 / 8329 / 1268
Регистрация: 21.01.2016
Сообщений: 31,424
|
|
23.01.2017, 07:37 | 20 |
ht1515, ты не сможешь добиться равномерного распределения элементов в хеш-таблице потому, что это самое распределение зависит от количества элементов хранящихся в таблице. Всё что ты сможешь сделать - сделать хеш убедительно разным для разных объектов и не париться так сильно этим.
Ну а пример автора выше - не пример, там человек дикий косяк допустил, раз у него сотня тысяч записей один и тот же хеш имела. Даже простейший XOR над всеми символами строки дал бы что-то очень похожее на хеш.
0
|
23.01.2017, 07:37 | |
Помогаю со студенческими работами здесь
20
Какая разница между типами char* LPSTR?? Разница между разными версиями win7? Какая разница между разными объявлениями объектов? Разница между разными созданиями объектов. Memory managment c++ Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |