Это только основы использования хеш-контейнеров. Также имеется набор параметров шаблона, которые позволяют указать используемую хеш-функцию, функцию, проверяющую ключи на эквивалентность, и объект, используемый для распределения памяти. Я опишу их немного позже.
В большинстве библиотек есть четыре хеш-контейнера, и они похожи на другие ассоциативные контейнеры стандартной библиотеки (т.е.
map
и
set
). Это
hash_map
,
hash_multimap
,
hash_set
и
hash_multiset
. хеш-контейнеры реализуются с помощью хеш- таблицы. Хеш-таблица — это структура данных, которая обеспечивает постоянное время доступа к элементам, используя для этого хеш-функцию перехода к месту, близкому к хранению искомого объекта, а не проход по древовидной структуре. Разница между
hash_map
и
hash_set
состоит в том, как данные хранятся в хеш-таблице.
Объявления контейнеров, использующих хеш-таблицу, в STLPort выглядят так.
hash_map<Key, // Тип ключа
Value, // Тип значения,
// связанного с ключом
HashFun = hash<Key>, // Используемая хеш-функция
EqualKey = equal_to<Key> // Функция, используемая для
// проверки равенства ключей
Alloc = alloc>; // Используемый распределитель памяти
hash_set<Key, // Тип ключа
HashFun = hash<Key>, // Используемая хеш-функция
EqualKey = equal_to<Key>, // Функция, используемая для
// проверки равенства ключей
Alloc = alloc>; // Используемый распределитель памяти
hash_map
— это хеш-таблица, которая хранит значения как объекты
pair<const Key, Data>
. Это означает, что когда я буду далее описывать хеш-таблицы, «элементы» в таблице будут означать пары ключ/значение.
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 включает в
<hash_map>
и
<hash_set>
такую хеш-функцию как шаблон функции. Однако эта функция не работает для любого объекта, так как невозможно создать общей хеш-функции, которая бы работала с любым вводом. Вместо этого имеется несколько специализированных встроенных типов, наиболее часто используемых для ключей в хеш-таблицах. Например, если требуется посмотреть, как выглядит значение хеша, хешируйте строку символов.
std::hash<const char*> 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
. Кажется, что их очень много, но в целом это означает, что библиотека содержит встроенные хеш-функции, которые поддерживают символьные строки и числа. Если требуется хешировать что-то другое, то просто укажите собственную хеш-функцию.
При помещении элемента в хеш-таблицу она определяет, какому участку принадлежит элемент, используя оператор взятия остатка от деления и число участков, т.е.
hashFun(key) % bucket_count
. Это быстрый оператор, который указывает непосредственно на индекс в главном векторе, по которому начинается участок.
Хеш-контейнер можно использовать как обычный ассоциативный контейнер, используя для добавления элементов в, скажем,
hash_map
оператор
operator[]
. Разница заключается в том, что вы знаете, что вставка и поиск займут постоянное время, а не логарифмическое. Рассмотрим пример 6.9, который содержит простой класс, отображающий имена логинов на объекты
Session
. Он использует некоторые из возможностей хеш-контейнеров, описываемых в этом рецепте.