АССОЦИАТИВНЫЕ КОЛЛЕКЦИИ Лекция 6 1. Отличие от последовательных 2 В последовательной коллекции каждый элемент ассоциируется с номером, начиная с 0. В. - презентация

1 АССОЦИАТИВНЫЕ КОЛЛЕКЦИИ Лекция 6 1

2 Отличие от последовательных 2 В последовательной коллекции каждый элемент ассоциируется с номером, начиная с 0. В ассоциативной коллекции элементы идентифицируются уникальными ключами произвольного типа – числа, строки, пользовательские классы, … Но у всех коллекций есть нечто общее, и это общее – интерфейсы.

3 Интерфейсы коллекций 3 GetEnumerator() Count this[int] Add(), Remove()…

4 Интерфейс IDictionary 4 K V public struct KeyValuePair { public KeyValuePair(TKey key, TValue value); public TKey Key { get; } public TValue Value { get; } public override string ToString(); } public interface IDictionary : ICollection > { ICollection Keys { get; } ICollection Values { get; } TValue this[TKey key] { get; set; } void Add(TKey key, TValue value); bool ContainsKey(TKey key); bool Remove(TKey key); bool TryGetValue(TKey key, out TValue value); }

5 Классы ассоциативных коллекций HashTable Dictionary SortedDictionary 5 К2К1К3

6 Хэш-таблица 6 Add ress Key (Год) Value 01980Smalltalk 11991Python NET Java Запись 1.Хешируем ключ и получаем адрес. 2.Если адрес свободен, записываем. 3.Если занят, рехешируем ключ. 4.goto 2. Чтение 1.Хешируем ключ и получаем адрес. 2.Если адрес свободен, значения нет. 3.Если занят, сверяем ключи 4.Если ключи совпали, читаем 5.Если не совпали, рехешируем ключ. 6.goto 2

7 Хэш-таблица 7 Add ress Key (Год) Value 01980Smalltalk 11991Python NET 31990Python Java Удаление 1.Определяем адрес, как для чтения. 2.Помечаем ключ как удаленный.

8 Пример: Частотный словарь 8 private static Dictionary CreateDictionary(string[] words) { Dictionary dict = new Dictionary (); foreach (string word in words) { if (dict.ContainsKey(word)) dict[word]++; else dict[word] = 1; } return dict; } Задан текст (массив слов). Составить для него частотный словарь.

9 Эквивалентность в.NET 9 Объекты, которые служат ключами в ассоциативных коллекциях, должны допускать операцию проверки эквивалентности. Строки, числа, символы допускают проверку эквивалентности. В пользовательских объектах операцию эквивалентности необходимо объявлять.

10 Метод Object.Equals() 10 В классе Object есть виртуальный метод bool Equals(object o), он считает объект эквивалентным только самому себе. Если программиста не устраивает такая семантика, он должен перекрыть этот метод в своем классе. Например, для класса Point это может быть сделано так. public override bool Equals(Object obj) { // Если параметр равен null, возвращаем false. if (obj == null) return false; // Если параметр не приводится к Point, возвращаем false. Point p = obj as Point; if ((System.Object)p == null) // антицикл return false; // Возвращаем true, если поля равны. return (x == p.x) && (y == p.y); } Замечание. Закрытые поля p.x, p.y видны так же, как и this.x, this.y.

11 Равна ли точка цветной точке? 11 class Point { public int X, Y; } class ColPoint: Point { public Color C; } Эквивалентными считаются только однотипные объекты. В противном случае ожидаются парадоксы, т.е. из A == B и B == C будет следовать, что A == C. Свойства эквивалентности: Рефлексивность Симметричность Транзитивность

12 Эквивалентность в.NET 12 Кроме метода Equals(), в классе Object есть еще два статических метода: public static bool ReferenceEquals(object objA, object objB); public static bool Equals(object objA, object objB); и метод public virtual int GetHashCode(); Порядок определения пользовательской эквивалентности: 1)перекрываем метод экземпляра Equals(); 2)перекрываем метод экземпляра GetHashCode(); 3)остальные методы не трогаем.

13 Операции == и != 13 Вместе с перегрузкой метода Equals() нужно пергружать не только GetHashCode(), но и операции сравнения.

14 Самостоятельно 14 1.Разработайте класс «Телефонный справочник», который бы мог хранить произвольное количество абонентов. Для каждого абонента известна фамилия и один номер телефона. Фамилии разных абонентов могут быть одинаковыми, номера телефонов – нет. Справочник должен выполнять поиск номеров телефонов по фамилии и поиск фамилии по номеру телефона 2.Сделайте класс Point способным выполнить роль ключа в ассоциативной коллекции. 3.Унаследуйте List и добавьте в наследник проверку эквивалентности. Коллекции считаются эквивалентными, если состоят из попарно эквивалентных элементов.