Д. Стефенс - C++. Сборник рецептов

В большинстве библиотек есть четыре хеш-контейнера, и они похожи на другие ассоциативные контейнеры стандартной библиотеки (т.е. mapи set). Это hash_map, hash_multimap, hash_setи hash_multiset. хеш-контейнеры реализуются с помощью хеш- таблицы. Хеш-таблица — это структура данных, которая обеспечивает постоянное время доступа к элементам, используя для этого хеш-функцию перехода к месту, близкому к хранению искомого объекта, а не проход по древовидной структуре. Разница между hash_mapи hash_setсостоит в том, как данные хранятся в хеш-таблице.

Объявления контейнеров, использующих хеш-таблицу, в STLPort выглядят так.

hash_map

Value, // Тип значения,

// связанного с ключом

HashFun = hash, // Используемая хеш-функция

EqualKey = equal_to // Функция, используемая для

// проверки равенства ключей

Alloc = alloc>; // Используемый распределитель памяти

hash_set

HashFun = hash, // Используемая хеш-функция

EqualKey = equal_to, // Функция, используемая для

// проверки равенства ключей

Alloc = alloc>; // Используемый распределитель памяти

hash_map— это хеш-таблица, которая хранит значения как объекты pair. Это означает, что когда я буду далее описывать хеш-таблицы, «элементы» в таблице будут означать пары ключ/значение. hash_mapне хранит ключи значение по отдельности (как и map). hash_setпросто хранит ключ как значение.

Параметр шаблона HashFun— это функция, которая превращает объекты типа Keyв значения, которые могут быть сохранены как size_t. Более подробно это описывается ниже. Параметр шаблона EqualKey— это функция, которая принимает два аргумента и, если они эквивалентны, возвращает true. В контейнерах hash_mapи hash_setдва ключа не могут быть равны, hash_multimapи hash_multisetмогут содержать по нескольку одинаковых ключей. Как и в случае с другими контейнерами, Alloc— это используемый распределитель памяти.

Хеш-таблица содержит две части. В ней есть относительно большой вектор, где каждый индекс это «участок». Каждый из участков является на самом деле указателем на первый узел в относительно коротком одно- или двухсвязном списке (в STLPort — односвязном). Именно в этих списках и хранятся данные. Чтобы получить число участков в хеш-контейнере, используйте метод bucket_count. Рисунок 6.3 дает представление о том, как выглядит в памяти хеш-отображение.

Рис. 6.3. Хеш-таблица

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

Если вы незнакомы с тем, что такое «хеширование», то это очень простая концепция. Если есть какое-то значение (скажем, массив типа char), то хеш-функция для него — это функция, которая принимает один аргумент и возвращает значение хеша типа size_t(т.е. число). В идеале требуется хеш-функция, которая генерирует уникальные значения хешей, но она не обязана это делать. Эта функция в математическом смысле неоднозначна: несколько строк типа string могут иметь одно и то же значение хеша. Далее я скажу, почему это не страшно.

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

std::hash hashFun;

std::cout << "\"Hashomatic\" хешируется как "

<< hashFun("Hashomatic") << '\n';

Вы увидите что-то похожее на следующее.

"Hashomatic" хешируется как 189555649

STLPort предоставляет специализации для следующих типов: char*, const char*, char, unsigned char, signed char, short, unsigned short, int, unsigned int, longи unsigned long. Кажется, что их очень много, но в целом это означает, что библиотека содержит встроенные хеш-функции, которые поддерживают символьные строки и числа. Если требуется хешировать что-то другое, то просто укажите собственную хеш-функцию.