12. Хэш-таблицы. Коллизии. Класс Dictionary.

1. Хэш-таблицы.

Продолжаем говорить о структурах данных.

Сегодня мы поговорим о структуре, которая позволяет найти элемент за О(1). Напоминаем, что и в обычном массиве, и в динамическом списке эта операция осуществляется за О(n).

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

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

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

2. Коллизии.

Естественно, возникает вопрос, почему невозможно такое, что мы попадем дважды в одну ячейку массива, ведь представить функцию, которая ставит в сравнение каждому элементу совершенно различные натуральные числа просто невозможно. Именно так возникает проблема коллизии.

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

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

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

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

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

Технология сцепления элементов (метод цепочек) состоит в том, что элементы множества, которым соответствует одно и то же хэш-значение, связываются в цепочку-список. В позиции номер i хранится указатель на голову списка тех элементов, у которых хэш-значение ключа равно i; если таких элементов в множестве нет, в позиции i записан NULL.

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

3. Класс Dictionary.

В C# есть несколько классов для реализации хэш-таблиц. Рассмотрим один из самых популярных.

Словарь (dictionary) — это обобщенная версия Hashtable. Главное свойство dictionary— быстрый поиск с помощью ключей. Можно также добавлять и удалять элементы, наподобие того как это делается в структуре List, но без расходов производительности, связанных с необходимостью смещения последующих элементов в памяти.

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

• Add() - добавляет в словарь пару "ключ-значение", определяемую параметрами key и value. Если ключ key уже находится в словаре, то его значение не изменяется, и генерируется исключение ArgumentException.
• ContainsKey() - возвращает логическое значение true, если вызывающий словарь содержит объект key в качестве ключа; а иначе — логическое значение false.
• ContainsValue() - возвращает логическое значение true, если вызывающий словарь содержит значение value; в противном случае — логическое значение false.
• Remove() - удаляет ключ key из словаря. При удачном исходе операции возвращается логическое значение true, а если ключ key отсутствует в словаре — логическое значение false.

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

• Keys - получает коллекцию ключей.
• Values - получает коллекцию значений.

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

Dictionary<int, string> countries = new Dictionary<int, string>(5);
countries.Add(1, "Russia");
countries.Add(3, "Great Britain");
countries.Add(2, "USA");
countries.Add(4, "France");
countries.Add(5, "China");

foreach (KeyValuePair<int, string> keyValue in countries)
{
    Console.WriteLine(keyValue.Key + " - " + keyValue.Value);
}

// получение элемента по ключу
string country = countries[4];
Console.WriteLine(country);

// изменение объекта
countries[4] = "Spain";

// удаление по ключу
countries.Remove(2);

Console.WriteLine();
foreach (KeyValuePair<int, string> keyValue in countries)
{
    Console.WriteLine(keyValue.Key + " - " + keyValue.Value);
}

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

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

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

class Localization
{
    public Localization(string russian, string german)
    {
        Russian = russian;
        German = german;
    }
    
    public string Russian { get; set; }
    public string German { get; set; }
}

public static void Main(string[] args)
{
    Dictionary<string, Localization> words = new Dictionary<string, Localization>();
    words.Add("book", new Localization("Книга", "Buch"));
    words.Add("pen", new Localization("Ручка", "Griff"));
    words.Add("paper", new Localization("Бумага", "Papier"));

    foreach (KeyValuePair<string, Localization> keyValue in words)
    {
        // keyValue.Value представляет класс Localization
        Console.WriteLine(keyValue.Key + " - " + keyValue.Value.Russian);
    }

    // перебор ключей
    foreach (string key in words.Keys)
    {
        Console.WriteLine(key);
    }

    // перебор по значениям
    foreach (Localization word in words.Values)
    {
        Console.WriteLine(word.Russian);
    }
}

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

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

Dictionary<string, Localization > words = new Dictionary<string, Localization>();
Dictionary.Add("eraser", new Localization ("Стерка", "Radiergummi"));
Dictionary["eraser"] = new Localization ("Ластик", "Radiergummi");

Несмотря на то, что изначально в словаре нет ключа "eraser" и соответствующего ему элемента, то он все равно будет установлен. Если же он есть, то элемент по ключу "eraser" будет заменен на новый объект new Localization ("Ластик", "Radiergummi").

Инициализация словарей.

Инициализировать словари можно следующим образом:

Первый вариант:

Dictionary<string, string> countries = new Dictionary<string, string>
{
     {"Франция", "Париж"},
     {"Германия", "Берлин"},
     {"Великобритания", "Лондон"}
};

foreach(var pair in countries)
     Console.WriteLine("{0} - {1}", pair.Key, pair.Value);

Второй вариант:

Dictionary<string, string> countries = new Dictionary<string, string>
{
     ["Франция"]= "Париж",
     ["Германия"]= "Берлин",
     ["Великобритания"]= "Лондон"
};

Итоги занятия.