C++ за 21 день седьмое издание

С++11____________________________________________


Контейнер std: :unordered_map библиотеки STL на базе хеш-таблиц ключей и значений

Начиная с версии C++11 библиотека STL предоставляет хеш-карту в форме класса s t d : :u n o rd e re d _ m a p . Для использования этого ш аблона класса включите его заголо­ вок:

#include

Контейнер u n o r d e r e d map предоставляет преимущество постоянной продолжитель­ ности вставки, удаления и поиска произвольных элементов в контейнере.

Как работают хеш-таблицы

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

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

Индекс = Хеш-функция (Ключ, РазмерТаблицы) ;

При выполнении функции f i n d ( ) для данного ключа Хеш-функция () используется еще раз, чтобы определить позицию элемента и возвратить из таблицы значение по пози­ ции, как возвратил бы хранимый элемент массива. В тех случаях, когда Хеш-функция () не определена, тот же Индекс может быть у нескольких элементов, расположенных в той же ячейке, которая внутренне станет списком элементов. В таких случаях, называемых конфликтом (collision), поиск осущ ествляется медленнее и не имеет больше постоянной продолжительности.

Предоставление специального предиката сортировки

477