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

Вступление

Всем доброго дня! В предыдущей статье Сравнение hash map С/C++ с dict Python (часть 1) я написал простейшую телефонную книгу на языке Python и частично написал телефонную книгу на языке C. Во второй части я напишу остальную часть функционала телефонной книги на языке C и отвечу на вопрос читателя. Открывайте свои IDE и приготовьтесь продолжить писать код по теме hash map.

Телефонная книга на языке C

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

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

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

// функция для получения названия контакта (фи)
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 struct contact *contactA = a;
    const struct contact *contactB = b;
    return strcmp(contactA->title, contactB->title);
}

void get_all_contacts(struct hashmap *phone_book) {
    size_t iter = 0;
    void *item;
    if (hashmap_count(phone_book)  0) {
        printf("Hash map пуста!\n");
    }

    while (hashmap_iter(phone_book, &iter, &item)) {
        const struct contact *contact = item;
        printf("%s - %s\n", contact->title, contact->number);
    }
}

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

// Главная функция
int main() {
    // Создание hash map
    struct hashmap *phone_book = hashmap_new(
        sizeof(struct contact),
        0,
        0,
        0,
        hash,
        compare,
        NULL,
        NULL
    );

    // Добавление контактов
    hashmap_set(
        phone_book,
        &(struct contact){
            .title = get_title("Николай", "Николаев"),
            .number = "+72423535354"
        }
    );

    hashmap_set(
        phone_book,
        &(struct contact){
            .title = get_title("Виталий", "Краснов"),
            .number = "84424434345"
        }
    );

    hashmap_set(
        phone_book,
        &(struct contact){
            .title = get_title("Сергей", "Сергеев"),
            .number = "83201345024"
        }
    );

    // Количество контактов
    size_t count = hashmap_count(phone_book);
    printf("Количество контактов: %zu\n", count);

    printf("--------------------------------\n");

    struct contact *contact;

    // Получаем контакт
    contact = hashmap_get(
        phone_book,
        &(struct contact){
            .title=get_title("Николай", "Николаев")
        }
    );

    if (contact != NULL) {
        // Получаем номер
        printf("%s\n", contact->number);
    }
    else {
        printf("Контакт не обнаружен!\n");
    }

    printf("--------------------------------\n");

    // Получаем все контакты
    get_all_contacts(phone_book);

    printf("--------------------------------\n");

    // Удаляем контакт
    hashmap_delete(
        phone_book,
        &(struct contact){
            .title=get_title("Виталий", "Краснов")
        }
    );

    // Получаем все контакты (для проверки после удаления)
    get_all_contacts(phone_book);

    printf("--------------------------------\n");

    // Очищаем hash map от записей
    hashmap_clear(phone_book, false);

    // Получаем все контакты (когда hash map пуста)
    get_all_contacts(phone_book);

    // Освобождение памяти занятой hash map
    hashmap_free(phone_book);

    return 0;
}

Давайте посмотрим на код, который у нас получился, и разберём его. Сразу можно заметить, что я изменил создание структуры контакта. Теперь это выглядит так: struct contact { вместо typedef struct {. Я решил сильно не отходить от примера библиотеки hashmap.c и это воспринимается проще если кто-то из читателей вдруг захочет поработать с библиотекой сам. Функцию get_title() я оставил без изменений. Далее идёт функция compare(), в которой я обновил строки const struct contact *contactA = a; и const struct contact *contactB = b;, добавив к ним struct. Мне пришлось это сделать так как при создании структуры я убрал typedef. Какой способ лучше использовать - решать вам. Способ с typedef может быть более удобным так как вам не придётся писать struct в алиасах. Алиас - это дополнительное имя (в нашем случае для структуры данных). В нашем примере contactA это алиас для указателя на структуру contact.

Идём далее вниз по строчкам кода и видим, что я добавил новую функцию get_all_contacts(), которая выводит на экран все контакты из телефонной книги. Строка void get_all_contacts(struct hashmap *phone_book) { объявляет функцию, которая использует void так как функция не возвращает значение в return. Функция имеет параметр, который принимает аргумент структуры hashmap (в нашем случае это наша телефонная книга). В условии if (hashmap_count(phone_book) 0) { мы обрабатываем случай если в телефонной книге 0 контактов. В этом случае мы выводим строку "Hash map пуста!\n" функцией printf. Далее у нас идёт строка кода с циклом while (hashmap_iter(phone_book, &iter, &item)) {. Функция hashmap_iter из библиотеки hashmap.h нам нужна, чтобы итерировать (обойти) в цикле while всю нашу has map телефонную книгу. Указатели в &iter, &item используются для указания адресов переменных, объявленных выше в коде, для изменения их значений. Переменная iter является индексом в контексте итерации по hash map. Она используется для отслеживания текущего положения во время обхода элементов hash map. Переменная item хранит наш контакт с title и number. В строке printf("%s - %s\n", contact->title, contact->number); мы выводим на экран название контакта и телефон. Строка contact->title, contact->number получает доступ к переменным структуры, на которые указывает contact.

Строки const char *str = key; и return hashmap_sip(str, strlen(str), seed0, seed1); из функции hash были заменены. Давайте посмотрим на изменённые строки. Строка const struct contact *contact = key; создаёт алиас (псевдоним) для структуры contact. Это наш ключ, для которого мы получаем хеш в строке hashmap_sip(contact->title, strlen(contact->title), seed0, seed1);. Отличие в том, что мы обращаемся к значению из структуры, а не просто к строке как это было раньше. Это всё также взято из примера работы с библиотекой hashmap.h.

Спустимся ниже по строкам кода и перейдём в места вызовов новых функций. Функция hashmap_get(), встроенная в библиотеку hashmap.h, нужна нам, чтобы получить один контакт из телефонной книги. Она принимает аргументы phone_book и структуру с title контакта "Николай Николаев", строку которой собирает функция get_title(). Далее у нас идёт условие if (contact != NULL) { которое пропустит printf("%s\n", contact->number); строку выведения на экран номера контакта в случае если контакт был найден. В противном случае будет выведена строка "Контакт не обнаружен!\n". Я понимаю, что if условие в данном месте кода это не есть хорошая практика. Этот пример (как делать не нужно) мне потребуется для одной из будущих статей =) Эти примеры телефонных книг будут модернизироваться мной в будущих статьях.

Давайте вкратце пройдём по остальным вызовам функций. Функция get_all_contacts(phone_book); принимает hash map в качестве аргумента и выводит все контакты из телефонной книги. После неё идёт функция удаления контакта hashmap_delete(), как и другие похожие функции она принимает hash map и указатель на структуру c title где мы ищем контакт "Виталий Краснов". Функция hashmap_clear(phone_book, false); библиотеки hashmap.h очистит hash map от записей. Если стоит false, код будет увеличивать размер hash map, освобождая старые ресурсы и создавая новые для более эффективного использования памяти при увеличении количества элементов. Строка hashmap_free(phone_book); делает полную очистку памяти занимаемой hash map. Это увеличивает безопасность кода, предотвращает утечки памяти, освобождает неиспользуемые ресурсы ПК. Давайте теперь скомпилируем и запустим наш доработанный код.

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

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

Обратите внимание на команду компиляции. Мы указываем относительный путь до библиотеки hashmap/hashmap.c. Теперь давайте взглянем на результат работы программы.

Вывод в terminal

Количество контактов: 3
--------------------------------
+72423535354
--------------------------------
Николай Николаев - +72423535354
Виталий Краснов - 84424434345
Сергей Сергеев - 83201345024
--------------------------------
Николай Николаев - +72423535354
Сергей Сергеев - 83201345024
--------------------------------
Hash map пуста!

Программа отработала верно и мы видим практически те же строки кода, что и при выводе Python программы. Исключение - строка Hash map пуста!. Язык C не предусматривает увидеть пустую hash map со скобочками {} как в Python. Поэтому для информирования я вывел строку, которая говорит нам о том, что hash map пуста. Обработать пустую hash map можно по-разному. Этим мы с вами займёмся в одной из следующих статей.

Поздравляю, вот мы с вами и написали простейшую телефонную книгу на C языке! В первой части статьи я вам обещал написать версию телефонной книги на C++ и я это уже воплотил в коде у себя в IDE. Я решил не включать реализацию на C++ во вторую часть. Если я буду объяснять синтаксис этого кода подробно, то вторая часть статьи очень затянется. Также нужно будет рассказать вам об отличиях реализации телефонной книги на C++ от реализаций Python и C. Ещё я подумал о небольшой вводной исторической справке о языке C++. Это всё не влезет во вторую часть, поэтому я решил анонсировать третью часть статьи. В третьей части будет: историческая справка по C++, реализация телефонной книги на С++, сравнение синтаксиса и реализаций телефонных книг.
А сейчас давайте перейдём к ответам на вопрос от читателя.

Ответы на вопросы

В комментарии Telegram к первой части статьи мне задал вопрос подписчик канала с ником Антон 'Arlate'. Вопрос следующий: "Сначала хотел спросить зачем вообще хешировать. Но вспомнил что из себя "строка" представляет. Даже в питоне это, на низком уровне, где-то в недрах питона, массив символов. А нам надо из них получить одно целое число. Но как из этого числа получается индекс в массиве?".

Давайте полностью ответим на вопрос читателя, так как он начал рассуждение по поводу хеширования и массива, но не довёл мысль до конца. Строка в Python - это неизменяемая последовательность упорядоченных символов. Нельзя менять строку по индексу. Такой метод как replace создаёт новую строку на базе старой с новыми символами. В традиционном плане это не совсем массив, но что-то очень с ним родственное.

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

Теперь отвечу на основной вопрос читателя про индекс. Индекс в hash map Python, как и в других языках, формируется из хеша. Потому вопрос Но как из этого числа получается индекс в массиве? Антона 'Arlate' звучит очень правильно. После определения хеша встроенной функцией hash() (язык Python) происходит определение индекса. Это делается операцией взятия по модулю index = hash(key) % size_of_table. Здесь hash(key) это получение хеша по ключу, size_of_table это количество элементов в hash map, а оператор % вернёт остаток от деления, который и будет нашим индексом. Таким способом и рассчитывается индекс. Это формула в упрощённом виде. В Python размер dict автоматически увеличивается, а ключи перехешируются. Библиотека hashmap.h тоже динамически увеличивает размер hash map. Вместо прямого использования операции модуля (%), библиотека применяет битовую маску. Это более эффективно, когда размер таблицы является степенью двойки. Также в ней используется метод открытой адресации с Robin Hood хешированием (специальный алгоритм для хеширования), что позволяет эффективно управлять коллизиями и размером таблицы.

Заключение

1. Дописали функционал телефонной книги на языке C;
2. Я дал ответ на вопрос читателя;