C++. Сборник рецептов

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

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

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

std::hash<const char*> hashFun;
std::cout << ''Hashomatic' хешируется как '
 << hashFun('Hashomatic') << '
';

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

'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. Он использует некоторые из возможностей хеш-контейнеров, описываемых в этом рецепте.

Пример 6.9. Простой менеджер сессий

#include <iostream>
#include <string>
#include <hash_map>
using namespace std;
class Session { /* ... */ };
// Облегчение читаемости с помощью typedef
typedef hash_map<string, Session*> SessionHashMap;
class SessionManager {
public:
 SessionManager() : sessionMap_(500) {} // Инициализация хеш-таблицы
                                        // 500-ми участками
 ~SessionManager() {
  for (SessionHashMap::iterator p = sessionMap_.begin();
   p != sessionMap_.end(); ++p)
   delete (*p).second; // Удаление объекта Session
 }
 Session* addSession(const string& login) {
  Session* p = NULL;
  if (!(p = getSession(login))) {
   p = new Session();
   sessionMap_[login] = d; // Присвоение новой сессии с помощью
  }                        // operator[]
  return(p);
 }
 Session* getSession(const string& login) {
  return(sessionMap_[login]);
 }
 // ...
private:
 SessionHashMap sessionMap_;
};

Каждый ключ отображается на единственный участок, а в участке может храниться несколько ключей. Участок это обычно одно- или двухсвязный список.

По хеш-функциям и таблицам написано огромное количество книг. Если вы заинтересовались этим вопросом, поищите в Google «C++ hash function».

Смотри также

Рецепт 6.6.

6.8. Хранение объектов в упорядоченном виде

Проблема

Требуется сохранить набор объектов в заданном порядке, например с целью доступа к упорядоченным диапазонам этих объектов без их пересортировки при каждом таком обращении.

Решение

Используйте ассоциативный контейнер set, объявленный в <set>, который хранит элементы в упорядоченном виде. По умолчанию он использует стандартный шаблон класса less (который для своих аргументов вызывает operator<), а можно передать в него собственный предикат сортировки. Пример 6.10 показывает, как сохранить строки в set.

Пример 6.10. Хранение строк в set

#include <iostream>
#include <set>
#include <string>