Лекции / КОНТЕЙНЕРЫ

Многочисленные эксперименты показывают, что для заполненной на 50%

таблицы (половина ячеек пустые) для поиска любого ключа в среднем требуется лишь 1,5 сравнения, причем это число не зависит от количества элементов. Это еще раз подтверждает высочайшую эффективность хеш-

поиска!

Взаключение дадим общие рекомендации по применению хеш-поиска.

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

функции и самих ключей можно построить бесконфликтную таблицу и достичь максимально возможной скорости поиска – ровно 1 сравнение для любого ключа независимо от их количества

2.Если набор ключей может меняться и заранее неизвестен, то важным становится выбор хеш-функции для равномерного распределения ключей по таблице. Одной из лучших хеш-функций считается следующая: исходный целочисленный ключ возводится в квадрат,

преобразуется в двоичное представление в виде набора битов и из середины этого набора извлекается необходимое число битов в соответствии с размерностью таблицы (например, для таблицы размерности 1024 необходимо извлечь 10 битов)

3.При использовании открытого хеширования рекомендуется размер таблицы выбирать равным n/2, что в среднем должно обеспечивать короткие вспомогательные списки (1-2 элемента), которые могут просматриваться только последовательно

4.При использовании внутреннего хеширования рекомендуется размер таблицы выбирать равным 1,2 для обеспечения достаточного количества свободных ячеек.

5.В обоих случаях, если в процессе использования хеш-поиска происходит добавление в таблицу новых элементов и из-за этого

нарушаются приведенные выше рекомендации, целесообразно

11

выполнить реструктуризацию хеш-таблицы, добавив в базовый массив

необходимое число ячеек

6.Некоторые сложности возникают при удалении элементов из хеш-

таблицы, особенно – при использовании внутреннего хеширования, т.к.

при этом за счет появления «незапланированных» пустых ячеек может

нарушится работа алгоритма поиска Ну и, наконец – ложка дегтя в бочке меда: метод совершенно

непригоден для обработки упорядоченных наборов.

§10.10 Коллекция Dictionary <T, V>

Еще один распространенный тип коллекции представляют словари.

Класс Dictionary <TKey, TValue> представляет собой коллекцию объектов, которые представляют пару ключ-значение. Здесь TKey – тип ключей в словаре, TValue - тип значений в словаре. Каждый такой объект является объектом структуры KeyValuePair <TKey, TValue>. Благодаря свойствам Key и Value, которые есть у данной структуры, мы можем получить ключ и значение элемента в словаре.

Рассмотрим на примере использование словарей:

Листинг 11.40 – Добавление элемента в словарь

1Dictionary<int, string> countries = new Dictionary<int, string>(5); //создание словаря

2countries.Add(1, "Russia"); //добавление элемента в словарь

3countries.Add(3, "Great Britain");

4countries.Add(2, "USA");

5countries.Add(4, "France");

6countries.Add(5, "China");

7foreach (KeyValuePair<int, string> keyValue in countries) //вывод всех элементов словаря countries

8{

9Console.WriteLine(keyValue.Key + " - " + keyValue.Value);

10}

11// получение элемента по ключу

12string country = countries[4];

12

13// изменение объекта

14countries[4] = "Spain";

15// удаление по ключу

16countries.Remove(2);

Класс словарей также, как и другие коллекции, предоставляет методы

Add и Remove для добавления и удаления элементов. Только в случае словарей в метод Add передаются два параметра: ключ и значение. А метод Remove

удаляет не по индексу, а по ключу.

Так как в нашем примере ключами является объекты типа int, а

значениями - объекты типа string, то словарь в нашем случае будет хранить объекты KeyValuePair<int, string>. В цикле foreach мы их можем получить и извлечь из них ключ и значение.

Кроме того, мы можем получить отдельно коллекции ключей и значений словаря:

Листинг 11.41 – Перебор ключей и значений

1

Dictionary<char, Person> people = new Dictionary<char, Person>();

2people.Add('b', new Person() { Name = "Bill" });

3people.Add('t', new Person() { Name = "Tom" });

4people.Add('j', new Person() { Name = "John" });

5foreach (KeyValuePair<char, Person> keyValue in people)

6{

7// keyValue.Value представляет класс Person

8	Console.WriteLine(keyValue.Key	+	"	-	"	+
	keyValue.Value.Name);
9	}

10// перебор ключей

11foreach (char c in people.Keys)

12{

13Console.WriteLine(c);

14}

15// перебор по значениям

16foreach (Person p in people.Values)

17{

18Console.WriteLine(p.Name);

19}

13

Здесь в качестве ключей выступают объекты типа char, а значениями -

объекты Person. Используя свойство Keys, мы можем получить ключи словаря, а свойство Values соответственно хранит все значения в словаре.

Для добавления необязательно применять метод Add(), можно использовать сокращенный вариант:

Листинг 11.42 – Сокращенная форма добавления элемента

1

Dictionary<char, Person> people = new

Dictionary<char, Person>();

2people.Add('b', new Person() { Name = "Bill" });

3people['a'] = new Person() { Name = "Alice" };

Несмотря на то, что изначально в словаре нет ключа 'a' и

соответствующего ему элемента, то он все равно будет установлен. Если же он есть, то элемент по ключу 'a' будет заменен на новый объект new Person() { Name = "Alice" }.

Получение значения с помощью его ключа выполняется очень быстро,

близко к O(1), поскольку Dictionary<TKey,TValue> класс реализуется как хэш-таблица.

При условии, что объект используется в качестве ключа в

Dictionary<TKey,TValue>, он не должен изменяться каким-либо образом,

который влияет на его значение хэша. Каждый ключ в

Dictionary<TKey,TValue> должен быть уникальным в соответствии с компаратором на равенство словаря. Ключ не может быть null, но значение может быть, если его тип TValue является ссылочным типом.

14