Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 31
Благодарю за статью. Планируется ли обзор других многопоточных коллекций из .NET 4?
Если эта тема кому-то интересно — конечно.
Так вроде когда все это выпускалось, уже была статья или даже серия про многопоточные коллекции. Советую поискать.
Искал, и, честно говоря, не нашел. Есть статья ConcurrentDictionary в роли кэша, но о ней я знаю, и автор этой статьи вначале сослался на неё. Есть Новая коллекция SortedSet<Т> в .NET 4.0, но это не о многопоточной коллекции (и эту статью я тоже читал). Ещё нашел Параллельная обработка IEnumerable в .NET, но это не совсем то. Возможно, я плохо искал, поэтому буду вам признателен, если дадите ссылку.
Вот как раз вчера засел за поиск потообезопасной очереди объектов и нашёл ConcurrentQueue. Насколько я понимаю — это одного поля ягоды и хотелось бы побольше узнать об очередях и о подводных камнях при работе с ними.
После прочтения промелькнула мысль: «Чувак, я нихрена не понял, но твои слова запали мне в душу».
А по делу, статья, конечно, достойная в плане расширения знаний.
Правда, у меня возникло недопонимание таких моментов…
«Затем проверяется нет ли уже такого в коллекции», такого индекса или хеша? Вроде по тексту дальше, подразумевается индекс. Но все-равно запутанно.
«Если происходит коллизия (то есть элемент с таким же хэшкодом уже есть в коллекции)». А как она может возникнуть? У наc же «операция Add выбросит исключение»?
А по делу, статья, конечно, достойная в плане расширения знаний.
Правда, у меня возникло недопонимание таких моментов…
«Затем проверяется нет ли уже такого в коллекции», такого индекса или хеша? Вроде по тексту дальше, подразумевается индекс. Но все-равно запутанно.
«Если происходит коллизия (то есть элемент с таким же хэшкодом уже есть в коллекции)». А как она может возникнуть? У наc же «операция Add выбросит исключение»?
Ответ на 1 вопрос — ключа и его хэша на самом деле. Я не уверен зачем так сделано, учитывая, что хэш генерится по ключу, но проверка там выглядит так:
По 2 вопросу — отредактировал пост. Вы правы, там не хэш, там индекс корзины который получился по формуле:
Тут, как вы понимаете результат может быть одинаковый для разных хэшей.
if ((this.entries[i].hashCode == hashcode) && this.comparer.Equals(this.entries[i].key, key))
По 2 вопросу — отредактировал пост. Вы правы, там не хэш, там индекс корзины который получился по формуле:
int bucketNum = (hashcode & 0x7fffffff) % capacity;
Тут, как вы понимаете результат может быть одинаковый для разных хэшей.
Кстати,
Делается эта операция для того, чтобы транслировать отрицательную часть диапазона
hashcode & 0x7fffffff — интересный приём. 0x7fffffff — это значение int.MaxValue.Делается эта операция для того, чтобы транслировать отрицательную часть диапазона
Int32 в положительную. Логически это то же самое, что:hashcode >= 0 ? hashcode : int.MaxValue + hashcode + 1
Ответ на 1 вопрос — ключа и его хэша на самом деле. Я не уверен зачем так сделано, учитывая, что хэш генерится по ключу, но проверка там выглядит так
if ((this.entries[i].hashCode == hashcode) && this.comparer.Equals(this.entries[i].key, key))
Если я правильно понял и речь идёт о добавлении элемента, то смысл самый прямой. Хеши ключей могу совпадать при разных значениях ключей. GetHash() гарантирует только то, что одинаковые объекты вернут одинаковые хеши, но не гарантирует что разные объекты будут иметь разный хешь.
Не пишу на C#, но с удовольствием прочитал статью.
Спасибо!
Спасибо!
На сколько я помню, стандартная реализация Dictionary перестраивает списки в деревья, если на одном хэше висит много элементов, а не делает перехэширование.
Тут я могу предложить вам поверить мне на слово, либо взять в руки рефлектор и убедиться самому.
Деревья для защиты от коллизий используются в джаве, IIRC.
При добавлении элемента вычисляется хэшкод его ключа и затем — индекс корзины в которую он будет добавлен по модулю от величины коллекции (именно для этого размер выбирается простым числом, чтобы обеспечить более равномерное распределение и уменьшить число возможных коллизий):Я, наверное, что-то недопонял. Можете пояснить, как деление по модулю простого числа обеспечивает «более равномерное» распределение, чем деление по модулю обычного числа (например, на единицу большего, чем простое)?
При вычислении хэша необходимо, чтоб распределение было как можно более равномерным, и чтоб хеширующая функция учитывала максимальное кол-во информации из хешируемого значения. Допустим делитель будет не простым числом, а степенью двойки 2^p, тогда остатком от деления на такое число любого другого (L) будет p нижних битов L, что само по себе нехорошо, потому что верхние биты не принимают «участие» в результирующем хеше.
По этому поводу есть глава в «Introduction To Algorithms» Кормена.
По этому поводу есть глава в «Introduction To Algorithms» Кормена.
А, кажется, я начинаю понимать. Но думаю, что дело не в том, что какие-то биты «не работают». Ведь биты — всего лишь одно из бесонечности возможных представлений числа. Если представить то же самое число в троичной системе, то «не будут работать» биты при делении на 3. Если представить число в системе по основанию 59, то не будут работать биты при делении на 59.
Думаю, идея в оптимизации перехэширования. Ведь алгоритмы хеширования, хотя и могут быть основаны на разных принципах, наверное могут иногда вести себя схожим образом при, например, делении их хэщей на степень двойки, или тройки, или ещё какого-то числа. В общем, мне кажется, что простые числа нужны, чтобы свести к минимуму необходимость повторного перехеширования. Например, по какому-то конкретному хэшу накопилось 100 значений, а после смены хэш-алгоритма снова наблюдается та же ситуация из-за того, что в обоих алгоритмах «не работают биты» при взятии остатка деления на какое-то число. Так вот, чем больше размер массива
Думаю, идея в оптимизации перехэширования. Ведь алгоритмы хеширования, хотя и могут быть основаны на разных принципах, наверное могут иногда вести себя схожим образом при, например, делении их хэщей на степень двойки, или тройки, или ещё какого-то числа. В общем, мне кажется, что простые числа нужны, чтобы свести к минимуму необходимость повторного перехеширования. Например, по какому-то конкретному хэшу накопилось 100 значений, а после смены хэш-алгоритма снова наблюдается та же ситуация из-за того, что в обоих алгоритмах «не работают биты» при взятии остатка деления на какое-то число. Так вот, чем больше размер массива
buckets, тем меньше вероятность, что мы с этим стокнёмся — ведь простые числа растут, и всё меньше остаётся чисел, которые на них без остатка делятся.Давайте я приведу пример. У вас есть словарик на 10 элементов (capacity = 10). При вычислении индекса корзины, в которую попадет элемент, мы берем остаток от деления на 10. Логично, что элемент, в зависимости от его хэша, попадет в 0..9 корзину. А теперь представьте что у хэша и размера словаря есть общие делители — например 2 (или 5). Тогда, элемент уже может попасть только в 0..4 (либо 0..1). А это значит что бОльшая часть корзин останется неиспользованными. А теперь возьмите простые числа — они делятся только на 1 и самих себя. Т.е. при емкости 11, элементы будут случайным образом всегда занимать 0..10 корзины.
Упрощенно, процент использования всех корзин можно представить как (GCD — наибольший общий делитель)
Упрощенно, процент использования всех корзин можно представить как (GCD — наибольший общий делитель)
x% = capacity / GCD (capacity, hashcode)
capacity = 10
hashcode = 18
GCD = 2
bucketNumber = 18 % 10 = 8
Не сходится это с тем, что вы написали.
Вообще, если хэш равномерно распределён по всему диапазону своих возможных значений, то уже на что его не дели, всё равно остаток будет распределён равномерно в диапазоне значений [0; capacity). Общие делители на это абсолютно никак не влияют — влияет только распределение хэшей.
Да, действительно, не подходит такой вариант. Тогда так — предположим, что у нас хорошая хэш функция, которая возвращает не связанные хэшкоды — тут разницы простое число или нет скорее всего не будет. А теперь представим, что хэшкоды связаны, например х, 2х, 3х, 4х и т.д. Например если ваши хэши — 2,4,6,8,10,12,14,16,18,20, то и корзины в которые они попадут будут одними и теми же.
И простое чило, выбранное в качестве делителя здесь просто помогает компенсировать плохую работу хэш функции.
2 % 10 = 12 % 10 = 2 и т.д.
И простое чило, выбранное в качестве делителя здесь просто помогает компенсировать плохую работу хэш функции.
Возьмём простое число P. На него без остатка делится N чисел из диапазона значений Int32.
Возьмём число P+1. На него без остатка будут делится N' чисел из того же диапазона, причём N' <= N.
Компенсировать плохую работу хэш-функции можно не тем фактом, что число простое, а тем фактом, что число большое. Чем больше число, тем меньше других чисел на него нацело делится. В том контексте, о котором вы говорите, абсолютно не имеет значения, простое ли значение capacity, или нет.
Возьмём число P+1. На него без остатка будут делится N' чисел из того же диапазона, причём N' <= N.
Компенсировать плохую работу хэш-функции можно не тем фактом, что число простое, а тем фактом, что число большое. Чем больше число, тем меньше других чисел на него нацело делится. В том контексте, о котором вы говорите, абсолютно не имеет значения, простое ли значение capacity, или нет.
А что удивительного? Все ждут пока кнонибудь напишет статью по канкаренси, я например, ждал точно. Еще бы чуть чуть и написал бы кто нибудь другой, может быть и я, это как игра в слабака, кто первый струсит. За статью спасибо!
Такс, всё круто, но остались белые ( или черные пятна ).
Dictionary умеет ведь искать элементы, так? А также выбрасывать исключения, если такой элемент уже есть в коллекции?
Так вот что будет если:
1) добавляем элемент, скажем, 25 (тип int, поэтому его значение и хешкод совпадают). Количество корзин было 23. значит элемент добавился в корзину № 25 % 23 = 2, в корзину 2 значит. Так?
2) Добавилось в коллекцию кучу других элементов так, что словарь увеличился до 29. Так? Значит количество корзин стало 29. (просто создался массив из 29 элементов и 23 элемента скопировалось в 29), так?
3) В коллекцию приходит снова элемент 25, только теперь он распределяется не в корзину 2, а в корзину 25.
25 % 29 = 25 Правильно?
При этом коллекция не выбрасывает исключение, в коллекции оказывается два одинаковых значения, только расположены они в разных местах.
Если после расширения словаря, попробовать найти какой либо из раннее добавленных элементов, то он найден не будет.
Что, получается, что при расширении словаря меняется не только структура с корзинами, но и вообще вся структура? это же очень дорого, все равно что взять и передобавить все существующие элементы в коллекцию только с новым размером словаря. Или как?
Dictionary умеет ведь искать элементы, так? А также выбрасывать исключения, если такой элемент уже есть в коллекции?
Так вот что будет если:
1) добавляем элемент, скажем, 25 (тип int, поэтому его значение и хешкод совпадают). Количество корзин было 23. значит элемент добавился в корзину № 25 % 23 = 2, в корзину 2 значит. Так?
2) Добавилось в коллекцию кучу других элементов так, что словарь увеличился до 29. Так? Значит количество корзин стало 29. (просто создался массив из 29 элементов и 23 элемента скопировалось в 29), так?
3) В коллекцию приходит снова элемент 25, только теперь он распределяется не в корзину 2, а в корзину 25.
25 % 29 = 25 Правильно?
При этом коллекция не выбрасывает исключение, в коллекции оказывается два одинаковых значения, только расположены они в разных местах.
Если после расширения словаря, попробовать найти какой либо из раннее добавленных элементов, то он найден не будет.
Что, получается, что при расширении словаря меняется не только структура с корзинами, но и вообще вся структура? это же очень дорого, все равно что взять и передобавить все существующие элементы в коллекцию только с новым размером словаря. Или как?
2) Добавилось в коллекцию кучу других элементов так, что словарь увеличился до 29. Так? Значит количество корзин стало 29. (просто создался массив из 29 элементов и 23 элемента скопировалось в 29), так?
Не так. При перехэшировании (только при нем увеличивается размер корзины) хэш каждого элемента вычисляется заново. Сложность этой операции указана в статье — O(n). Происходить перехэширование будет не часто, т.к. размер корзины выбирается простым числом.
Обновите ссылку пожалуйста, она перестала работать
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Под капотом у Dictionary и ConcurrentDictionary