Урок 36. Коллекция Hashtable C#

На 36-м уроке учебника по основам C# описывается использование класса Hashtable. Он предоставляет универсальные коллекции словарей, позволяющие обращаться к элементам коллекции не по индексу, а по объектному ключу.

Что такое хеш-таблица?

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

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

Коллекция Hashtable

Платформа .NET framework предоставляет класс Hashtable, который обладает всеми функциональными возможностями, необходимыми для реализации хэш-таблицы без дополнительной разработки. Hashtable - это набор универсальных словарей. Каждый элемент коллекции - это объект DictionaryEntry с двумя свойствами: объектом key и объектом value. Они известны как пары ключ / значение.

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

Реализованные интерфейсы Collection

Коллекция Hashtable реализует интерфейсы IDictionary и ICollection. Это поведение описано в предыдущей статье. В остальной части этой статьи описываются дополнительные функциональные возможности класса Hashtable.

Объявление хэш-таблицы

Конструкторы

В .NET framework версии 1,1 класс Hashtable включает десять конструкторов. Более поздние версии платформы включают в себя еще больше. В этой статье для начинающих мы рассмотрим четыре конструктора. Самый простой не требует никаких параметров. Следующий код создает новую пустую хэш-таблицу. Класс Hashtable находится в пространстве имен System.Collections, так что, чтобы выполнить примеры, добавьте using System.Collections; к исходному коду.

Hashtable myData = new Hashtable();

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

Природа словаря Hashtable означает, что емкость всегда считается приблизительно. Можно задать начальную приблизительную емкость, передав ее в качестве целочисленного параметра конструктору. Это полезно, когда максимальный размер коллекции известен, поскольку он устраняет необходимость изменения размера хэш-таблицы и повышает производительность.

Hashtable myData = new Hashtable(100);

Все хэш-таблицы имеют коэффициент загрузки. Это соотношение между количеством элементов в коллекции и имеющееся дисковое пространство. Коэффициент загрузки для словаря Hashtable по умолчанию равен 1,0, чтобы обеспечить хороший баланс между требованиями к производительности и памяти. Значение может быть изменено в конструкторе путем указания начальной емкости в виде целого числа и второго, десятичного параметра для коэффициента нагрузки. Допустимые значения коэффициента нагрузки находятся в диапазоне от 0,1 до 1,0. Значение 0.1 указывает на то, что до увеличения емкости хэш-таблицы будет использоваться только одна десятая часть пространства хранения в коллекции. Это дало бы высокоэффективный, но "голодный" на память словарь.

Hashtable myData = new Hashtable(100, 0.1f);

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

Hashtable myData = new Hashtable();
myData.Add("key1","value1");
Hashtable myCopy = new Hashtable(myData);  

Изменение содержимого Hashtable

Добавление элемента

Вы можете добавлять элементы в хэш-таблицу таким же образом, как и для всех коллекций, реализующих IDictionary. Однако есть два важных ограничения. Во-первых, ключ добавляемого элемента не должен быть равен null. Во-вторых, ключ должен быть уникальным. Эти ограничения не применяются к части значения записи Hashtable.

Hashtable myData = new Hashtable();
myData.Add("key1","value1");
myData.Add("key1","value2");        
myData.Add(null,"value2");                

Обновление с помощью key

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

Hashtable fruit = new Hashtable();
fruit["apple"] = "Granny Smith";            
fruit["apple"] = "Golden Delicious";        
fruit["banana"] = "Cavendish";
fruit["cherry"] = "Yamagata";

Чтение информации Hashtable

Одним из ключевых преимуществ коллекции Hashtable является возможность прямого считывания записи, используя ее ключ в качестве ссылки. Это самый простой способ получить элемент. Как и в случае массивов и индексных коллекций, ключ добавляется к имени коллекции в квадратных скобках.

Примечание: в следующих примерах используется тип String для ключей и значений, чтобы продемонстрировать использование Хэштабов. Помните, что при разработке собственных программ как key так и value элементы могут быть любого типа объектов.

Hashtable fruit = new Hashtable();
fruit.Add("apple","Granny Smith");
fruit.Add("banana","Cavendish");
fruit.Add("cherry","Yamagata");
fruit.Add("orange","Seville");
 
string banana = fruit["banana"].ToString();
Console.WriteLine(banana);                  

Итерация с использованием объектов DictionaryEntry

При добавлении элемента в словарь ключевые и значимые элементы объединяются в один объект типа DictionaryEntry. Используя оператор foreach, можно выполнить цикл, пройти по каждому элементу, извлечь его ключ и значение из объекта DictionaryEntry. В следующем примере выводятся сведения о каждой паре ключ / значение в консоль. Обратите внимание, что порядок элементов в коллекции не совпадает с порядком, в котором они были добавлены.

Hashtable fruit = new Hashtable();
fruit.Add("apple","Granny Smith");
fruit.Add("banana","Cavendish");
fruit.Add("cherry","Yamagata");
fruit.Add("orange","Seville");
 
foreach(DictionaryEntry de in fruit)
{
    Console.WriteLine("{0} \t: {1}", de.Key, de.Value);
}
 
/* OUTPUT
 
cherry  : Yamagata
apple   : Granny Smith
banana  : Cavendish
orange  : Seville
 
*/

Values

Во многих случаях вы не захотите перебирать список объектов DictionaryEntry, поскольку вам нужно будет только запрашивать значения. Свойство Values возвращает объект ICollection, содержащий только значения из таблицы Hashtable. Это может быть зациклено напрямую.

Hashtable fruit = new Hashtable();
fruit.Add("apple","Granny Smith");
fruit.Add("banana","Cavendish");
fruit.Add("cherry","Yamagata");
fruit.Add("orange","Seville");
 
foreach(string value in fruit.Values)
{
    Console.WriteLine(value);
}
 
/* OUTPUT
 
Yamagata
Granny Smith
Cavendish
Seville
 
*/

Keys

Свойство Keys аналогично Values. Он возвращает коллекцию ICollection, содержащую все ключи в хэш-таблице.

Hashtable fruit = new Hashtable();
fruit.Add("apple","Granny Smith");
fruit.Add("banana","Cavendish");
fruit.Add("cherry","Yamagata");
fruit.Add("orange","Seville");
 
foreach(string value in fruit.Keys)
{
    Console.WriteLine(value);
}
 
/* OUTPUT
 
cherry
apple
banana
orange
 
*/

ContainsKey

Как описано в предыдущей статье в учебнике Основы C#, все коллекции, реализующие IDictionary, включают метод с именем Contains, который возвращает логическое значение, указывающее, существует ли указанный ключ в коллекции. Hashtable включает в себя этот метод и другой с именем ContainsKey, который обеспечивает точно такую же функциональность.

ContainsValue

Помимо определения того, существует ли определенный ключ в пределах Hashtable, может быть полезно проверить, происходит ли значение в коллекции. ContainsValue работает аналогично Contains и ContainsKey; объект для проверки передается как единственный параметр. Результирующее логическое значение истинно, если объект существует, и ложно в противном случае.

Hashtable fruit = new Hashtable();
fruit.Add("apple","Granny Smith");
fruit.Add("banana","Cavendish");
fruit.Add("cherry","Yamagata");
fruit.Add("orange","Seville");
 
Console.WriteLine(fruit.ContainsValue("Seville"));      // Outputs "True"
Console.WriteLine(fruit.ContainsValue("Valencia"));     // Outputs "False"

Создание потокобезопасной оболочки Hashtable

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

Hashtable myDictionary = new Hashtable();
Hashtable myThreadSafe = Hashtable.Synchronized(myDictionary);
Console.WriteLine(myThreadSafe.IsSynchronized);