Если вы не планируете делать большое количество удалений, то это не так сложно.Удаление приводит к фрагментации.
Вам также необходимо зафиксировать ключ фиксированной длины.Вы упомянули 80 байтов.Ваши ключи могут дублироваться?Если нет, то это даже проще.
Итак, вот что вы делаете.
Вы создаете массив:
struct {
char value[80];
char *data;
} key;
И вы сохраняете этот массив отсортированным.
Если ключи могут дублироваться, вам необходимо:
struct link {
char *data;
link *next;
}
struct {
char value[80];
link *data;
} key;
(My C ржавый, но это суть). У каждого ключа есть ключ, указывающий на связанный список значений.
Тогда поиск - это простой бинарный поиск.«Боль» заключается в поддержании этого массива и вставке / удалении ключей.Это не так больно, как кажется, но экономит много памяти, особенно в 64-битных системах.
То, что вы хотите уменьшить, это количество указателей.Указатели дороги, когда у вас много структур, заполненных указателями.В 64-битной системе указатель составляет 8 байтов.Таким образом, для одного указателя у вас уходит 8 МБ бюджета памяти.
Таким образом, затраты заключаются в создании массива, копировании и сжатии памяти (если вы «знаете», у вас будет миллион строк и вы сможете зафиксироватьзатем malloc (1000000 * sizeof (key)) сразу же, это сэкономит вам некоторое копирование во время расширения).
Но не бойтесь, как только он запущен, производительность довольно хорошая,Современные процессоры на самом деле неплохо копируют 100М блоков памяти.
Просто в стороне, я просто сделал что-то похожее на Java.На 64-битной JVM карта с 25M записями - это 2G оперативной памяти.Мое решение (с использованием методов, подобных этому) имеет около 600 млн.).Java использует больше указателей, чем C, но предпосылка та же.