Деревья, множества, хэш-таблицы
Бинарные деревья. Начало
Бинарное дерево. Способы обхода и удаления вершин
Реализация бинарного дерева на Python
Множества (set). Операции над множествами
Множества set и multiset в C++
Контейнер map библиотеки STL в C++
Префиксное (нагруженное, Trie) дерево. Ассоциативные массивы
Хэш-таблицы. Что это такое и как работают
Хэш-функции. Универсальное хэширование
Метод открытой адресации. Двойное хэширование
Использование хэш-таблиц в Python и С++
Обучающие курсы
Python Python ООП Структуры данных Django C/C++
Телеграм-каналы
Канал selfedu_rus Python Django Машинное обучение Java и С++
Наш канал

Использование хэш-таблиц в Python и С++

Курс по структурам данных: https://stepik.org/a/134212

На предыдущих занятиях мы с вами подробно рассмотрели принципы работы хэш-таблиц. Естественно, возникает вопрос, как их можно использовать в своих программах? Обычно, в каждом современном языке программирования имеется класс (или классы), который позволяет создавать и работать с хэш-таблицами. Мы затронем два популярных языка программирования: Python и C++. В Python на основе хэш-таблиц реализован словарь dict и множество set. Как с ними работать я уже подробно рассказывал в курсе «Python для начинающих»:

#29. Введение в словари (dict): https://www.youtube.com/watch?v=JV2olufru8Q
#32. Множества (set) и их методы: https://www.youtube.com/watch?v=Z3lw-yMZKuQ

Поэтому здесь лишь затрону их в целом.

Хэш-таблицы в Python

Когда мы в программе на Python создаем словарь, например:

d = {'one': 1, 'two': 2, 'five': 5}

то формируется хэш-таблица с ключами 'one', 'two', 'five' и соответствующими значениями 1, 2, 5. Если нам нужно добавить в эту хэш-таблицу еще какой-либо ключ, то это можно сделать так:

d['three'] = 3

А считывание значений по ключу выполняется, например, командой:

value = d['one']
print(value)

Как видите, все предельно просто и при этом мы имеем возможность представлять данные в формате «ключ-значение» на уровне хэш-таблицы. Кстати, именно поэтому в качестве ключей словаря должны использоваться только хэшируемые объекты. В Python к ним относятся все неизменяемые типы данных, такие как строки, числа, булевы значения, кортежи и т.п. А вот если попытаться указать нехэшируемые (изменяемые) объекты, скажем, список:

d[[1,2,3]] = 10

то в процессе выполнения этой команды будет сгенерирована ошибка:

TypeError: unhashable type: 'list'

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

По аналогии со словарями в Python работает и множество:

s = {'one', 'two', 'five'}

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

s = {'one', (1, 2, 3), True, 10, 5.8}

А вот нехэшируемые приводят к той же ошибке, что и у словарей:

s = {'one', (1, 2, 3), True, 10, 5.8, [1, 2, 3]}

Здесь последний элемент список (list) относится к изменяемому, а значит, нехэшируемому типу.

Хэш-таблицы в С++

В языке С++ для использования хэш-таблиц можно воспользоваться классом unordered_map стандартной библиотеки шаблонов STL. Для этого вначале подключается заголовок:

#include <unordered_map>

и в функции main() получаем возможность создавать объекты (хэш-таблицы) с помощью этого класса:

int main()
{
         setlocale(LC_ALL, "ru");
         using namespace std;
 
         unordered_map<string, int> ar;
 
         return 0;
}

Класс unordered_map в целом имеет тот же функционал (тот же набор методов), что и класс map, о котором мы уже с вами говорили. Только map реализован на основе красно-черного бинарного дерева, а unordered_map – на основе хэш-таблиц. Поэтому в программе выбирается тот класс, который предпочтительнее использовать для хранения и обработки данных.

Так как функционал этих классов схожий, то я кратко продемонстрирую работу с unordered_map. При создании объекта, мы в угловых скобках указываем тип ключа и тип значения. В примере ключ имеет тип string (строка), а значение тип int (целое число). Сам объект ar представляет собой пустую хэш-таблицу.

Чтобы внести в нее какие-либо данные, можно воспользоваться или методом insert():

ar.insert(pair<string, int>("one", 1));
ar.insert(make_pair("three", 3));

но проще и лучше методом emplace():

ar.emplace("four", 4);

Для перебора содержимого хэш-таблицы удобно использовать цикл for следующим образом:

for (auto& item : ar)
{
         cout << item.first << " " << item.second << endl;
}

В результате увидим на экране строчки:

one 1
three 3
four 4

Также добавлять новые данные можно с помощью оператора квадратные скобки:

ar["five"] = 5;

И читать значения по ключу:

auto val = ar["one"];
cout << val << endl;

Для удаления ключа из хэш-таблицы можно воспользоваться методом erase():

auto it = ar.erase("three");

Данный метод возвращает булево значение false, если удаление ключа по каким-либо причинам не было выполнено и true в противном случае.

Для поиска элемента по ключу используется метод find():

auto it = ar.find("two");

Данный метод возвращает итератор на пару ключ-значение, если указанный ключ был найден, либо значение ar.end(), если ключ не найден.

Класс unordered_set

Наряду с классом unordered_map в библиотеке STL языка С++ есть еще один подобный класс unordered_set, который реализует множество на основе хэш-таблиц. Функционал этого класса подобен функционалу класса set, о котором мы с вами уже говорили.

Чтобы использовать unordered_set в своей программе, нужно вначале подключить заголовок:

#include <unordered_set>

А, затем, в функции main() создать экземпляр этого класса, например, так:

int main()
{
         setlocale(LC_ALL, "ru");
         using namespace std;
 
         unordered_set<int> s = { 1, 2, 3 };
 
         for (auto& item : s)
         {
                   cout << item << " " << endl;
         }
 
         return 0;
}

Мы здесь сразу инициализируем множество значениями 1, 2, 3. В результате создается хэш-таблица с такими ключами и далее, с помощью цикла for, мы перебираем эту хэш-таблицу и выводим значения ключей в консоль.

Я не буду подробно останавливаться на работе с классом unordered_set, так как он содержит подобный набор методов, что и класс set. Основные из них приведены в таблице ниже.

Метод	Описание	Сложность
begin(), cbegin()	Возвращает итератор на первый элемент списка	O(1)
end(), cend()	Возвращает итератор на последний элемент списка	O(1)
size()	Возвращает число элементов в списке	O(1)
insert()	Вставка нового элемента в произвольную позицию	O(1)
erase()	Удаление произвольного элемента списка	O(1)
find()	Поиск элемента по значению	O(1)
clear()	Очистка двусвязного списка	-
empty()	Возвращает true, если множество пустое и false в противном случае	O(1)

Например, мы можем выполнить следующие операции:

cout << s.size() << endl;
 
s.insert(4);
s.erase(2);
auto it = s.find<int>(1);
if (it != s.end())
{
         cout << *it << endl;
}

Главное здесь знать, что unordered_set использует хэш-таблицу для хранения и обработки значений, а класс set – бинарное красно-черное дерево. Во всем остальном эти два класса очень похожи.

Заключение

На этом занятии мы увидели с вами, как можно применять хэш-таблицы для хранения данных в языках Python и С++. Причем, хэш-таблицы могут быть использованы не только в формате «ключ-значение» (как это у карт (map) и словарей (dict)), но и просто в формате «ключ», как это сделано у множеств.