Реализация хеш-таблицы ANSI C с данными в одном блоке памяти

Question

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

Большое спасибо заранее за все входные данные.

РЕДАКТИРОВАТЬ: Это не такобязательно должна быть хеш-таблица, что бы ни делала таблица пар ключ-значение.

Answer 1

Количество раз, которое вы сериализовали бы такую ​​структуру данных (и отправка по сети также сериализует) по сравнению с тем, сколько раз вы использовали бы такую ​​структуру данных (в вашей программе), довольно мало. Таким образом, в большинстве реализаций основное внимание уделяется скорости, а не «возможно, проще сериализации».

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

• перераспределить память при операциях добавления
• Наиболее похоже на сжатие / вакуум при операциях удаления (так что один блок, который вам так нравится, плотный и не имеет отверстий)

Большинство сетевых операций в любом случае буферизуются, просто перебирайте ключи и отправляйте ключи + значения.

Answer 2

В системе Unix я, вероятно, использовал бы буфер с общей памятью (см. shm_open()), или, если недоступен файл с отображением в памяти с флагом MAP_SHARED, см. Различия в ОС хотя http://en.wikipedia.org/wiki/Mmap

Если и shm_open, и mmap недоступны, вы все равно можете использовать файл на диске (в некоторой степени), вам нужно позаботиться о правильной блокировке, я бы отправил сигнал разблокировки на следующий процесс и, возможно, поиск обновленной части файла, затем этот процесс снова блокирует файл, ищет интересную часть и продолжает работу как обычно (обновляет / удаляет / и т. д.).

В любом случае вы можете свободно создавать макет хеш-таблицы или что угодно, например, иметь пары ключ / поиск фиксированной ширины. Таким образом, у вас будет быстрый доступ к ключам вашей хеш-таблицы, и при необходимости вы будете искать часть данных, а затем скопировать / удалить / изменить / и т. Д.

В идеале этот файл, конечно, должен быть на оперативном диске.

Answer 3

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

Напишите свою собственную функцию для сериализации (и unserialize ) хеш-таблицы наиболее удобным для вас способом. Вы можете сохранить сериализованный контент, если он вам нужен несколько раз (конечно, когда изменяется хеш-таблица, вам нужно обновить сериализованную «версию», хранящуюся в памяти).

Answer 4

Я полностью согласен с Акирой (+1). Еще один комментарий о местонахождении данных. Как только таблица становится больше или если спутниковые данные достаточно велики, наверняка возникает загрязнение кэша, которое дополнительно замедляет любую операцию над таблицей, или, другими словами, вы можете полагаться на цепочку кэша уровня 1/2/3 для обслуживания ключевые данные незамедлительно при потере кеша, когда вам нужно получить доступ к спутниковым данным (например, для сериализации).