Хэширование для оптимизации поиска данных
Определение хэш-функции
Хэшированием данных называется преобразование входных данных произвольной длины в данные фиксированной длины. Хэширование производится последовательным выполнением операций преобразования (суммирование, сдвиг и т.п) по заранее определённому алгоритму над блоками данных фиксированной длины. Размер блоков данных, над которыми производится преобразование, как правило, определяется размером выходных данных. В том случае, когда размер входных данных не позволяет выполнить их разбиение на блоки, данные могут либо дополнятся либо обрезаться. Алгоритм преобразования называется хэш-функцией, а полученные в результате данного преобразования данные - хэш-кодом.
Для текста хэш-кодом может быть первая буква в слове, такой способ хэширования широко распространён в «быту», это обычная записная книжка или словарь иностранных слов.
Основные свойства хэш-функций и их практическое применение
Детерминированность
Для двух одинаковых наборов данных хэш-функция должна возвращать одинаковый код. Это свойство используется для контроля целостности данных в системах хранения и передачи. При отправлении исходные данные дополняются вычисленным по этим данным хэш-кодом, который также называют контрольной суммой. При получении данных производится вычисление контрольной суммы полученных данных и сравнение её с полученной. Если контрольные суммы различны значит в данные были внесены изменения.
Отсутствие биективности преобразования
Поскольку размер выходых данных фиксирован а рамер входных может быть произвольным, то в общем случае, при хэшировании происходит потеря части исходных данных. Поэтому данное преобразование является необратимым или односторонним. Если использовать математическую терминологию, хэш-преобразование в общем случае не является биективным. Необратимость хэш-функций используется в криптографии и системах защиты информации для предотвращения восстановления зашифрованных ключей (паролей, если по простому). Требование необратимости преобразования является одним из требований криптографической стойкости хэш-функции.
Фиксированный размер хэш-кода
Фиксированность размера хэш-кода означает константность времени его обработки, например, сравнения. Поэтому предварительное хэширование данных позволяет оптимизировать определённые операции обработки данных, такие как поиск.
Оптимизация поиска и сортировки данных
С физической точки зрения меньший, по-сравнению с исходными данными, размер хэш-кода уменьшает количество данных, передаваемых между оперативной памятью или любым иным устройством хранения данных и процессором, что сокращает время выполнения операций. Наиболее распространённым вариантом хэш-кода является целое число, сравнение которых выполнялось за один процессорный такт уже где-то в эпохе компьютерного плейстоцена.
В качестве хэш-кода можно использовать не только значение, полученное на основе преобразования данных, но и адрес исходных данных, например, адрес в памяти или смещение относительно начала файла. Использование ассоциативных массивов (словарей) в которых в качестве ключей используются подобные адреса позволяет осуществлять такие операции как сортировка или фильтрация без дорогостоящих операций манипулирования данными непосредственно на носителе.
Фиксированный размер хэш-кода позволяет хранить коды в статических структурах данных, массивах, векторах, записях. Поскольку процесс вычисления адреса элемента в статических структурах константен (т.е. не зависит от количества её элементов), мы так же можем получить выигрыш в производительности.
Используя хэш-код можно обойти технологические ограничения на размер хранимых данных, например, размер индекса MS SQL Server ограничен 900 байтами, что для строки произвольной длины явно мало, а для хранения хэш-кода даже криптографического размера вполне достаточно.
Примеры оптимизации
Оптимизация времени поиска текста
Использование предварительного хэширования позволяет значительно сократить время поиска в массиве строк. Очевидно, что время, необходимое для посимвольного сравнения двух строк, линейно зависит от количества символов в этих строках. В тех случаях, когда строки сравниваются многократно, устранение линейной зависимости операций сравнения посредством предварительного хэширования позволяет значительно сократить время поиска строки.
Ниже приведен простой пример оптимизации поиска по полному пути в списке файлов. Для оптимизации поиска используется словарь, построенный на базе хэш-кода строк. Исходная задача: определить существование указанного файла в списке из нескольких тысяч файлов. В качестве тестовой платформы выбран Microsoft .NET. Тестовая программа исполнялась на процессоре Intel Core2.
Исходные данные:16749 достаточно длинных строк (имена всех файлов и папок каталога «C:\Program Files (x86)\Microsoft Visual Studio 9.0»)
Поиск прямым сравнением
В данном варианте происзводится поиск прямым сравнением строк хранящихся в списке folders.
Random r = new Random();
int iterations = 7000;
{
Stopwatch sw = new Stopwatch();
sw.Reset();
for (int i = 0; i < iterations; i++)
{
int index = r.Next(0, folders.Count - 1);
string value = folders[index];
sw.Start();
string result = folders.Find(x => { return string.Compare(x, value, true) == 0; });
sw.Stop();
}
}Оптимизированный поиск
В данном варианте по исходному массиву путей (хранящемуся в списке folders) строится словарь списков. Ключ в данном словаре это хэш-код строки, а значение — список различающихся строк с одинаковым хэш-кодом. Перед поиском вычисляется хэш-код строки, которую необходимо найти в списке после чего проверяется наличие данного ключа в словаре. Если ключ существует, по нему получается список строк, в котором далее выполняется прямой поиск. Хэширование позволяет значительно сократить количество строк, в которых необходимо произвести поиск прямым сравнением. Организация хранения ключей словаря в виде бинарного дерева так же позволит сократить количество операций сравнения ключей (от линейной зависимости до логарифмической).
IEnumerable<IGrouping<int, string>> d = folders.GroupBy(x => { return x.GetHashCode(); });
Dictionary<int, List<string>> map = d.ToDictionary(x => x.Key, y => y.ToList());
Stopwatch sw = new Stopwatch();
for (int i = 0; i < iterations; i++)
{
int index = r.Next(0, folders.Count - 1);
string value = folders[index];
sw.Start();
int code = value.GetHashCode();
if (map.ContainsKey(code))
{
string result = map[code].Find(x => { return string.Compare(x, value, true) == 0; });
}
sw.Stop();
}Время выполнения операций
| Кол-во итераций | Прямой поиск (мс) | Поиск в хэшированных данных (мс) |
| 100 | 150 | 0 (меньше одной миллисекунды) |
| 1000 | 1420 | 1 |
| 3000 | 4298 | 2 |
| 7000 | 10454 | 5 |
Как нетрудно заметить, даже на ста итерациях разница во времени составляет два порядка.
Оптимизация размера текстовых индексов MS SQL Server
Индексирование текста в MS SQL связано с определёнными ограничениями (ограничения других СУБД мне неизвестны, поэтому писать о них ничего не буду). Во-первых, при непосредственной индексации строк размер индекса получается нерационально большим. Во-вторых, существуют ограничения на размер индексируемых данных (зависящие от реализации СУБД). Данные ограничения могут создать определённые сложности при проектировании систем хранения данных, максимальный размер которых не может быть известен на этапе проектирования. Для MS SQL размер индекса ограничен 900 байтами, соответственно размер индексированной колонки для хранения unicode строк не может превышать 450 символов.
Ниже приведён пример позволяющий обойти данные ограничения посредством хэширования хранимых строк. Для оценки разницы в размерах индекса проведём простой тест. Создадим две таблицы для хранения текста, в каждой из них будет колонка первичного ключа и колонка с текстовыми данными. Во-второй таблице дополнительно добавим вычисляемую колонку хэш-кода строки. Для первой таблице создадим индекс по текстовым данным, во второй по хэш-коду.
Заполним таблицы текстовыми данными (имена файлов и папок каталога «C:\Program Files (x86)\Microsoft Visual Studio 9.0» обрезанные по длине в 450 символов).
Таблица с индексированием текстовой колонки
В данной таблице две колонки — колонка первичного ключа ID и колонка Value, для который создан некластеризованный, не уникальный индекс. Установим максимальный размер колонки Value в 450 unicode символов.
CREATE TABLE [dbo].[TextIndex](
[ID] [int] IDENTITY(1,1) NOT NULL,
[Value] [nvarchar](450) NOT NULL,
CONSTRAINT [PK_TextIndex] PRIMARY KEY CLUSTERED ([ID] ASC)
WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF,
IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON,
ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]) ON [PRIMARY]
CREATE NONCLUSTERED INDEX [IX_TextIndex] ON [dbo].[TextIndex] ([Value] ASC)
WITH (PAD_INDEX = OFF,
STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF,
IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF,
ONLINE = OFF, ALLOW_ROW_LOCKS = ON,
ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
Таблица, где в качестве индекса используется хэш-код
В данной таблице три колонки — колонка первичного ключа ID, не индексированная колонка Value и вычисляемая колонка Hash, для который создан некластеризованный, не уникальный индекс. Поскольку в данном случае данные в колонке Value не индексируются, максимальный размер данных данной колонки ограничен длиной данных nvarchar(max), однако для чистоты эксперимента так же ограничим её 450 unicode символами.
Вычисление хэш-кода производится с помощью стандартной функции hasbytes, значение которой затем приводится к целому числу вычислением остатка от целочисленного деления на максимальное значение типа int.
[Hash] AS (hashbytes('MD5',[value]) % (2147483647)).
CREATE TABLE [dbo].[HashIndex](
[ID] [int] IDENTITY(1,1) NOT NULL,
[Hash] AS (hashbytes('MD5',[value])%(2147483647)),
[Value] [nvarchar](450) NOT NULL,
CONSTRAINT [PK_HashIndex] PRIMARY KEY CLUSTERED([ID] ASC)
WITH (PAD_INDEX = OFF,
STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF,
ALLOW_ROW_LOCKS = ON,
ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]) ON [PRIMARY]
Статистика использование дисковой памяти
| Имя таблицы | Число записей | Данные (КБ) | Индексы (КБ) |
| HashIndex | 10500 | 2114 | 280 |
| TextIndex | 10500 | 2114 | 3680 |
Как нетрудно заметить разница в размерах индекса примерно пятнадцать раз.