Разработана нестандартная хеш-таблица на языке Си, оптимизированная для минимизации потребления памяти и быстрого разрешения коллизий. Ключевой особенностью является использование единого массива, где каждый элемент содержит индекс следующего элемента в списке коллизий и сами данные, что позволяет избежать избыточного выделения памяти.
Реализация таблицы сочетает преимущества открытой адресации и метода цепочек. Для экономии памяти в 64-битных системах используются 32-битные целые числа для индексов, ограничивая количество элементов, но сохраняя 4 байта на каждый элемент массива. Предусмотрены callback-функции для вычисления хеш-значений и сравнения данных, позволяющие таблице работать с разными типами данных и сценариями, включая случаи, когда типы добавляемых и искомых элементов отличаются.
Для использования хеш-таблицы предоставляется набор функций, включая инициализацию, установку функций для работы с данными (хеширование, сравнение), добавление, поиск и удаление элементов. Реализована потокобезопасная версия с возможностью компиляции с опцией
Библиотека прошла тщательное тестирование, включая проверку добавления, поиска, обновления и удаления элементов при различной заполненности таблицы, а также тестирование потокобезопасной версии с использованием нескольких потоков. Дополнительно проводилось тестирование с инструментами AddressSanitizer и MemorySanitizer для выявления ошибок.
Изображение носит иллюстративный характер
Реализация таблицы сочетает преимущества открытой адресации и метода цепочек. Для экономии памяти в 64-битных системах используются 32-битные целые числа для индексов, ограничивая количество элементов, но сохраняя 4 байта на каждый элемент массива. Предусмотрены callback-функции для вычисления хеш-значений и сравнения данных, позволяющие таблице работать с разными типами данных и сценариями, включая случаи, когда типы добавляемых и искомых элементов отличаются.
Для использования хеш-таблицы предоставляется набор функций, включая инициализацию, установку функций для работы с данными (хеширование, сравнение), добавление, поиск и удаление элементов. Реализована потокобезопасная версия с возможностью компиляции с опцией
THREAD_SAFETY. Библиотека прошла тщательное тестирование, включая проверку добавления, поиска, обновления и удаления элементов при различной заполненности таблицы, а также тестирование потокобезопасной версии с использованием нескольких потоков. Дополнительно проводилось тестирование с инструментами AddressSanitizer и MemorySanitizer для выявления ошибок.
