Курсовая работа (т): Реализация интерфейса IComparer

) Хеш-код не должен изменяться на протяжении времени существования объекта.

Хорошая производительность словаря основана на хорошей реализации метода GetHashCode(). [2]

Если два ключа возвращают хеш-значения, дающие один и тот же индекс, класс словаря вынужден искать ближайшее доступное свободное место для сохранения второго элемента, к тому же ему придется выполнять некоторый поиск, чтобы впоследствии извлечь требуемое значение. Это наносит ущерб производительности, и если множество ключей дают одни и те же индексы, куда их следует поместить, вероятность конфликтов значительно возрастает. Однако благодаря способу, которым работает часть алгоритма, принадлежащая Microsoft, риск снижается до минимума, когда вычисляемое значение хеш-кода равномерно распределено между int.MinValue и int.MaxValue. [2]

Помимо реализации GetHashCode() тип ключа также должен реализовывать метод IEquatable<T>.Equals() либо переопределять метод Equals() класса Object. Поскольку разные объекты ключа могут возвращать один и тот же хеш-код, метод Equals() используется при сравнении ключей словаря. Словарь проверяет два ключа А и В на эквивалентность, вызывая A.Equals(В). Это означает, что потребуется обеспечить истинность следующего утверждения:

Если истинно А.Equals(В), значит, А.GetHashCode() и В.GetHashCode() всегда должны возвращать один и тот же хеш-код. [2]

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

По этой причине компилятор С# будет отображать предупреждение, если вы переопределите Equals (), но не представите переопределения GetHashCode(). [3]

Для System. Object это условие истинно, поскольку Equals () просто сравнивает ссылки, a GetHashCode () в действительности возвращает хеш-код, основанный исключительно на адресе объекта. Это означает, что хеш-таблицы, основанные на ключе, не переопределяющем эти методы, будут работать корректно. Однако проблема такого подхода заключается в том, что ключи трактуются как эквивалентные только в том случае, если они представляют один и тот же объект. Это значит, что когда при помещении объекта в словарь, обязательно нужно обращаться к ссылкам на ключ. Возможности просто позднее создать экземпляр другого ключевого объекта с тем же значением нет. Если не переопределить Equals() и GetHashCode(), то тип будет не слишком удобным для использования в словаре. [6].String реализует интерфейс IEquatable и соответственно переопределяет GetHashCode(). Equals() обеспечивает сравнение значений, а GetHashCode() возвращает хеш-код, основанный на значении строки. Строки с успехом могут использоваться в качестве ключей в словарях. [6]

Числовые типы, такие как Int32, также реализуют интерфейс IEquatable и перегружают GetHashCode(). Однако хеш-код, возвращаемый этими типами, просто отображает значение. Если число, которое нужно использовать в качестве ключа, само по себе не распределено по всему диапазону возможных целочисленных значений, применение целых в качестве ключей не отвечает правилу равномерного распределения ключевых значений для получения наилучшей производительности. Int32 не предназначен для использования в словаре. [3]

Если нужно использовать тип ключа, который не реализует IEquatable и не переопределяет GetHashCode соответственно значениям ключа, сохраняемым в словаре, то есть возможность создать компаратор, реализующий интерфейс IEqualityComparer<T>. IEqualityComparer<T> определяет методы GetHashCode() и Equals() с аргументом - переданным объектом, так что вы можете предоставить реализацию, отличающуюся от типа самого объекта. Перегрузка конструктора Dictionary<TKey, TValue> позволяет передать объект, реализующий IEqualityComparer<T>. Если такой объект присвоен словарю, этот класс используется для генерации хеш-кодов и сравнения ключей. [3]

Класс Dictionary<TKey, TValue>

В классе Dictionary<TKey, TValue> реализуются интерфейсы IDictionary, IDictionary<TKey, TValue>, ICollection, ICollection<KeyValue Pair<TKey, TValue>>, IEnumerable, IEnumerable<KeyValuePair<TKey, TValue>>, ISerializable и IDeserializationCallback. В двух последних интерфейсах поддерживается сериализация списка. Словари имеют динамический характер, расширяясь по мере необходимости. [2]

В классе Dictionary<TKey, TValue> предоставляется немало конструкторов. Ниже перечислены наиболее часто используемые из них:

Dictionary()Dictionary(IDictionary<TKey, TValue> dictionary)

public Dictionary(int capacity)

В первом конструкторе создается пустой словарь с выбираемой по умолчанию первоначальной емкостью. Во втором конструкторе создается словарь с указанным количеством элементов dictionary. А в третьем конструкторе с помощью параметра capacity указывается емкость коллекции, создаваемой в виде словаря. Если размер словаря заранее известен, то, указав емкость создаваемой коллекции, можно исключить изменение размера словаря во время выполнения, что, как правило, требует дополнительных затрат вычислительных ресурсов. [2]

В классе Dictionary<TKey, TValue> определяется также ряд методов:()

Добавляет в словарь пару "ключ-значение", определяемую параметрами key и value. Если ключ key уже находится в словаре, то его значение не изменяется, и генерируется исключение ArgumentException()

Возвращает логическое значение true, если вызывающий словарь содержит объект key в качестве ключа; а иначе - логическое значение false()

Возвращает логическое значение true, если вызывающий словарь содержит значение value; в противном случае - логическое значение false()

Удаляет ключ key из словаря. При удачном исходе операции возвращается логическое значение true, а если ключ key отсутствует в словаре - логическое значение false. [2]

Кроме того, в классе Dictionary<TKey, TValue> определяются собственные свойства, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Эти свойства приведены ниже, в таблице 4. [5]

Таблица 4 - Собственные свойства класса Dictionary<TKey, TValue>

Следует иметь в виду, что ключи и значения, содержащиеся в коллекции, доступны отдельными списками с помощью свойств Keys и Values. В коллекциях типа Dictionary<TKey, TValue>.KeyCollection и Dictionary<TKey, TValue>.ValueCollection реализуются как обобщенные, так и необобщенные формы интерфейсов ICollection и IEnumerable.

И наконец, в классе Dictionary<TKey, TValue> реализуется приведенный ниже индексатор, определенный в интерфейсе IDictionary<TKey, TValue>

TValue this[TKey key] { get; set; }

Этот индексатор служит для получения и установки значения элемента коллекции, а также для добавления в коллекцию нового элемента. Но в качестве индекса в данном случае служит ключ элемента, а не сам индекс. При перечислении коллекции типа Dictionary<TKey, TValue> из нее возвращаются пары "ключ-значение" в форме структуры KeyValuePair<TKey, TValue>. Напомним, что в этой структуре определяются два поля. [4]

TKey Key;TValue Value;

В этих полях содержится ключ или значение соответствующего элемента коллекции. Как правило, структура KeyValuePair<TKey, TValue> не используется непосредственно, поскольку средства класса Dictionary<TKey, TValue> позволяют работать с ключами и значениями по отдельности. Но при перечислении коллекции типа Dictionary<TKey, TValue>, например, в цикле foreach перечисляемыми объектами являются пары типа KeyValuePair.

Классы HashSet<T> и SortedSet<T>

Класс SortedSet<T> удобен тем, что при вставке или удалении элементов он автоматически обеспечивает сортировку элементов в наборе. Класс SortedSet<T> понадобится информировать о том, как должны сортироваться объекты, за счет передачи его конструктору аргумента - объекта, реализующего обобщенный интерфейс IComparer<T>.

Коллекция, содержащая только отличающиеся элементы, называется множеством (set). В составе .NET 4 имеются два множества - HashSet<T> и SortedSet<T>. Оба они реализуют интерфейс ISet<T>. Класс HashSet<T> содержит неупорядоченный список различающихся элементов, а в SortedSet<T> элементы упорядочены. [6]

Интерфейс ISet<T> предоставляет методы для создания объединения нескольких множеств, пересечения множеств и определения, является ли одно множество надмножеством или подмножеством другого. [2]

Ниже перечислены наиболее употребительные конструкторы, определенные в классе HashSet<T>:

HashSet ()HashSet(IEnumerable<T> collection)

public HashSet(IEqualityCompare comparer)

public HashSet(IEnumerable<T> collection, IEqualityCompare comparer)

В первой форме конструктора создается пустое множество, а во второй форме - множество, состоящее из элементов указываемой коллекции collection. В третьей форме конструктора допускается указывать способ сравнения с помощью параметра comparer. А в четвертой форме создается множество, состоящее из элементов указываемой коллекции collection, и используется заданный способ сравнения comparer. Имеется также пятая форма конструктора данного класса, в которой допускается инициализировать множество последовательно упорядоченными данными.

В этом классе предоставляется также метод RemoveWhere(), удаляющий из множества элементы, удовлетворяющие заданному условию, или предикату. Помимо свойств, определенных в интерфейсах, которые реализуются в классе HashSet<T>, в него введено дополнительное свойство Comparer, приведенное ниже:

IEqualityComparer<T> Comparer { get; }

Оно позволяет получать метод сравнения для вызывающего хеш-множества. [4]

Ниже перечислены четыре наиболее часто используемых конструкторов, определенных в классе SortedSet<T>:

public SortedSet()SortedSet(IEnumerable<T> collection)SortedSet(IComparer comparer)SortedSet(IEnumerable<T> collection, IComparer comparer)

В первой форме конструктора создается пустое множество, а во второй форме - множество, состоящее из элементов указываемой коллекции collection. В третьей форме конструктора допускается указывать способ сравнения с помощью параметра comparer. А в четвертой форме создается множество, состоящее из элементов указываемой коллекции collection, и используется заданный способ сравнения comparer. Имеется также пятая форма конструктора данного класса, в которой допускается инициализировать множество последовательно упорядоченными данными.

В этом классе предоставляется также метод GetViewBetween(), возвращающий часть множества в форме объекта типа SortedSet<T>, метод RemoveWhere(), удаляющий из множества элементы, не удовлетворяющие заданному условию, или предикату, а также метод Reverse(), возвращающий объект типа IEnumerable<T>, который циклически проходит множество в обратном порядке. [6]

Помимо свойств, определенных в интерфейсах, которые реализуются в классе SortedSet<T>, в него введены дополнительные свойства, приведенные ниже:

IComparer<T> Comparer { get; }T Max { get; }T Min { get; }

Свойство Comparer получает способ сравнения для вызывающего множества. Свойство Мах получает наибольшее значение во множестве, а свойство Min - наименьшее значение во множестве.

Класс SortedDictionary<TKey, TValue>

Класс SortedDictionary<TKey, Tvalue> представляет дерево бинарного поиска, в котором все элементы отсортированы на основе ключа. Тип ключа должен реализовать интерфейс IComparable<TKey>. Если тип ключа не сортируемый, компаратор можно также создать, реализовав IComparer<TKey> и указав его в качестве аргумента конструктора сортированного словаря. [2]

Классы SortedDictionary<TKey, Tvalue> и SortedList<TKey, TValue> имеют схожую функциональность. Но поскольку SortedList<TKey, TValue> реализован в виде списка, основанного на массиве, a SortedDictionary<TKey, Tvalue> реализован как словарь, эти классы обладают разными характеристиками:

SortedList<TKey, TValue> использует меньше памяти, чем SortedDictionary<TKey, TValue>

SortedDictionary<TKey, TValue> быстрее вставляет и удаляет элементы.

При наполнении коллекции отсортированными данными SortedList<TKey,TValue> работает быстрее, если при этом не требуется изменение емкости. [6]

В классе SortedDictionary<TKey, TValue> реализуются интерфейсы IDictionary, IDictionary<TKey, TValue>, ICollection, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable и IEnumerable<KeyValuePair<TKey, TValue>>. В классе SortedDictionary<TKey, TValue> предоставляются также следующие конструкторы:

SortedDictionary()SortedDictionary(IDictionary<TKey, TValue> dictionary)SortedDictionary(IComparer<TKey> comparer)SortedDictionary(IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer)

В первом конструкторе создается пустой словарь, во втором конструкторе - словарь с указанным количеством элементов dictionary. В третьем конструкторе допускается указывать с помощью параметра comparer типа IComparer способ сравнения, используемый для сортировки, а в четвертом конструкторе - инициализировать словарь, помимо указания способа сравнения. [2]

В классе SortedDictionary<TKey, TValue> определен ряд методов. Некоторые наиболее часто используемые методы этого класса приведены ниже: [2]()

Добавляет в словарь пару "ключ-значение", определяемую параметрами key и value. Если ключ key уже находится в словаре, то его значение не изменяется, и генерируется исключение ArgumentException()

Возвращает логическое значение true, если вызывающий словарь содержит объект key в качестве ключа; в противном случае - логическое значение false()

Возвращает логическое значение true, если вызывающий словарь содержит значение value, в противном случае - логическое значение false()

Удаляет ключ key из словаря. При удачном исходе операции возвращается логическое значение true, а если ключ key отсутствует в словаре - логическое значение false

Следует иметь в виду, что ключи и значения, содержащиеся в коллекции, доступны отдельными списками с помощью свойств Keys и Values. В коллекциях типа SortedDictionary<TKey, TValue>.KeyCollection и SortedDictionary<TKey, TValue>.ValueCollection реализуются как обобщенные, так и необобщенные формы интерфейсов ICollection и IEnumerable. [6]

И наконец, в классе SortedDictionary<TKey, TValue> реализуется приведенный ниже индексатор, определенный в интерфейсе IDictionary<TKey, TValue>:

TValue this[TKey key] { get; set; }

Этот индексатор служит для получения и установки значения элемента коллекции, а также для добавления в коллекцию нового элемента. Но в данном случае в качестве индекса служит ключ элемента, а не сам индекс.

. Параллельные коллекции

В версию 4.0 среды .NET Framework добавлено новое пространство имен System.Collections.Concurrent. Оно содержит коллекции, которые являются потокобезопасными и специально предназначены для параллельного программирования. Это означает, что они могут безопасно использоваться в многопоточной программе, где возможен одновременный доступ к коллекции со стороны двух или больше параллельно исполняемых потоков. Для безопасного в отношении потоков доступа к коллекциям определен интерфейс IProducerConsumerCollection<T>. Наиболее важными методами этого интерфейса являются TryAdd() и TryTake(). Метод TryAdd() пытается добавить элемент в коллекцию, но это может не получиться, если коллекция заблокирована от добавления элементов. Метод возвращает булевское значение, сообщающее об успехе или неудаче операции. [2]() работает аналогичным образом, информируя вызывающий код об успехе или неудаче, и в случае успеха возвращает элемент из коллекции. Ниже перечислены классы из пространства имен System.Collections.Concurrent с кратким описанием их функциональности:<T>

Этот класс коллекции реализован со свободным от блокировок алгоритмом и использует 32 массива, которые внутренне скомбинированы в связный список. Для доступа к элементам очереди применяются методы Enqueue(), TryDequeue() и TryPeek(). Имена этих методов очень похожи на уже известные методы Queue<T>, но с добавлением префикса Try к тем из них, которые могут дать сбой. Поскольку этот класс реализует интерфейс IProducerConsumerCollection<T>, методы TryAdd() и TryTake() просто вызывают Enqueue() и TryDequeue(). [6]<T>

Очень похож на ConcurrentQueue<T>, но с другими методами доступа к элементам. Класс ConcurrentStack<T> определяет методы Push(), PushRange(), TryPeek(), TryPop() и TryPopRange(). Внутри этот класс использует связный список для хранения элементов. [2]<T>