Анализ структур данных. Часть 2: Очередь, стек и хеш-таблица
Страница 7. Класс System.Collections.Hashtable

Класс System.Collections.Hashtable

Базовая библиотека классов .NET Framework iсодержит реализацию хеш-таблицы в классе Hashtable. При добавлении элемента в Hashtable вы должны передать не только данные, но и уникальный ключ, по которому этот элемент может быть найден. Как ключ так и данные могут быть любого типа. В нашем примере с сотрудникамиключом был номер социального страхования. Элементы добавляются в Hashtable с помощью метода Add().

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

using System;
using System.Collections;
public class HashtableDemo
{
 private static Hashtable ages = new Hashtable();
 public static void Main()
 {
 // Добавим несколько значений, проиндексированных строковым ключом в хеш-таблицу
 ages.Add("Scott", 25);
 ages.Add("Sam", 6);
 ages.Add("Jisun", 25); 
 // Найдем элемент по его ключу
 if (ages.ContainsKey("Scott"))
 {
 int scottsAge = (int) ages["Scott"];
 Console.WriteLine("Scott is " + scottsAge.ToString());
 }
 else
 Console.WriteLine("Scott is not in the hash table...");
 }
}

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

// проход по всем элементам хеш-таблицы
foreach(string key in ages.Keys)
 Console.WriteLine("Value at ages[\"" + key + "\"] = " + ages[key].ToString());

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

Value at ages["Jisun"] = 25
Value at ages["Scott"] = 25
Value at ages["Sam"] = 6

Несмотря на то, что порядок добавления элементов был "Scott," "Sam," "Jisun." Хеш-функция класса Hashtable

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

Это магическое преобразование осуществляется методом GetHashCode(), определенным в классе System.Object. Реализация метода GetHashCode() класса Object по умолчанию возвращает уникальное целое число, которое гарантированно не изменится за время жизни объекта. Поскольку все типы прямо наследуются от класса Object, всем объектам доступен этот метод. Поэтому строка или любой другой тип может быть представлен уникальным числом.

Определение хеш-функции класса Hashtable таково:

H(key) = [GetHash(key) + 1 + (((GetHash(key) >> 5) + 1) % (hashsize - 1))] % hashsize

Эдесь GetHash(key) - это по умолчанию значение, возвращаемое при вызове метода GetHashCode() объекта key ( вы можете определить собственную функцию GetHash()). GetHash(key) >> 5 вычисляет хэш для key после чего выполняет побитовый сдвиг вправо на 5 бит, что равносильно делению результата хеширования на 32. Как уже обсуждалось ранее в этой статье, оператор % служит для нахождения остатка от деления одного числа на другое. hashsize - это общее число всех ячеек в хеш-таблице. (Вспомним, что x % y возвращает остаток от деления x на y и что этот остаток лежит в диапазоне от 0 до y - 1.) Благодаря операциям взятия модуля конечный результат функции H(key) всегда будет от 0 до hashsize - 1. А поскольку hashsize - это число всех ячеек в хеш-таблице, то результат, выданный хеш-функцией, будет всегда лежать в допустимых пределах.

Разрешение коллизий в классе Hashtable

Вспомним, что при вставке или удалении элемента из хеш-таблицы может возникнуть коллизия. При вставке элемента необходимо найти пустую ячейку; а при выборке элемента, его фактическое местоположение должно быть найдено, если его нет в ожидаемой позиции. Ранее мы кратко рассмотрели дваметода разрешения коллизий - линейную и квадратичную последовательность проб. Класс Hashtable использует другой метод, называемый повторным хешированием (rehasing). В некоторых источниках этот метод называют двойным хешированием (double hashing).

Повторное хеширование работает следующим образом. Пусть имеется набор хеш-функций, H1 H2 …. Hn . При вставке или извлечении элемента из хеш-таблицы изначально используется хеш-функция H1. Если в результате мы получаем коллизию, то далее пробуется функция H2 и т.д. до Hn . В предыдущем разделе я продемонстрировал лишь одну хеш-функцию-пусть она будет начальной хеш-функцией (H1). Остальный хеш-функции будут похожи на H1, отличаясь от нее лишь множителем k. Т.е. k-я хеш-функция Hk определена так:

Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize - 1)))] % hashsize

Математическое примечание В случае повторного хеширования важно, чтобы каждая ячейка хеш-таблица была посещена ровно 1 раз после hashsize проб. То есть, для каждого ключа мы не хотим, чтобы функции Hi и Hj выдавали одно и то же значение хеша. В случае хеш-функций класса Hashtable это свойство выполняется, если результат вычисления (1 + (((GetHash(key) >> 5) + 1) % (hashsize - 1)) и hashsize взаимно просты. (Два числа называются взаимно простыми, если они не имеют общих делителей кроме единицы). Эти двачисла будут гарантированно взаимно просты, если hashsize - простое число.

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