Сравнение hash map С/C++ с dict Python (часть 1)

Краткое описание

Всем доброго дня! Рассказывая об областях применения в двух моих предыдущих статьях "Где применяются Python и C/C++ (часть 1)" и "Где применяются Python и C/C++ (часть 2)" я совершенно не писал код. За эти несколько недель я очень соскучился по написанию кода и не только я один. Сегодня мы наконец-то начнём писать код в статье снова =) Я решил выбрать тему hash table она же hash map, а в Python её называют dict или словарь. Откройте свои IDE и приготовьтесь писать код мы начинаем интересную и важную тему hash table (хеш таблица).

Dict в Python

Для простоты давайте начнём разбирать тему хеш таблиц на более простом по сравнению с низкоуровневыми языками C и C++ высокоуровневом языке Python. Читатели, которые писали на языке Python скорее всего знают что dict это тип данных словарь, который хранит пару key (ключ) и value (значение). Но что такое hash table (хеш таблица) и что делает dict (словарь) хеш таблицей? Прежде чем я дам вам ответы на эти вопросы я реализую на dict простейшую телефонную книгу, запущу код и на его примере наглядно расскажу про хеш таблицу.

phone_book = {
    'Николай Николаев': '+72423535354',
    'Виталий Краснов': '84424434345'
}

def add_contact(firstname, lastname, number):
    """функция добавит новый контакт в книгу"""
    contact = f'{firstname} {lastname}'
    phone_book[contact] = number
    
def get_number(firstname, lastname):
    """функция получает номер по фи"""
    contact = f'{firstname} {lastname}'
    if contact in phone_book.keys():
        return phone_book[contact]
    return 'Контакт не обнаружен!'
    
def get_all_contacts():
    """функция получает список всех контактов"""
    for contact, number in phone_book.items():
        print(f'{contact} - {number}')
        
def del_contact(firstname, lastname):
    """функция удалит контакт по фио"""
    contact = f'{firstname} {lastname}'
    del phone_book[contact]
    
def del_all_contacts():
    """функция удалит все контакты из телефонной книги"""
    copy_contacts = phone_book.copy()
    for contact in copy_contacts.keys():
        del phone_book[contact]
        
        
if __name__  '__main__':
    # получим номер контакта
    nuber = get_number(firstname='Николай', lastname='Николаев')
    print(nuber)
    print('--------------------------------')
    
    # добавим новый контакт
    add_contact(firstname='Сергей', lastname='Сергеев', number='83201345024')
    
    # выведем колличество контактов
    print(f'Количество контактов: {len(phone_book)}')
    print('--------------------------------')
    
    # выведем список всех контактов
    get_all_contacts()
    print('--------------------------------')
    
    # удалим контакт
    del_contact(firstname='Виталий', lastname='Краснов')
    
    # снова выведем список всех контактов
    get_all_contacts()
    print('--------------------------------')
    
    # удалим все контакты
    del_all_contacts()
    
    # убедимся что телефонная книга пуста
    print(phone_book)

Как мы видим я реализовал простую телефонную книгу с использованием dict (словарь). На базе словаря удобно делать простую телефонную книгу, получая номер по ключу. Я не случайно выбрал Python в качестве первого языка для реализации телефонной книги ведь на нём её реализовать проще и быстрее чем на C или С++. Получиться некий прототип, основываясь на котором я постараюсь реализовать тот же функционал на C и C++ языках. Давайте пройдём по строкам и посмотрим что же я написал за телефонную книгу. 

Переменная phone_book хранит себе keys (ключи) и values (значения). В качестве ключа у нас строка с именем и фамилией через пробел, а в качестве значения строка телефонного номера. Ключ и значение имеют тип данных str (строка). В словаре для наглядности я создал пару записей. 

Далее у нас идёт несколько функций, с помощью которых будет удобно использовать телефонную книгу. Первая функция add_contact нужна для добавления нового контакта в телефонную книгу. Она принимает три аргумента, которые я люблю явно присваивать к её параметрам при вызове функции firstname (имя), lastname (фамилия), number (номер). В строке contact = f'{firstname} {lastname}' я собираю строку ключа из имени и фамилии через пробел с использованием f строки и присваиваю строку переменой contact. Далее я присваиваю ключу из переменной contact для словаря phone_book значение из параметра number (номер). Скажу заранее что у меня нет цели в этой статье сравнивать и показывать все методы dict для Python. Для тех кому dict в новинку и интересно узнать глубже про его методы я оставлю ссылку на статью, где показаны методы словарей и не только (для новичков). В своих статьях я обычно показываю самые простейшие способы работы с тем или иным типом данных или структурой. Вернёмся к разбору кода. 

Далее у нас идёт функция get_number, которая нужна для получения номера по имени и фамилии контакта. Я не буду объяснять повторно одинаковый код, а буду лишь останавливаться на новом коде для вас. Так я избавляюсь от повторения одного и того же и буду быстрее продвигаться дальше. В if contact in phone_book.keys(): ищем ключ (контакт) в ключах словаря для проверки факта его наличия. Если мы этого не сделаем и попробуем получить ключ, которого нет в словаре, то получим ошибку KeyError. Метод keys() выдаёт нам только ключи из словаря. По нему даже можно пройти в цикле for как по list (списку), но он из себя представляет <class 'dict_keys'> имеет гораздо более сложную структуру чем обычный список. Так же его можно преобразовать в обычный list используя list(phone_book.keys()). В if условии мы возвращаем return phone_book[contact] наш телефонный номер если находим имя и фамилию контакта в ключах словаря телефонной книге. Если мы не находим ключи, то вернём return 'Контакт не обнаружен!' строку, которая нам говорит о том что мы не обнаружили контакт в телефонной книге. Опытные читатели и разработчики могли заметить что в предыдущем методе add_contact можно было тоже добавить проверку на существование контакта. Это бы предотвратило перетирание данных так как мы создаём новый контакт, а не редактируем его. Да и в остальных методах можно много добавить разных проверок например на тип данных и прочие. По той же причине нет и прочих улучшений кода, которые делают код более читаемым. Я сделал это намеренно так как в следующей статье я хочу модифицировать данный код и показать как улучшить логику программы, обрабатывать ошибки, проверять на типы данных. Пока наш код будет простой основой. 

Смотрим далее функцию get_all_contacts(), которая нужна для вывода списка всех контактов из телефонной книги. В цикле for contact, number in phone_book.items(): мы обходим пары ключ и значение из каждой записи словаря, которые нам предоставляет метод items(). Метод items() возвращает <class 'dict_items'>, который создали для того чтоб оптимизировать производительность перебора ключей и значений словаря. Далее print(f'{contact} - {number}') выводим на экран функцией print фамилию по ключу из переменной contact и номера по значению из переменной number.Следующая функция del_contact удаляет пару ключ и значение контакта по строке по имени и фамилии. Тут я тоже не сделал проверку на ключ в словаре, но выше я писал причину почему я так сделал =) В строке del phone_book[contact] при помощи оператора del, которым можно удалять данные и из list (списка) в том числе я удаляю пару ключ и значение по строке с именем и фамилией. 

Следующая функция del_all_contacts() нужна чтоб полностью удалить все контакты из словаря телефонной книги. Код из строки copy_contacts = phone_book.copy() нужен для того чтоб полностью скопировать словарь в память. Это нужно так нам нужно пройти по словарю и одновременно удалить данные из него. Если мы сделаем так copy_contacts = phone_book то, создадите ссылку на словарь, а не скопируете его. При обходе получиться так что вы работаете с одним и тем же словарём как при удалении так и при обходе. В результате вы получите ошибку RuntimeError: dictionary changed size during iteration - словарь изменил размер во время выполнения итерации (прохода в цикле по нему). Язык Python защищается от неопределённого поведения программы таким образом. Поэтому я полностью копирую словарь и прохожу в цикле по его копии, а удаляю данные из оригинала. Подобным образом нужно делать и с list (список). Для списка тоже доступен метод copy(). Далее мы проходим по ключам словаря в цикле и удаляем пару ключ и значение. Как это работает рассматривал на примерах с функциями выше. 

Далее мы запускаем наш код в if __name__ '__main__': для того чтоб мой тестовый запуск кода был запущен только когда работаем из самого файла в данном случае это phone_book.py. При этом если мы импортируем код в другой файл .py как модуль, то код пробного запуска не будет мешаться и запускаться. Переменная __main__ примет значение '__main__' когда код запускается из самого файла phone_book.py. Далее я пробую запускать каждую функцию из кода и смотреть как они работают. На примере функции get_number мы сначала создаём переменную с этой функцией в строке nuber = get_number(firstname='Николай', lastname='Николаев'). Параметрам функции (её переменным) назначаем аргументы (значения). Затем мы выводим на экран результат в строке print(nuber). Я решил разделять результаты выполнения функций таким образом print('--------------------------------'). Аналогично мы запускаем все остальные функции. Ещё упомяну что я получаю количество контактов в строке print(f'Количество контактов: {len(phone_book)}'). Само количество контактов получаю встроенной в Python функцией len(), которая получит количество записей в dict (словаря) в данном случае.

Давайте запустим наш код и посмотрим что он выведет в terminal. Я запускаю код из IDE VSCode, нажав на кнопку запуска кода.

+72423535354
--------------------------------
Николай Николаев - +72423535354
Виталий Краснов - 84424434345
Сергей Сергеев - 83201345024
--------------------------------
Николай Николаев - +72423535354
Сергей Сергеев - 83201345024
--------------------------------
{}

Мы видим что функция get_number выдала нам номер +72423535354 по ключу, который был собран из имени и фамилии. 

Следующая функция add_contact() добавила нам новый контакт, но о результате свой работы она никак не показывает. Зато функция get_all_contacts() показала нам все контакты, включая тот который добавила функция add_contact(). 

Так что же такое hash table (хеш таблица) и почему dict (словарь) ей является? Для того чтоб ответить на эти вопросы нужно понять что такое хеширование и в чем заключается функция key (ключ). Простое понимание назначения ключа в словаре заключается в том что по нему мы легко можем получить значение. Для этого достаточно ввести название переменной словаря и в квадратных скобках указать ключ test_dict['key_name'] или использовать метод test_dict.get('key_name'). Метод get() удобен тем что он не вызывает ошибок если нет ключа в словаре. Данный метод вернёт None если не указано дефолтное значение и вернёт значение, которое вы указываете по дефолту. Пример test_dict.get('key_name', 'Нет ключа') вернёт строку 'Нет ключа' если не обнаружит ключа в словаре. Это может экономить строки кода, для логики программы. 

Теперь опустимся чуть глубже в логику работы словаря в Python и узнаем что такое хеширование ключа. После того как вы добавляете пару ключ значение в словарь Python ключ хешируется специальной хеш функцией. Хеш функция преобразует ключ в специальное числовое значение - уникальный хеш код. Это гарантирует уникальность ключа. Затем полученый хеш код используется для вычисления индекса, который необходим для поиска значения. Данные сохраняются в ячейке памяти хеш таблицы по рассчитанному индексу. Это удобно так как пк оперирует с числами. В списке мы аналогично получаем данные по индексу. В ссылках к статье я оставлю интересную статью с Хабр про хеш функции, которые дополнят мою статью и расскажут о хешировании ещё подробнее.

Мы реализовали простую хеш таблицу с уникальными индексами на языке Python. Но как же повторить подобное на простом языке C? Спойлер в стандартной комплектации C никак =)

Хеш таблица и её альтернативы в языке C

Язык C из коробки действительно не имеет ничего похожего на хеш таблицу. Из коробки вы можете реализовать похожий функционал на array (массив). Реализовывать самостоятельно алгоритм поиска (например линейный). Это всё будет работать не очень эффективно. Так же можно реализовать хеш таблицу самостоятельно что потребует очень глубокого знания алгоритмов и языка C. К счастью есть готовая сторонняя библиотека hashmap.c, разработанная Тайлом Уоллом. 

Данная библиотека предоставляет реализацию hash map (хеш карты), которая легко позволяет добавлять, удалять, искать элементы по ключу. Ссылку на данную библиотеку я оставлю в ссылках к статье. Термины hash table и hash map синонимы и оба относятся к типу структур, которые используют хеширование и предоставляют быстрый доступ к данным по ключу. Для использования библиотеки hashmap.c потребуется её скачать с официального сайта и подключить. Одной из ближайших тем для статей я хочу раскрыть тему подключения библиотек и их использования. Поэтому я не буду сейчас сильно заострять внимание на использовании библиотек в C. Пока я лишь скажу что подключу библиотеку локально. 

И так я перейду на сайт с библиотекой и скачаю с него библиотеку hashmap.h и файл hashmap.c, который понадобиться нам для компиляции. Создадим папку hashmap и положим эти два файла туда. Далее создадим файл phone_book.c, в котором будет храниться наша телефонная книга. Приступим к написанию телефонной книги на языке C, которая аналогична по функционалу той что мы написали на Python.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "hashmap/hashmap.h"

// Структура для хранения информации о контакте
typedef struct {
    char *title;
    char *number;
} Contact;

// функция для получения названия контакта (фи)
char *get_title(char *first_name, char *last_name){
    // Максимальный размер имени и фамилии 200 + 1 \0 конец строки + 1 для пробела
    char *new_title = malloc(202);
    // Копируем первую строку в строку контакта
    sprintf(new_title, "%s", first_name);
    // Добавляем пробел и фамилию
    strcat(new_title, " ");
    strcat(new_title, last_name);
    return new_title;
}

// Функция сравнения для структур Contact
int compare(const void *a, const void *b, void *udata) {
    const Contact *contactA = a;
    const Contact *contactB = b;
    return strcmp(contactA->title, contactB->title);
}

// Функция хеширования для строк
uint64_t hash(const void *key, uint64_t seed0, uint64_t seed1) {
    const char *str = key;
    return hashmap_sip(str, strlen(str), seed0, seed1);
}

// Главная функция
int main() {
    // Создание hash map
    struct hashmap *phone_book = hashmap_new(
        sizeof(Contact),
        0,
        0,
        0,
        hash,
        compare,
        NULL,
        NULL
    );
    
    // Добавление контактов
    hashmap_set(
        phone_book,
        &(Contact){
        .title = get_title("Николай", "Николаев"),
        .number = "+72423535354"
    });
    
    hashmap_set(
        phone_book,
        &(Contact){
        .title = get_title("Виталий", "Краснов"),
        .number = "84424434345"
    });
    
    hashmap_set(
        phone_book,
        &(Contact){
        .title = get_title("Сергей", "Сергеев"),
        .number = "83201345024"
    });
    
    // Колличество контактов
    size_t count = hashmap_count(phone_book);
    printf("Количество контактов: %zu\n", count);
    return 0;
}

Мы с вами написали код телефонной книги на языке C, близкий функционалом к тому что мы писали на Python. Давайте теперь взглянем на код повнимательней ибо он выглядит куда сложнее кода на Python. 

Первая строка #include <stdio.h> нам уже знакома в ней мы импортируем библиотеку ввода вывода. Она нам нужна для того чтоб печатать данные в terminal (эмулятор терминала в Linux). Библиотека #include <string.h> нам нужна для работы со строками. Следующая строка #include <stdlib.h> включает стандартную библиотеку функций, связанных с управлением памятью и выполнением процесса (например, выделение памяти, работа с аргументами командной строки). Она также содержит макросы для обработки ошибок и функции для генерации случайных чисел. Пока не буду останавливаться с подробностями на данной библиотеке. Далее строка #include "hashmap/hashmap.h" осуществляет импорт библиотеки для работы с hash map (хеш картой). Обратите внимание что мы используем относительный путь и "" используются для импорта локальных библиотек проекта. 

Следующий блок кода создаёт структуру для контакта. Эта структура внутри имеет две переменных char типа, которая будет хранить имя и фамилию в переменной title, а в переменной number будет храниться номер. Строка typedef struct { определяет пользовательский тип данных, который позволяет группировать данные различных типов под одним именем. Завершает эту конструкцию строка } Contact;, которая отвечает за название нового типа данных.

Следующей идёт функция get_contact(), в которой мы собираем имя, пробел и фамилию в один массив char. После Python так и хочется назвать это строкой =) Сначала мы выделяем размер для массива символов в строке char *new_title = malloc(202);. Затем мы копируем массив с именем в переменную contact в sprintf(new_title, "%s", first_name);. Далее мы конкатенируем (складываем) массивы char в strcat(new_title, " "); и strcat(new_title, last_name); и возвращаем готовый массив с именем и фамилией в return new_title;. 

Далее мы создаём функцию compare int типа, которая нужна для сравнения структур при сортировке. В отсортированном виде данные быстрее найти и в целом повышается скорость работы со структурой hash map. Она принимает в себя три параметра. Параметры const void *a и const void *b это указатели на две структуры контакта, которые нужно сравнить между собой. Указатель это переменная, которая хранит в себе адрес памяти для объекта. Это чем-то похоже на координаты на карте. Строка return strcmp(contactA->contact, contactB->contact); возвращает результат сравнения двух строк, которая производит функция strcmp. Возвращаться могут следующие варианты: отрицательное число (первая строка меньше второй), положительное число (если первая строка больше второй) и 0 (если строки равны). Оператор -> в contactA->contact и в contactB->contact используется для получения доступа к char *contact; структуры Contact через указатели contactA и contactB. 

Далее идёт сложная и одновременно важная функция hash, которая отвечает за хеширование нашего ключа. Принцип хеширования ключа и для чего это нужно мы уже разобрали на примере Python кода. Давайте разберёмся в её коде. Строка uint64_t hash(const void *key, uint64_t seed0, uint64_t seed1) { объявляет функцию uint64_t типа. Тип uint64_t является целым 64 битным числом. Более подробно о битности я расскажу в одной из следующих статей, когда я буду рассказывать о том как компьютер хранит данные на компьютере и как C и Python работают с ними. Тип uint64_t хранит только беззнаковые числа, что означает что он хранит только положительные числа от 0 до 18,446,744,073,709,551,615. В памяти тип uint64_t занимает 8 байт и всегда имеет фиксированный размер в независимости от архитектуры процессора и компилятора, что делает его надёжным. Параметр функции const void *key указывает на ключ, который мы будем хешировать. Параметр uint64_t seed0 хранит первое значение для алгоритма хеширования. Параметр uint64_t seed1 хранит второе значение для алгоритма хеширования. Результатом кода return hashmap_sip(str, strlen(str), seed0, seed1); будет возврат хеша для ключа. 

Функции хеширования мы передаём четыре аргумента. Первый аргумент хранит переменная str, которая хранит строку ключа. Второй аргумент strlen(str) это длина строки ключа. И остальные два аргумента это сиды, которые служат начальными значениями для инициализации процесса хеширования. Далее происходит магия хеширования - те самые сложные для понимания математические операции по вычислению хеша =) 

Наконец мы переходим к главной функции main() int типа, где мы собираем всю логику программы вместе. Создаём новую структуру в строке struct hashmap *phone_book = hashmap_new( для hash map. Для использования функции hashmap_new обязательно проверьте правильно ли вы импортировали библиотеку hashmap.h. Первым аргументом передаём sizeof(Contact) размер контакта, для определения размера памяти для хранения на компьютере. Аргументы 0, 0, 0 относятся к конфигурации hash map. Далее передаём hash ключа, функцию сравнения compare и NULL, NULL доп опции что не используются в данном случае. 

Далее я добавляю три контакта функцией hashmap_set() встроенной в библиотеку hashmap.h. В данном случае не вижу смысла создавать свою функцию добавления контакта поэтому использую готовый вариант. При добавлении в функции hashmap_set() мы указываем наш hash map phone_book, далее добавляем данные в структуру контакта &(Contact){.contact = get_title("Сергей", "Сергеев"), .number = "83201345024"}. Оператор & используется для получения адреса объекта. Далее в строке size_t count = hashmap_count(phone_book); мы получаем количество записей (контактов) в hash map. После этого выводим количество в строке printf("Количество контактов: %zu\n", count); Тип данных size_t этот тип данных используется чтобы хранить размер объекта с высокой точностью без погрешностей. Для печати данных этого формата используется спецификатор формата %zu. В данной статье с кодом закончили. Теперь давайте компилировать и запускать нашу неполную версию телефонной книги.

Компиляция и запуск кода в terminal

$ gcc -o phone_book phone_book.c hashmap/hashmap.c
$ ./phone_book

Вывод в terminal

Количество контактов: 3

На этом я заканчиваю первую часть статьи посвящённую hash map. Статья вышла очень большой поэтому я решил разделить её на две части. Во второй части статьи мы с вами добавим остальную часть функционала в версию на C, которую не добавили в первой части. Так же вас ждёт реализация телефонной книги на C++. Дальше будет ещё интереснее :)

Заключение

1. Рассмотрели тему dict (словарь) в Python;
2. Разобрались что такое и для чего hash в hash table;
3. Написали телефонную книгу на Python и C;
4. Создали hash map на языке C, используя библиотеку hashmap.h;

Ссылки к статье

1. Словари (dict) и работа с ними. Методы словарей (язык Python)
2. Хеширование: ключ к безопасности и эффективности в мире цифровых данных
3. Библиотека hashmap.h (язык C)