C++. Сборник рецептов - [93]
>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
>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
. Он использует некоторые из возможностей хеш-контейнеров, описываемых в этом рецепте.
Пример 6.9. Простой менеджер сессий
>#include
>#include
>#include
>using namespace std;
>class Session { /* ... */ };
>// Облегчение читаемости с помощью typedef
>typedef hash_map
>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
, объявленный в >
, который хранит элементы в упорядоченном виде. По умолчанию он использует стандартный шаблон класса
Java Enterprise Edition (Java EE) остается одной из ведущих технологий и платформ на основе Java. Данная книга представляет собой логичное пошаговое руководство, в котором подробно описаны многие спецификации и эталонные реализации Java EE 7. Работа с ними продемонстрирована на практических примерах. В этом фундаментальном издании также используется новейшая версия инструмента GlassFish, предназначенного для развертывания и администрирования примеров кода. Книга написана ведущим специалистом по обработке запросов на спецификацию Java EE, членом наблюдательного совета организации Java Community Process (JCP)
Разработчику часто требуется много сторонних инструментов, чтобы создавать и поддерживать проект. Система Git — один из таких инструментов и используется для контроля промежуточных версий вашего приложения, позволяя вам исправлять ошибки, откатывать к старой версии, разрабатывать проект в команде и сливать его потом. В книге вы узнаете об основах работы с Git: установка, ключевые команды, gitHub и многое другое.В книге рассматриваются следующие темы:основы Git;ветвление в Git;Git на сервере;распределённый Git;GitHub;инструменты Git;настройка Git;Git и другие системы контроля версий.
Рассмотрено все необходимое для разработки, компиляции, отладки и запуска приложений Java. Изложены практические приемы использования как традиционных, так и новейших конструкций объектно-ориентированного языка Java, графической библиотеки классов Swing, расширенной библиотеки Java 2D, работа со звуком, печать, способы русификации программ. Приведено полное описание нововведений Java SE 7: двоичная запись чисел, строковые варианты разветвлений, "ромбовидный оператор", NIO2, новые средства многопоточности и др.
Система сборки программ, используемая во FreeBSD, имеет значительно большие возможности, чем те, которые мы задействовали. Какие это возможности и как их использовать в своих портах?
Python - объектно-ориентированный язык сверхвысокого уровня. Python, в отличии от Java, не требует исключительно объектной ориентированности, но классы в Python так просто изучить и так удобно использовать, что даже новые и неискушенные пользователи быстро переходят на ОО-подход.
«Как пасти котов» – это книга о лидерстве и руководстве, о том, как первое совмещать со вторым. Это, если хотите, словарь трудных случаев управления IT-проектами. Программист подобен кошке, которая гуляет сама по себе. Так уж исторически сложилось. Именно поэтому так непросто быть руководителем команды разработчиков. Даже если вы еще месяц назад были блестящим и дисциплинированным программистом и вдруг оказались в роли менеджера, вряд ли вы знаете, с чего надо начать, какой выбрать стиль руководства, как нанимать и увольнять сотрудников, проводить совещания, добиваться своевременного выполнения задач.