Словарь: класс Dictionary
представляет собой сложную структуру данных, позволяющую обеспечить доступ к элементам по ключу. Главное свойство словарей — быстрый поиск на основе ключей. Можно также свободно добавлять и удалять элементы, подобно тому, как это делается в List , но без накладных расходов производительности, связанных с необходимостью смещения последующих элементов в памяти.
На следующем рисунке представлена упрощенная модель словаря. Здесь ключами словаря служат идентификаторы сотрудников, такие как В4711. Ключ трансформируется в хеш. В хеше создается число для ассоциации индекса со значением. После этого индекс содержит ссылку на значение. Изображенная модель является упрощенной, поскольку существует возможность того, что единственное вхождение индекса может быть ассоциировано с несколькими значениями, и индекс может храниться в виде дерева.
В .NET Framework предлагается несколько классов словарей. Главный класс, который можно использовать — это Dictionary .
Тип ключа
Тип, используемый в качестве ключа словаря, должен переопределять метод GetHashCode() класса Object. Всякий раз, когда класс словаря должен найти местоположение элемента, он вызывает метод GetHashCode().
Целое число, возвращаемое этим методом, используется словарем для вычисления индекса, куда помещен элемент. Мы не станем углубляться в подробности работы этого алгоритма. Единственное, что следует знать — это то, что он использует простые числа, так что емкость словаря всегда выражается простым числом.
Реализация метода GetHashCode() должна удовлетворять перечисленным ниже требованиям:
Один и тот же объект должен всегда возвращать одно и то же значение.
Разные объекты могут возвращать одно и то же значение.
Он должен выполняться насколько возможно быстро, не требуя значительных вычислительных затрат.
Он не должен генерировать исключений.
Он должен использовать как минимум одно поле экземпляра.
Значения хеш-кода должны распределяться равномерно по всему диапазону чисел, которые может хранить int.
Хеш-код не должен изменяться на протяжении времени существования объекта.
Чем вызвана необходимость равномерного распределения значений хеш-кода по диапазону целых чисел? Если два ключа возвращают хеш-значения, дающие один и тот же индекс, класс словаря вынужден искать ближайшее доступное свободное место для сохранения второго элемента, к тому же ему придется выполнять некоторый поиск, чтобы впоследствии извлечь требуемое значение. Понятно, что это наносит ущерб производительности, и если множество ключей дают одни и те же индексы, куда их следует поместить, вероятность конфликтов значительно возрастает. Однако благодаря способу, которым работает часть алгоритма, принадлежащая Microsoft, риск снижается до минимума, когда вычисляемое значение хеш-кода равномерно распределено между int.MinValue и int.MaxValue.
Помимо реализации GetHashCode() тип ключа также должен реализовывать метод IEquatable .Equals() либо переопределять метод Equals() класса Object. Поскольку разные объекты ключа могут возвращать один и тот же хеш-код, метод Equals() используется при сравнении ключей словаря. Словарь проверяет два ключа А и В на эквивалентность, вызывая A.Equals(В). Это означает, что потребуется обеспечить истинность следующего утверждения:
Если истинно А.Equals(В) , значит, А.GetHashCode() и В.GetHashCode() всегда должны возвращать один и тот же хеш-код.
Класс Dictionary
В классе Dictionary реализуются интерфейсы IDictionary, IDictionary , ICollection, ICollection >, IEnumerable, IEnumerable >, ISerializable и IDeserializationCallback. В двух последних интерфейсах поддерживается сериализация списка. Словари имеют динамический характер, расширяясь по мере необходимости.
В классе Dictionary предоставляется немало конструкторов. Ниже перечислены наиболее часто используемые из них:
В первом конструкторе создается пустой словарь с выбираемой по умолчанию первоначальной емкостью. Во втором конструкторе создается словарь с указанным количеством элементов dictionary. А в третьем конструкторе с помощью параметра capacity указывается емкость коллекции, создаваемой в виде словаря. Если размер словаря заранее известен, то, указав емкость создаваемой коллекции, можно исключить изменение размера словаря во время выполнения, что, как правило, требует дополнительных затрат вычислительных ресурсов.
В классе Dictionary определяется также ряд методов:
Add()
Добавляет в словарь пару «ключ-значение», определяемую параметрами key и value. Если ключ key уже находится в словаре, то его значение не изменяется, и генерируется исключение ArgumentException
ContainsKey()
Возвращает логическое значение true, если вызывающий словарь содержит объект key в качестве ключа; а иначе — логическое значение false
ContainsValue()
Возвращает логическое значение true, если вызывающий словарь содержит значение value; в противном случае — логическое значение false
Remove()
Удаляет ключ key из словаря. При удачном исходе операции возвращается логическое значение true, а если ключ key отсутствует в словаре — логическое значение false
Кроме того, в классе Dictionary определяются собственные свойства, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Эти свойства приведены ниже:
Comparer
Получает метод сравнения для вызывающего словаря
Keys
Получает коллекцию ключей
Values
Получает коллекцию значений
Следует иметь в виду, что ключи и значения, содержащиеся в коллекции, доступны отдельными списками с помощью свойств Keys и Values. В коллекциях типа Dictionary .KeyCollection и Dictionary .ValueCollection реализуются как обобщенные, так и необобщенные формы интерфейсов ICollection и IEnumerable.
И наконец, в классе Dictionary реализуется приведенный ниже индексатор, определенный в интерфейсе IDictionary
Этот индексатор служит для получения и установки значения элемента коллекции, а также для добавления в коллекцию нового элемента. Но в качестве индекса в данном случае служит ключ элемента, а не сам индекс. При перечислении коллекции типа Dictionary из нее возвращаются пары «ключ-значение» в форме структуры KeyValuePair . Напомним, что в этой структуре определяются два поля.
В этих полях содержится ключ или значение соответствующего элемента коллекции. Как правило, структура KeyValuePair не используется непосредственно, поскольку средства класса Dictionary позволяют работать с ключами и значениями по отдельности. Но при перечислении коллекции типа Dictionary , например, в цикле foreach перечисляемыми объектами являются пары типа KeyValuePair.
Давайте рассмотрим пример использования словарей:
Источник
Вывод на экран значений по ключу (Dictionary)
У меня есть класс который состоит из списка сотрудников лаборатории.
Как мне написать метод который бы выводил список сотрудников по ключу(название лаборатории)?
Помощь в написании контрольных, курсовых и дипломных работ здесь.
Объединение значений двух Dictionary по ключу
Добрый день! Есть два Dictionary >: Dictionary >.
Отсортировать Dictionary по ключу
В общем, у меня есть такой код Dictionary dictionary = new Dictionary 6
Решение
Оно выводит только Имя а мне нужно всю информацию о сотруднике.
Dictionary получение элемента по ключу
Интересует такая ситуация. Для простого примера возьмем словарь, в котором в качестве значения.
Поиск значения по ключу в Dictionary
Как сделать что бы я вводил «ttt», а мне выводила «глицин» и наоборот все варианты? using.
Получить обьект по строке ключу в Dictionary
Здравствуйте! Это достаточно простой вопрос, но с ним возникли трудности. Мне нужен ассоциативный.
Как в Dictionary перезаписать значение по ключу?
Люди подскажите пожалуйста. Есть заполненный Dictionary. И в нем нужно переписать значение по.
Источник
Под капотом у Dictionary и ConcurrentDictionary
Некоторое время назад, я решил, что хочу знать больше подробностей о работе многопоточности в .NET и что я уделял этому незаслуженно мало внимания в прошлом. Информации на эту тему великое множество (отправной точкой я для себя выбрал этот раздел книги «C# in a nutshell»), но, как оказалось, только малая часть ресурсов пытаются объяснить что-то в деталях.
Каждый мастер должен знать свои инструменты, а что может использоваться чаще коллекций? Поэтому я решил сделать небольшой обзор многопоточных коллекций и начать с ConcurrentDictionary (беглый обзор уже встречался здесь, но его там совсем мало). Вообще, я несколько удивился, что такой статьи для .NET еще нет (зато хватает по Java).
Итак, поехали.
Если вы уже знакомы с самим Dictionary, то можете пропустить следующий раздел.
Что такое Dictionary ?
Dictionary представляет собой реализацию стандартной Hashtable.
Здесь интересны следующие функции:
Инициализация
Инициализация происходит либо при создании (если передана начальный размер коллекции), либо при добавлении первого элемента, причем в качестве размера будет выбрано ближайшее простое число (3). При этом создаются 2 внутренние коллекции — int[] buckets и Entry[] entries. Первая будет содержать индексы элементов во второй коллекции, а она, в свою очередь, — сами элементы в таком виде:
Добавление элементов
При добавлении элемента вычисляется хэшкод его ключа и затем — индекс корзины в которую он будет добавлен по модулю от величины коллекции:
Выглядеть это будет примерно так: 
Затем проверяется нет ли уже такого ключа в коллекции, если есть — то операция Add выбросит исключение, а присваивание по индексу просто заменит элемент на новый. Если достигнут максимальный размер словаря, то происходит расширение (выбирается новый размер ближайшим простым числом).
Сложность оперции соответственно — O(n).
Если происходит коллизия (то есть в корзине с индексов bucketNum уже есть элемент), то новый элемент добавляется в коллекцию, его индекс сохраняется в корзине, а индекс старого элемента — в его поле next.
Таким образом получаем однонаправленный связный список. Данный механизм разрешения коллизий называется chaining. Если при добавлении элемента число коллизий велико (больше 100 в текущей версии), то при расширении коллекции происходит операция перехэширования, перед выполнением которой случайным образом выбирается новый генератор хэшкодов.
Сложность добавления O(1) или O(n) в случае коллизии.
Удаление элементов
При удалении элементов мы затираем его содержимое значениями по умолчанию, меняем указатели next других элементов при неоходимости и сохраняем индекс этого элемента во внутреннее поле freeList, а старое значение — в поле next. Таким образом, при добавлении нового элемента мы можем повторно использовать такие свободные ячейки:
Сложность снова O(1) или O(n) в случае коллизии.
Другое
Так же стоит отметить 2 момента:
1) При очистке словаря, его внутренний размер не изменяется. То есть, потенциально, вы просто тратите место.
2) GetEnumerator просто возвращает итератор по коллекции entires (сложность O(1)). Если вы только добавляли элементы — они вернутся в том же порядке. Однако если вы удаляли элементы и добавляли новые — порядок соответственно изменится, поэтому на него полагаться не стоит (тем более, что в будущих версиях фреймворка это может измениться).
Так и что же с ConcurrentDictionary?
Казалось бы, есть 2 решения в лоб для обеспечения потокобезопасности — обернуть все обращения к словарю в блокировки или обернуть все его методы в них же. Однако, по понятным причинам, такое решение будет медленным — задержки, добавляемые lock, да и ограничение на 1 поток, который мог бы работать с коллекцией не добавляют быстродействия.
В Microsoft пошли более оптимальным путем и Dictionary притерпел некоторые изменения. Так, благодаря внутренней структуре словаря и его корзин, блокировка осуществляется по ним, с помощью метода
В то же время обычный словарь не смог бы работать с этой схемой, потому что все корзины используют один и тот же массив entries, поэтому корзины стали представлять собой обычный single linked list: volatile Entry[] m_buckets (поле объявлено как volitale, чтобы обеспечить неблокирующую синхронизацию в ситуации когда один поток пытается выполнить какую-то операцию, а другой в этот момент изменяет размер коллекции).
В итоге корзины стали выглядеть вот так:
lockNo — это индекс в новом массиве, который содержит объекты синхронизации — object[] m_locks. Его использование позволяет разным потокам изменять разные корзины в одно и то же время. Размер этой коллекции зависит от параметра ConcurrencyLevel который можно задать через конструктор. Он определяет примерное число потоков которые будут одновременное работать с коллекцией (по умолчанию это число_процессоров * 4). Чем выше это значение, тем проще будут происходить операции записи, но так же станут гораздо дороже операции, которые требуют полной блокировки всей коллекции (Resize, ToArray, Count, IsEmpty, Keys, Values, CopyTo, Clear). Также этот параметр определяет сколько элементов коллекции приходится на один lock (как отношение числа корзин к размеру этой коллекции) и когда элементов становится больше, чем надо — коллекция расширяется, потому что в противном случае поиск элемента требует не O(1), а уже O(n) за счет обхода связных списков. Чтобы немного снизить число первоначальных расширений коллекции, начальный размер словаря уже не 3, а 31.
Все операции приобрели вид:
При добавлении нового элемента приходится обойти весь связанный список просто чтобы определить есть ли уже такой ключ и если нет — добавить. Аналогично при удалении — сперва надо найти узел который удалить.
Впрочем, для некоторых операций блокировка не нужна в принципе — это TryGetValue, GetEnumerator, ContainsKey и индексация. Почему? Потому что все изменения размера корзин видны за счет того что поле volatile, любые добавления или изменения элементов происходят путем создания нового элемента и замены им старого, а удаления происходят просто заменой указателя на следующий узел.
Другое
лучше использовать dictionary.Select(x => x.Value).ToArray(), чем dictionary.Values.ToArray()
И это не совсем верно — вместо «лучше» тут должно быть «быстрее» — за счет отсутствия блокировок, но надо принять во внимание, что данные подходы могут вернуть разные данные.
Источник