Применение хеш-функций, SHA1, GetHashCode, HashSet и Dictionary

Вне сомнений, одной из часто пренебрегаемых по незнанию возможностей .NET Framework являются хеш-алгоритмы. Данная статья познакомит читателя с тем, чем же на самом деле является хеш-сумма, как она применяется в системах безопасности, как работают классы Dictionary и HashSet в .NET Framework и почему в ряде случаев важно использовать именно их вместо обычных списков.

Хеш-функция
 принимает массив данных произвольной длины, а возвращает хеш-сумму — массив строго определённой длины, условно-уникальный для конкретного входящего массива данных, без возможности обратного преобразования в исходные данные. Таким образом хеш-функция должна быть способной сгенерировать определённого размера массив данных как для пустой строки, так и для файла с фильмом размером в 20 Гб. При этом, при изменении хотя бы одного бита в файле с фильмом, хеш-сумма должна измениться как можно более серьёзно. 

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

Рассмотрим использование в .NET очень популярной хеш-функции SHA1, которая производит из любого набора данных 20-байтную уникальную хеш-сумму:
var sha1 = SHA1.Create();
Action<string> drawHash = (word) => 
	Console.WriteLine(Convert.ToBase64String(sha1.ComputeHash(Encoding.UTF8.GetBytes(word))));
drawHash("Thing 1"); // выводит nkog+V/vSxwuNc5WEasSYLAXqWc=
drawHash("Thing 2"); // выводит EvZt0pEmKYN7ec4mDzHuR5lYgq0=
Примечание: класс SHA1 находится в пространстве имён System.Security.Cryptography.

Как можно заметить, замена всего лишь одного символа в строке приводит к кардинальной смене хеш-суммы. Однако при этом длина суммы остаётся неизменной, и самое главное — на любом компьютере, под управлением любой ОС, в любое время года, для конкретной строки, конкретным хеш-алгоритмом (SHA1) будет сгенерирована только такая хеш-сумма и никакая другая. Благодаря этим свойствам, хеш-сумма позволяет избежать хранения паролей пользователей в базе данных. Хранение паролей в базе данных является сомнительной практикой, поскольку при осуществлении любого вида взлома резко увеличиваются шансы получения паролей злоумышленниками. Даже если они хранятся в зашифрованном виде, злоумышленник сможет их получить, узнав ключи и алгоритм шифрования.

Поэтому, принятой практикой является хранение хеш-суммы пароля. При задании пароля в базе данных сохраняется его хеш-сумма, при вводе пароля пользователем хеш-сумма снова вычисляется и проверяется на соответствие сохранённой в базе данных.
var sha1 = SHA1.Create();
Func<string, string> getHash = (word) => Convert.ToBase64String(sha1.ComputeHash(Encoding.UTF8.GetBytes(word)));
 
var password1 = "word";
var password2 = "word2";
 
var hash1 = getHash(password1);
var hash2 = getHash(password2);
 
Console.WriteLine("Hashes are equal:             {0}", 
	hash1 == hash2); // FALSE, хеш-суммы разные
Console.WriteLine("Password1 equals to its hash: {0}", 
	password1 == hash1); // FALSE, хеш-сумма всегда отличается от входящих данных
Console.WriteLine("Password1 hash is equal to computed earlier: {0}", 
	getHash(password1) == hash1); // TRUE, хеш-сумма всегда одинаковая для конкретного набора данных
Console.WriteLine("Password2 hash is equal to computed earlier: {0}",
	getHash(password2) == hash2); // TRUE, хеш-сумма всегда одинаковая для конкретного набора данных
Console.WriteLine("Password1 hash suits Password2 hash: {0}",
	getHash(password1) == hash2); // FALSE, хеш-сумма отличается
Приведённый выше код демонстрирует, что функция getHash(word) (строковая обёртка над SHA1) всегда возвращает одинаковую уникальную хеш-сумму для введённого значения.

Однако, у хеш-функций есть и ещё одно замечательное применение, которое очень часто позволяет невероятно существенно улучшить производительность конкретных систем. Допустим, существует список из 500 строк разной длины, и необходимо проверить — присутствует ли в нём определённая строка.
const int count = 500;
const string neededToken = "specific words";
const string unavailableToken = "other words";
List<string> tokens = new List<string>();
Random random = new Random();
for (var i = 0; i < count; i++) {
	byte[] buffer = new byte[i];
	random.NextBytes(buffer);
	tokens.Add(Convert.ToBase64String(buffer));
}
tokens.Add(neededToken);
 
Stopwatch stopwatch = Stopwatch.StartNew();
for (var i = 0; i < 10000; i++) {
	var exists = tokens.Contains(neededToken);
	exists = tokens.Contains(tokens.First());
	exists = tokens.Contains(unavailableToken);
}
stopwatch.Stop();
Console.WriteLine("Ms: {0}", stopwatch.ElapsedMilliseconds); // 188
Примечание: класс Stopwatch находится в пространстве имён System.Diagnostics.

Выполнение кода показывает, что 10 000 проверок на то, присутствуют ли в списке последний элемент, первый элемент, и недобавленный элемент, занимают на моём компьютере 188 миллисекунд. Если учесть, что в реальных проектах вызов Contains запросто может встретиться внутри двух вложенных циклов по 20 и 500 итераций соответственно, число проверок в 10 000 вполне отражает встречающееся в действительности. Contains может содержаться и в реализации get-методов для свойств, что может ещё больше затруднить поиск узкого места по производительности (если конечно не использовать профайлер, который сразу это покажет).

Проблема заключается в том, что Contains поочерёдно проверяет каждый элемент списка на равенство искомому. Проверка строки на равенство — достаточно долгая операция, особенно если строки имеют одинаковые длину и некоторую часть первых символов, т.к. в этом случае необходимо посимвольво сравнивать две строки.

Попробуем оптимизировать код, добавив к нему создание второго списка, содержащего вместо строк целые числа–хеш-суммы соответствующих строк первого списка. Для вычисления хеш-сумм воспользуемся стандартным методом Object.GetHashCode(), который реализован в классе String таким образом, чтобы всегда возвращать условно-уникальное целое число для конкретной строки. (Примечание: функцию Object.GetHashCode() согласно документации .NET Framework нельзя использовать в задачах по безопасности, подробнее можно узнать в блоге Эрика Липперта.)
const int count = 500;
const string neededToken = "specific words";
const string unavailableToken = "other words";
List<string> tokens = new List<string>(count);
Random random = new Random();
for (var i = 0; i < count; i++) {
	byte[] buffer = new byte[i];
	random.NextBytes(buffer);
	tokens.Add(Convert.ToBase64String(buffer));
}
tokens.Add(neededToken);
 
Stopwatch stopwatch = Stopwatch.StartNew();
List<int> tokenHashes = tokens.Select(t => t.GetHashCode()).ToList();
for (var i = 0; i < 10000; i++) {
	var exists = tokenHashes.Contains(neededToken.GetHashCode());
	exists = tokenHashes.Contains(tokens.First().GetHashCode());
	exists = tokenHashes.Contains(unavailableToken.GetHashCode());
}
stopwatch.Stop();
Console.WriteLine("Ms: {0}", stopwatch.ElapsedMilliseconds); // 75
Время выполнения уменьшилось больше, чем в два раза! Это произошло благодаря тому, что исходный список превратился в список структур куда меньшего размера (целых чисел), сравнение которых происходит намного быстрее, чем сравнение исходных строк. Тем не менее, держать в уме два списка очень неудобно — добавив строку в первый список, будет необходимо добавлять её хеш-сумму во второй. К тому же, такой подход не учитывает того, что на самом деле две разные строки могут вернуть одинаковый GetHashCode, что приведёт к тому, что код будет ошибочно полагать, что список содержит в себе строку, которая на самом деле просто имеет одинаковое значение GetHashCode с некоторой строкой из списка.

К счастью, в .NET Framework уже существует нужный нам аналог List<T> — HashSet<T>. HashSet<T> содержит уникальные экземпляры типа T и обладает способностью выполнять операцию Contains молниеносно:
const int count = 500;
const string neededToken = "specific words";
const string unavailableToken = "other words";
HashSet<string> tokens = new HashSet<string>();
Random random = new Random();
for (var i = 0; i < count; i++) {
	byte[] buffer = new byte[i];
	random.NextBytes(buffer);
	tokens.Add(Convert.ToBase64String(buffer));
}
tokens.Add(neededToken);
 
Stopwatch stopwatch = Stopwatch.StartNew();
for (var i = 0; i < 10000; i++) {
	var exists = tokens.Contains(neededToken);
	exists = tokens.Contains(tokens.First());
	exists = tokens.Contains(unavailableToken);
}
stopwatch.Stop();
Console.WriteLine("Ms: {0}", stopwatch.ElapsedMilliseconds); // 3
Всего 3 миллисекунды. Это делает очевидным, что при необходимости выполнения операции Contains на списке, пусть даже от одного раза, лучше использовать HashSet<T> вместо List<T>. В дополнение к этому, HashSet<T> построен на использовании хеш-таблицы, что делает его свободным от рисков, связанных с коллизиями GetHashCode().

Примечание: во всех примерах выше значение переменной exists изменяется как true, true, false, это можно проверить в режиме отладки (Debug). Пример со вторым списком составлен только для демонстрации того, как сильно ускоряется выполнение за счёт сокращения сравниваемых данных, в реальных случаях применение такого подхода бессмысленно.

Далее рассмотрим следующий случай: существует список объектов, у каждого из которых есть уникальный идентификатор. Задача заключается в том, чтобы найти в этом списке объект с нужным идентификатором.
class PersonEntity {
	public int Id { get; set; }
	public string FirstName { get; set; }
	public string LastName { get; set; }
}
static void Main(string[] args) {
	const int count = 500;
	List<PersonEntity> people = new List<PersonEntity>();
	Random random = new Random();
	for (var i = 0; i < count; i++) {
		byte[] buffer = new byte[i];
		random.NextBytes(buffer);
		people.Add(new PersonEntity {
			Id = i,
			FirstName = Convert.ToBase64String(buffer),
			LastName = "Smith"
		});
	}
 
	Stopwatch stopwatch = Stopwatch.StartNew();
	for (var i = 0; i < 10000; i++) {
		var personById = people.First(person => person.Id == count - 1);
	}
	stopwatch.Stop();
	Console.WriteLine("Ms: {0}", stopwatch.ElapsedMilliseconds); // 170
}
Задача решена, однако 10 000 итераций выливаются в 170 миллисекунд. Но ведь нам уже известно, что даже 10 000 итераций трёх вызовов поиска строки в списке должны занимать не больше 3-х миллисекунд. А сравниваются в данном случае даже не сами объекты или строки, а целые числа–идентификаторы. На помощь приходит класс Dictionary<TKey, TValue>, хранящий соответствие ключа (на самом деле, его хеш-суммы) значению, и весьма оптимизированный для быстрого поиска благодаря использованию хеш-таблицы. В дополнение, начиная с версии 3.5, .NET Framework содержит удобный extension-метод ToDictionary для упрощения процедуры создания словаря из любого перечисляемого (IEnumerable<T>).
class PersonEntity {
	public int Id { get; set; }
	public string FirstName { get; set; }
	public string LastName { get; set; }
}
static void Main(string[] args) {
	const int count = 500;
	List<PersonEntity> people = new List<PersonEntity>();
	Random random = new Random();
	for (var i = 0; i < count; i++) {
		byte[] buffer = new byte[i];
		random.NextBytes(buffer);
		people.Add(new PersonEntity {
			Id = i,
			FirstName = Convert.ToBase64String(buffer),
			LastName = "Smith"
		});
	}
 
	Stopwatch stopwatch = Stopwatch.StartNew(); 
	Dictionary<int, PersonEntity> peopleById = people.ToDictionary(person => person.Id);
	for (var i = 0; i < 100000; i++) {
		var personById = peopleById[count - 1];
	}
	stopwatch.Stop();
	Console.WriteLine("Ms: {0}", stopwatch.ElapsedMilliseconds); // 10
}
Чтобы увидеть точное значение, пришлось увеличить количество итераций цикла поиска в 10 раз. Получилось 10 миллисекунд. Таким образом, код с Dictionary почти в 170 раз быстрее обычного поиска по списку. Но и это ещё не всё. Увеличив количество объектов в списке (константа count) до 5000, увидим, что 10 000 итераций обычного поиска по списку знимают уже 2114 мс, в то время как такое же количество итераций поиска по Dictionary занимает всё так же порядка 1 мс (100 000 итераций - 12 мс). Таким образом, можно сделать вывод, что если где-либо несколько раз необходимо произвести поиск объекта с определённым идентификатором, лучше всего реализовать это при помощи Dictionary.

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

Применение хеш-функций серьёзным образом помогает решать многие повседневные задачи, данная статья лишь поверхностно описывает способы реализации некоторых из них в .NET Framework.

P.S. Благодарю за комментарии Romanchik и Trolzen, некоторые формулировки были отредактированы.
Статья была впервые опубликована 25-го августа 2010 года в блоге.